Многие школьники боятся задания №16 — «там же рекурсия!», «это же факториалы!», «а вдруг зависнет?».
Но на самом деле — это одна из самых предсказуемых задач в ЕГЭ. И если вы знаете три ключевых подхода, описанных в статье, то решите её быстрее, чем найдёте калькулятор.
Сегодня разберём все типы задач №16 из реальных вариантов, пошагово, с акцентом на:
- рекурсию,
- итерацию (циклы),
- и главное — кэширование (да, это то, что спасает от переполнения стека!).
Поехали!
🧠 Общая идея задания 16
Дано рекуррентное определение функции F(n) (иногда ещё G(n)).
Нужно вычислить значение выражения, например:
(F(2024) – 3·F(2023)) // F(2022)
Или найти максимальное n, при котором F(n) < 300.
Или определить, сколько раз результат — полный квадрат.
Главная проблема:
- Если вызывать рекурсию «в лоб» — Python упадёт из-за глубины стека.
- Но есть три способа обойти это — и все они в нашей статье!
✅ Тип 1: Факториалоподобная функция
Условие:
Подход 1: Простая рекурсия → НЕ РАБОТАЕТ!
Что делает программа?
- При вызове F(2024) она пытается вызвать F(2023), который вызывает F(2022), и так далее — до F(1).
- Это создаёт цепочку из 2024 вложенных вызовов.
- Python по умолчанию позволяет только ~1000 уровней рекурсии → RecursionError.
❌ Вывод: такой код не пройдёт даже на компьютере, не говоря об экзамене.
🔸 Подход 2: Увеличение лимита рекурсии
Что делает программа?
- setrecursionlimit(10000) увеличивает максимальную глубину рекурсии до 10 000.
- Теперь F(2024) не упадёт, но…
- Каждый вызов всё равно ждёт завершения предыдущего, и ничего не запоминается.
- Если бы нам нужно было вызвать F(2023) отдельно — он пересчитался бы заново.
⚠️ Проблема: медленно, расточительно, ненадёжно.
🔸 Подход 3: Кэширование через @lru_cache
Что делает программа?
- Декоратор @lru_cache(None) автоматически сохраняет результат каждого вызова F(k) в специальной таблице.
- При первом вызове F(2024):Вычисляются F(2023), F(2022), ..., F(1) — и все они записываются в кэш.
- При последующих вызовах (например, F(2023) в выражении) — значение берётся из кэша мгновенно, без пересчёта.
- Это снижает сложность с экспоненциальной до линейной.
✅ Результат: выражение вычисляется за доли секунды.
🔸 Подход 4: Итерация (лучший!)
Что делает программа?
- Создаёт массив f длиной 2100 (хватит для n=2024).
- Заполняет его последовательно: сначала f[1], потом f[2], ..., до f[2024].
- Каждое значение вычисляется один раз, без рекурсии.
- В конце подставляет готовые значения в формулу.
✅ Преимущества:
- Нет риска переполнения стека.
- Максимально быстро.
- Понятно даже новичку.
✅ Ответ: 4092870
💡 Вывод: для больших n — всегда используйте итерацию или кэширование.
✅ Тип 2: Две взаимные функции F(n) и G(n)
🔸 Что делает программа с кэшированием?
Пошагово:
- Вызывается F(47995) → вызывает G(47994).
- G(47994) проверяет: 47994 > 9 → вызывает G(47992) + 1.
- G(47992) → G(47990) + 1 → и так далее, пока не дойдёт до G(8) или G(9).
- Без кэширования каждое чётное число между 10 и 47994 считалось бы много раз (например, G(100) может быть вызван из G(102), G(104), и т.д.).
- С кэшированием — каждое значение G(k) сохраняется после первого вычисления.
- В итоге программа делает ровно ~24 000 вызовов (47994 / 2), а не миллионы.
✅ Ответ: 23997
💡 Почему кэширование критично?
Потому что G(n) уменьшается на 2, и одни и те же значения встречаются многократно при разных путях. Без кэша — экспоненциальный взрыв.
✅ Тип 3: Условная рекурсия с делением на 3
🔸 Что делает программа?
Пошагово:
- Перебираем n от 1 до 10000.
- Для каждого n вызываем F(n).
- Если n не делится на 3 → сразу возвращаем n³ – 26 (это быстро).
- Если делится → рекурсивно вызываем F(n//3).
- Например, при n=81:F(81) = F(27) + 324
F(27) = F(9) + 108
F(9) = F(3) + 36 = 1 + 36 = 37
Итого: F(81) = 37 + 108 + 324 = 469 → больше 300 → не подходит. - Программа запоминает все промежуточные значения (F(3), F(9), F(27)), поэтому при n=243 они уже не пересчитываются.
✅ Ответ: 6
✅ Тип 4: Поиск параметра X в рекуррентной формуле
🔸 Что делает программа?
Пошагово:
- Перебираем возможные значения X (от -100 до 1000).
- Для каждого X создаём массив f.
- Заполняем базу: для n ≥ 3000 → f[n] = n.
- Затем в обратном порядке (от 2999 вниз до 2984) вычисляем:f[2999] = 2999 + X + f[3001]
f[2998] = 2998 + X + f[3000]
...
f[2984] = 2984 + X + f[2986] - После заполнения проверяем: f[2984] - f[2988] == 5916?
- Как только условие выполнено — выводим X и завершаем.
✅ Ответ: 147
💡 Почему не рекурсия? Потому что мы не знаем X заранее — нужно пробовать много значений. Рекурсия была бы слишком медленной.
✅ Тип 5: Сколько раз F(n) — полный квадрат?
🔸 Что делает программа?
Пошагово:
- Для каждого n от 1 до 100:Вычисляем F(n) = G(n - 1).
Например, n=1 → F(1)=G(0)=0 → 0 — полный квадрат (0²).
n=2 → F(2)=G(1)=1 → 1=1² → да.
n=10 → F(10)=G(9)=9 → 9=3² → да.
n=11 → F(11)=G(10)=G(8)+1=8+1=9 → снова 9 → да. - Проверка квадрата:int(val ** 0.5) — целая часть корня.
Если root * root == val → значит, val — точный квадрат. - Кэширование гарантирует, что G(99), G(97) и т.д. считаются только один раз.
✅ Ответ: 9
🎯 Главный вывод: как решать задание 16?
🔥 Золотое правило:
Никогда не пишите "голую" рекурсию на ЕГЭ. Всегда добавляйте @lru_cache или переходите к циклу.
Подпишитесь на мой канал и научитесь решать все задания ЕГЭ по информатике!
Удачи на ЕГЭ! Вы — будущие программисты! 💻✨
Записаться ко мне на занятия можно тут https://vk.com/nebolsink