Задание 16 ЕГЭ информатика

1. Введение

В задании №16 функция задаётся рекурсивно: значение F(n) вычисляется через значение той же функции при другом аргументе. Иногда в условии встречаются две связанные функции F(n) и G(n).

Главная задача — не вычислить гигантские значения вслепую, а увидеть зависимость между соседними аргументами и выбрать подходящий способ.

Задание проверяет умение:

находить базовый случай, на котором рекурсия останавливается;
понимать направление зависимости: n - 1, n - k, n + 1 или n + k;
раскрывать несколько шагов рекурсии и сокращать общий множитель;
переводить кусочное определение функции в Python;
соблюдать порядок вычислений и правильно расставлять скобки.

Условие задаёт базу и переходы, а вопрос — итоговое выражение.

Решение вручную особенно выгодно, когда в выражении стоят близкие аргументы: например, F(n), F(n - 1) и F(n - 2). Для длинной или ветвящейся рекурсии надёжнее код.

2. Решение вручную: сокращаем функции

Функции можно сокращать только после того, как все значения выражены через одно и то же базовое значение F(k).

Нельзя просто зачеркнуть разные F(n) как одинаковые числа.

Алгоритм ручного решения

Выберите функцию с наименьшим аргументом в знаменателе или в общем выражении.
Раскройте рекурсию у функций с большими аргументами на один-два шага.
Вынесите общий множитель F(k) за скобки.
Сократите общий множитель и вычислите оставшееся небольшое выражение.

Основная волна 2026: F(n) = (n − 1) · F(n − 1)

Дано:

F(1) = 1

При n > 1:

F(n) = (n - 1) · F(n - 1)

Требуется найти:

(F(17258) + 3 · F(17257)) / F(17256)

Общий множитель F(17256) полностью сокращается.

После сокращения остаётся:

17256 · (17257 + 3)
= 17256 · 17260

Ответ: 297838560

Основная волна 2026, день 1: F(n) = n · F(n − 1)

Нужно найти:

(F(3238) / 2 + F(3237)) / F(3236)

Раскрываем только два соседних значения:

F(3237) = 3237 · F(3236)

F(3238) = 3238 · 3237 · F(3236)

Выносим 3237 · F(3236) и сокращаем F(3236):

3237 · (3238 / 2 + 1)
= 3237 · 1620

Ответ: 5243940

3. Решение кодом

Универсально лучшего способа нет. Выбор зависит от глубины рекурсии, количества повторных вызовов и размера промежуточных чисел.

Способ	Когда удобен	Сильная сторона	Ограничение
`lru_cache` + прогрев	ветвящиеся или длинные рекурсии	не повторяет уже найденные значения	кэш занимает память
`setrecursionlimit`	нужно быстро переписать короткую цепочку	минимум дополнительного кода	глубокий стек может завершить программу аварийно
список	зависимости удобно считать по порядку	нет рекурсии; скорость предсказуема	хранит все значения, включая огромные числа

Рекомендуемый порядок на ЕГЭ:

Сначала проверить, сокращается ли выражение вручную.
Затем использовать lru_cache с прогревом.
setrecursionlimit оставлять для случаев, где глубина умеренная и решение нужно записать максимально быстро.

Сначала правильно записываем print

Внешние скобки задают числитель целиком.

Операторы * и // выполняются раньше +. Поэтому скобки должны повторять структуру математической дроби.

В задачах с целым ответом используем //, чтобы не переводить огромные числа в неточный тип float.

Например, правильно:

