Задание 16 ЕГЭ по информатике: решайте с автопроверкой

Задание 16 о рекурсии. Функция задана через свои значения при меньших аргументах, и нужно найти значение при большом n, разность двух значений или количество значений с заданным свойством.

Решать задачи номера

Как решать программой

Перепишите определение функции в Python почти дословно. Чтобы рекурсия не считала одно и то же много раз, добавьте декоратор @lru_cache(None) из functools: он запоминает уже найденные значения.

Если аргумент большой, рекурсия упрётся в ограничение глубины. Поднимите его через sys.setrecursionlimit или вызывайте функцию по возрастанию аргумента, чтобы кэш заполнялся постепенно. Ещё проще посчитать значения циклом снизу вверх.

Когда спрашивают о разности F(2025) − F(2023), не пытайтесь вычислить каждое значение отдельно, если они огромны: часто проще упростить выражение. Но для экзаменационных размеров Python справляется и напрямую, потому что работает с длинными числами.

Перед запуском на большом аргументе посчитайте программой несколько первых значений и сверьте их с вычислением руками. Ошибка в одном знаке формулы видна уже на третьем значении.

Разбор примера

F(n) = n + 1 при n ≤ 2, F(n) = F(n − 1) + 2 · F(n − 2) − n при n > 2. Чему равно F(5)?

from functools import lru_cache

@lru_cache(None)
def F(n):
    return n + 1 if n <= 2 else F(n - 1) + 2 * F(n - 2) - n

print(F(5))

Программа печатает

9

По шагам: F(1) = 2, F(2) = 3, F(3) = 3 + 4 − 3 = 4, F(4) = 4 + 6 − 4 = 6, F(5) = 6 + 8 − 5 = 9. Такую цепочку полезно выписать руками для малых n: она проверяет, что функция в программе записана верно.

Решить эту задачу

Задачи к заданию 16

  • Значение рекурсивной функцииЛёгкаяРешать
  • Две взаимно рекурсивные функцииСредняяРешать
  • Сколько значений F делится на kСредняяРешать
  • Разность значений при глубокой рекурсииСредняяРешать
  • Сколько разных значений принимает FСредняяРешать
  • Первое значение больше границыСредняяРешать
  • Сумма напечатанных чиселСредняяРешать
  • Функция двух аргументовСредняяРешать
  • Частное значений огромной функцииСредняяРешать
  • Рекурсия с вычитанием суммы цифрСредняяРешать

Бесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).

Вопросы и ответы

Что делать с ошибкой RecursionError?
Вызовите sys.setrecursionlimit(10000) или посчитайте значения циклом от меньших n к большим.
Зачем lru_cache?
Без него функция с двумя рекурсивными вызовами работает экспоненциально долго. С ним каждое значение считается один раз.
Как решать задачи с двумя функциями?
Опишите обе функции, каждая может вызывать другую. Кэш нужен обеим.