Разбор номера 16 — ЕГЭ Информатика

📋 Условие

Вычислить значение выражения (f(13766) - 9 * f(13762)) // f(13758), где рекурсивная функция f(n) определена как: если n < 5, то возвращает n; иначе возвращает 2 * n * f(n - 4).

🔍 Подробное решение

Вычислить значение выражения (f(13766) - 9 * f(13762)) // f(13758), где рекурсивная функция f(n) определена как: если n < 5, то возвращает n; иначе возвращает 2 * n * f(n - 4).

Способы решения:

1. Рекурсия без мемоизации — самый медленный
2. Рекурсия с lru_cache
3. Мемоизация через словарь
4. Использование декоратора
5. Использование @cache (Python 3.9+)

```python
from functools import lru_cache

@lru_cache(maxsize=None)
def f(n):
if n < 5:
return n
return 2 * n * f(n - 4)

result = (f(13766) - 9 * f(13762)) // f(13758)
print(result)
```

Альтернативный подход — аналитический:

Заметим, что f(n) растёт как O(n!!) — произведение каждого четвёртого числа. Можно вычислить рекуррентно и подставить.

Ответ: 757543052

📚 Теория

Рекуррентные соотношения. @lru_cache для мемоизации. Всегда // для деления.

🐍 Шаблон Python

Python

import sys
sys.setrecursionlimit(1000000)

from functools import *
@lru_cache(None)  # None меняем на 100 или 500 если не работает

def f(n):
    if n < 5:
        return n
    return 2 * n * f(n - 4)

for i in range(14000):  # число ближайшее вперед к числам в задаче
    f(i)

print((f(13766) - 9 * f(13762)) // f(13758))  # Всегда // (целое деление)

🐍 Альтернативный способ

Способ 2

# Способ 3 — список (самый быстрый)
f = [0] * 14000
for n in range(len(f)):
    if n < 5:
        f[n] = n
    if n >= 5:
        f[n] = 2 * n * f[n - 4]
print((f[13766] - 9*f[13762]) // f[13758])

🔗 Полезные ссылки