6 Шпаргалка по заданию 16

Шпаргалка по заданию 16

Способ 1 — рекурсия с кэшем

from functools import lru_cache
import sys; sys.setrecursionlimit(100000)
@lru_cache(None)
def F(n):
    if <база>: return <значение>
    return <формула с F(n±...)>
print( <нужное выражение с F> )

Способ 2 — таблица

f = [0]*(N+1)
f[1] = <база>                       # или заполнить базовые n
for n in range(2, N+1):             # вниз: range(N, -1, -1)
    f[n] = <формула с f[n±...]>
print( <выражение с f[...]> )

⚠️ Типичные ошибки

1. Забыл поднять лимит рекурсии — на больших n программа падает. sys.setrecursionlimit(100000).

2. Неверно перенёс базу: сколько базовых случаев в условии — столько и в коде (if n == 1, if n < 10 и т. д.).

3. Перепутал направление: база у маленьких n — считаем вверх; база у больших — вниз (обратный range).

4. Сделал массив слишком коротким — нужен размер хотя бы до максимального n в выражении.

5. Ошибся в самом выражении: считают именно F(2024) − F(2022), а не F от разности.

💡 Последнее напутствие

Задание 16 — это дословный перенос формулы в код. База — это if, рекуррента — строчка return. Хочешь короче — бери рекурсию с lru_cache, хочешь надёжнее — заполни таблицу циклом.

Не забывай про лимит рекурсии и размер массива — и ответ сойдётся с первого запуска. Удачи на экзамене — Профиматика с тобой!