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

Две функции, направление прогрева

Алгоритм вычисления функций F(n) и G(n) задан соотношениями: G(n) = (остаток от деления n на 7) + 5, если n ≥ 20000; G(n) = G(n + 9) + 2, если n < 20000; F(n) = 3 · G(n + 100) + 4, если n < 20; F(n) = F(n − 1) + G(5 · n), если n ≥ 20. Чему равно значение F(3000)?

Учебная задача

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

@lru_cache(None)
def G(n):
    if n >= 20000:
        return n % 7 + 5
    return G(n + 9) + 2

@lru_cache(None)
def F(n):
    if n < 20:
        return 3 * G(n + 100) + 4
    return F(n - 1) + G(5 * n)

for n in range(20000, 0, -1):
    G(n)
for n in range(1, 3001):
    F(n)
print(F(3000))