print((F(a) + 3 * F(b)) // F(c))

А такая запись:

print(F(a) + 3 * F(b) // F(c))

означает уже другое выражение: на F(c) делится только второе слагаемое.

Способ 1. lru_cache и прогрев — основной

Декоратор lru_cache запоминает уже вычисленные значения.

Но один только lru_cache не отменяет ограничение глубины рекурсии. Поэтому перед print вызываем функцию по порядку: каждый новый вызов опирается на уже готовое значение.

Направление цикла определяется направлением рекурсивной зависимости:

если F(n) зависит от F(n - 1), идём от меньших аргументов к большим;
если F(n) зависит от F(n + 1), начинаем с известной правой границы и идём вниз.

Пример для зависимости F(n) = n · F(n - 1):

from functools import lru_cache


@lru_cache(None)
def F(n):
    if n == 1:
        return 1
    return n * F(n - 1)


for n in range(1, 3239):
    F(n)


print((F(3238) // 2 + F(3237)) // F(3236))

Результат: 5243940

Способ 2. sys.setrecursionlimit — коротко, но рискованно

Правильное имя команды:

sys.setrecursionlimit(...)

Она увеличивает допустимую глубину вызовов, но не ускоряет вычисления и не сохраняет результаты.

Слишком большое значение может привести не к обычной ошибке Python, а к аварийному завершению программы из-за переполнения системного стека.

import sys

sys.setrecursionlimit(10_000)


def F(n):
    if n == 1:
        return 1
    return n * F(n - 1)


print((F(3238) // 2 + F(3237)) // F(3236))

Здесь три значения F вычисляются отдельными цепочками, поэтому часть работы повторяется.

Способ удобен как быстрый черновик, но не как самый надёжный шаблон.

Способ 3. Список — итеративно и без глубокой рекурсии

Список хранит:

F(0), F(1), ..., F(N)

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

F = [0] * 18000
F[1] = 1

for n in range(2, 17259):
    F[n] = (n - 1) * F[n - 1]


print((F[17258] + 3 * F[17257]) // F[17256])

Результат: 297838560

Если формула зависит только от предыдущего значения, список можно оптимизировать: хранить текущее значение и несколько последних нужных результатов.

Это действительно уменьшает расход памяти.

4. Прототипы задач

Прототип 1. Рекурсия идёт к меньшим аргументам

Признак: в формуле встречается:

F(n - 1)
F(n - 2)
F(n - k)

Сначала известны маленькие аргументы, поэтому прогрев идёт от базы к нужному N.

Шаблон цикла:

for n in range(BASE, N + 1):
    F(n)

Если база начинается с 0, начинаем с 0; если с 1 — с 1.

Пример:

from functools import lru_cache


@lru_cache(None)
def F(n):
    if n == 1:
        return 1
    return n * F(n - 1)


for n in range(1, 3239):
    F(n)


print((F(3238) // 2 + F(3237)) // F(3236))

Ответ: 5243940

Прототип 2. Рекурсия идёт к большим аргументам

Учебный пример:

F(n) = n, если n ≥ 1000

F(n) = F(n + 1) + 2, если n < 1000

Найти F(10).

Теперь известная область находится справа. Поэтому начинаем с границы 1000 и идём вниз до 10.

Если пойти от 10 вверх, первый же вызов снова построит длинную рекурсивную цепочку.

from functools import lru_cache


@lru_cache(None)
def F(n):
    if n >= 1000:
        return n
    return F(n + 1) + 2


for n in range(1000, 9, -1):
    F(n)


print(F(10))

От 10 до 1000 — 990 шагов, на каждом прибавляется 2:

F(10) = 1000 + 990 · 2

Ответ: 2980

Прототип 3. Две связанные функции

Дано:

F(n) = F(n - 8) + 1095, при n ≥ 21

F(n) = 10 · (G(n - 7) - 36), при n < 21

G(n) = n // 23 + 33, при n ≥ 22560

G(n) = G(n + 11) - 4, при n < 22560

Найти F(548).

Функция F в базовой области вызывает G, поэтому сначала прогреваем G от 22560 вниз, затем F от малых аргументов вверх.

Порядок подготовки значений соответствует зависимости функций.

from functools import lru_cache


@lru_cache(None)
def G(n):
    if n >= 22560:
        return n // 23 + 33
    return G(n + 11) - 4


@lru_cache(None)
def F(n):
    if n >= 21:
        return F(n - 8) + 1095
    return 10 * (G(n - 7) - 36)


for n in range(22560, -8, -1):
    G(n)

for n in range(0, 549):
    F(n)


print(F(548))

Ответ: 50

Проверка вручную

548 уменьшается на 8 ровно 66 раз и приходит в 20.

Поэтому:

F(548) = F(20) + 66 · 1095

Для G(13) требуется 2050 шагов по +11.

После подстановки:

F(20) = -72220

В итоге:

F(548) = 50