0У
Все задачи №16
№16

две функции

Алгоритм вычисления значений функций F(n) и G(n), где n — целое число, задан соотношениями: F(n) = 3 × G(n − 3) + 7; G(n) = n + 2, если n ≤ 20; G(n) = G(n − 3) + 1, если n > 20. Чему равно значение F(37811)?

Источник: ФИПИ (банк), № 29970

Ответвпиши то, что вывела программа
Показать разбор
  1. Перепиши обе функции из условия и поставь на них @lru_cache(None).
  2. G спускается с шагом 3 от большого числа, поэтому без прогрева будет слишком глубокая рекурсия.
  3. Прогрей G по возрастанию, от 1 до 37808: столько нужно для F(37811).
  4. Напечатай F(37811).
from functools import lru_cache

@lru_cache(None)
def F(n):
    return 3 * G(n - 3) + 7

@lru_cache(None)
def G(n):
    if n <= 20:
        return n + 2
    if n > 20:
        return G(n - 3) + 1

for n in range(1, 37809):
    G(n)
print(F(37811))