Базовый (1 балл)
Время: 2-3 мин
Python def
@lru_cache(None)
sys.setrecursionlimit
Все задачи №{ topic_num } в каталоге
Задание №16. Вычисление значений рекурсивных функций
Тема: Рекуррентные соотношения, снятие лимита стека и мемоизация @lru_cache
Вычисление значения функции F(N) по рекуррентным формулам. Требует мемоизации `@lru_cache(None)` и увеличения лимита рекурсии `sys.setrecursionlimit(50000)`.
1. Шаблон для Задания №16:
import sys
from functools import lru_cache
sys.setrecursionlimit(50000)
@lru_cache(None)
def F(n):
if n == 1: return 1
if n % 2 == 0: return n + F(n - 1)
return 2 * F(n - 2)Разновидности и прототипы задания на экзамене
Тип 1: Прямое вычисление F(2026)
Функция с lru_cache.
Тип 2: Вычисление разности или отношения F(2026) / F(2023)
Сокращение множителей.
Боевой шаблон решения на Python
Запустить код в онлайн-песочнице# === Боевой шаблон Задания №16 на Python ===
import sys
from functools import lru_cache
# 1. Снимаем лимит глубины стека:
sys.setrecursionlimit(50000)
# 2. Обязательно кэшируем результаты:
@lru_cache(None)
def F(n):
if n <= 1:
return 1
if n % 2 == 0:
return 2 * n + F(n - 1)
else:
return 3 * n + F(n - 2)
# Прогреваем кэш снизу вверх для больших N:
for i in range(1, 2027):
F(i)
print("Ответ F(2026):", F(2026))Анти-примеры (Типичные ошибки vs Как делать правильно)
Как делать НЕ надо:
Ошибка: Забыть @lru_cache(None) при вычислении F(n-1) + F(n-2)
Программа зависнет на 10 минут из-за экспоненциального количества вызовов!Как делать ПРАВИЛЬНО:
Правильно: ВСЕГДА вешать @lru_cache(None) на рекурсивную функцию.
ГРОБ
ГРОБ №16: Числа огромного порядка (F(2026) / F(2023))
Значение F(2026) содержит тысячи знаков и не влезает в память.
Как обойти ловушку: Распишите формулу на бумаге: в дроби $F(2026) / F(2023)$ почти все множители взаимно сокращаются!
Лайфхаки и подводные камни на экзамене:
- Если число n очень большое (например, 5000+), вызовите функцию в цикле `for i in range(1, n+1): F(i)` для заполнения кэша без падения стека.