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

Большие числа, одна функция

Алгоритм вычисления функции F(n) задан соотношениями: F(n) = 1, если n < 8; F(n) = n · F(n − 2), если n ≥ 8. Чему равно значение выражения F(60000) / F(59996)?

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

Ответвпиши то, что вывела программа
Показать разбор
  1. Перепиши функцию из условия: F(n) = 1 при n < 8, иначе n * F(n - 2).
  2. Значения получаются огромные, поэтому поставь @lru_cache(100): кэш держит только последние значения и не забивает память.
  3. Прогрей функцию циклом снизу вверх до самого большого нужного n. Значения F(60000) и F(59996) запомни в переменные прямо в цикле.
  4. Все остальные n считай в ветке else: F(n). Без неё кэш не прогреется.
  5. Раздели первое значение на второе через // и напечатай результат.
from functools import lru_cache

@lru_cache(100)
def F(n):
    if n < 8:
        return 1
    return n * F(n - 2)

for n in range(8, 60001):
    if n == 60000:
        x1 = F(n)
    elif n == 59996:
        x2 = F(n)
    else:
        F(n)
print(x1 // x2)