Разборы · ЕГЭ, задание 16

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

Что проверяет задание

Функция F(n) задана рекуррентными соотношениями: F(1) = …, F(n) = … через F(n − 1). Нужно вычислить её значение или выражение из нескольких значений при больших n. 1 балл.

Что нужно знать

• Рекурсия прямо «как в условии» при n в несколько тысяч упирается в предел глубины рекурсии: RecursionError.
• Надёжный способ — считать значения циклом от меньших n к большим и хранить их в словаре или списке.
• Второй способ — @lru_cache и «прогрев»: вызывать F(1), F(2), … по порядку. Тогда каждое значение считается из уже сохранённого, и глубина рекурсии не растёт.
• Значения бывают огромными. Делите через //: деление / переводит число в float и падает с ошибкой OverflowError.

Как решать

1. Посмотрите на формулу: иногда выражение упрощается вручную (как в примере ниже).
2. Если нет — посчитайте значения циклом и подставьте в выражение.
3. Если в формуле есть F(n // 2), F(n + 1) или несколько ветвей по чётности, используйте запоминание с прогревом: так не нужно думать, в каком порядке считать значения.

Проверяйте функцию на маленьких n, которые легко посчитать вручную: F(1), F(2), F(3). Если здесь всё совпало, большие значения тоже будут верны.

Пример из демоверсии 2027

F(n) = 1 при n = 1; F(n) = n × F(n − 1) при n > 1. Чему равно (F(3038) + 5 × F(3037)) / F(3036)?

Решение вручную. F(n) = n! — факториал. F(3038) = 3038 · 3037 · F(3036), F(3037) = 3037 · F(3036). Делим: 3038 · 3037 + 5 · 3037 = 3037 · 3043 = 9241591.

Программой:

F = {1: 1}                          # F(1) = 1
for n in range(2, 3039):
    F[n] = n * F[n - 1]             # F(n) = n × F(n − 1)

print((F[3038] + 5 * F[3037]) // F[3036])        # 9241591

Вариант с запоминанием и прогревом — удобен, когда формула сложная (несколько ветвей, F(n − 2), F(n // 2) и т. п.):

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, 3039):            # прогрев: считаем значения по порядку
    F(n)
print((F(3038) + 5 * F(3037)) // F(3036))        # 9241591

Типичные ошибки

• Вызывают F(3038) без прогрева и получают RecursionError.
• Делят через / и получают OverflowError или неточный ответ.
• Путают ветви условия: «n > 1» и «n ≥ 1», чётные и нечётные n.

Потренироваться: задание 16 новые варианты с проверкой ответа