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

Рекуррентные функции

1 балл ≈ 5 мин уровень П

Задание 16 – функция задана рекуррентно (F(n) через F(n − 1), F(n − 2), иногда две функции F и G). Найти значение выражения, часто с огромными n. 1 балл.

Алгоритм

Перепиши определение в код один в один, с базовыми случаями.
Добавь кэш (lru_cache) – без него рекурсия ветвится экспоненциально.
Если n большое (тысячи) – подними предел рекурсии или считай циклом снизу вверх.
Если выражение вида F(2024)/F(2022) – часто проще упростить вручную.

Шаблон

import sys
from functools import lru_cache
sys.setrecursionlimit(100000)

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

print(F(20))                      # 524288

Для очень больших n (десятки тысяч) надёжнее «прогреть» кэш по возрастанию: for i in range(1, n): F(i) – тогда глубина рекурсии останется маленькой.

Разобранный пример (сокращение). F(1) = 1, F(n) = n · F(n − 1). Найди (F(2024) + F(2023)) / F(2022). F(2024) = 2024 · 2023 · F(2022), F(2023) = 2023 · F(2022). Значит, выражение = 2024 · 2023 + 2023 = 2023 · 2025 = 4 096 575.

Ловушки: деление / даёт дробное число с потерей точности на больших значениях – используй //; пропущенный базовый случай → бесконечная рекурсия; условие «если n < 10» и «если n ≥ 10» – границы проверь буквально.

На экзамене

@lru_cache(None) – первая строка над любой рекурсивной функцией в ЕГЭ.
Ошибка RecursionError – подними sys.setrecursionlimit или прогрей кэш циклом.
Для двух функций F и G кэшируй обе.

Разобранные задания 16 из открытого банка ФИПИ

Пример 1 · код ФИПИ 0E2072

Алгоритм вычисления значения функции F(n), где n $-$ натуральное число, задан следующими соотношениями:

F(n) = 3 при n < 3;

F(n) = n + F(n − 2), если n ≥ 3.

Чему равно значение выражения F(2022) $-$ F(2018)?

Показать ответ и решение

Ответ: 4042

$F (2022) = 2022 + F (2020) = 2022 + 2020 + F (2018)$ .

Разность 4042.

Пример 2 · код ФИПИ 9DAE40

Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.

Бейсик	Python
DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) IF n > 0 THEN G(n - 1) END SUB SUB G(n) PRINT "*" IF n > 1 THEN F(n - 3) END SUB	def F(n): if n > 0: G(n - 1) def G(n): print("*") if n > 1: F(n - 3)
Алгоритмический язык	Паскаль
алг F(цел n) нач если n > 0 то G(n - 1) все кон алг G(цел n) нач вывод "*" если n > 1 то F(n - 3) все кон	procedure F(n: integer); forward; procedure G(n: integer); forward; procedure F(n: integer); begin if n > 0 then G(n - 1); end; procedure G(n: integer); begin writeln('*'); if n > 1 then F(n - 3); end;
Си
void F(int n); void G(int n); void F(int n){ if (n > 0) G(n - 1); } void G(int n){ printf("*"); if (n > 1) F(n - 3); }

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(18)?

Показать ответ и решение

Ответ: 5

F(18)→G(17)*→F(14)→G(13)*→F(10)→G(9)*→F(6)→G(5)*→F(2)→G(1)*. Всего 5 звёздочек.

Пример 3 · код ФИПИ 3E7B68

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 2 при n < 3;

F(n) = F(n − 2) + F(n − 1) – n, если n > 2 и при этом n чётно;

F(n) = F(n − 1) − F(n − 2) + 2 × n, если n > 2 и при этом n нечётно.

Чему равно значение функции F(32)?

Показать ответ и решение

Ответ: 3194

Считаем по возрастанию n (программой): F(1)=F(2)=2, чётные $F (n - 2) + F (n - 1) - n$ , нечётные $F (n - 1) - F (n - 2) + 2 n$ .

F(32)=3194.

Частые вопросы о задании 16

Сколько баллов даёт задание 16 ЕГЭ по информатике?

Максимум – 1 первичный балл. Норма времени на экзамене – около 5 мин. Уровень сложности – П.

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

Как подготовиться к заданию 16?

Прочитайте теорию выше: алгоритм, нужные факты и ловушки. Затем решите подход из 10 заданий с автопроверкой и разбором – первые без регистрации – и вернитесь к ошибкам. В пробниках Сотки номер встречается в полных вариантах ФИПИ с подсчётом баллов.