2 Краткая информация о задании 16

Краткая информация о задании 16

Задание 16 — про вычисление рекуррентной функции. Дана функция F(n): для маленьких n её значение задано напрямую (база), а для остальных — выражено через соседние значения, например F(n) = n + 2 + F(n − 1). Нужно вычислить какое-то выражение вроде F(2023) − F(2021).

Считать такие функции руками бессмысленно — значения зависят друг от друга по цепочке до самой базы. Python проходит эту цепочку мгновенно.

Проверяемые требования

Вычисление рекуррентных выражений; умение исполнять алгоритм, заданный рекурсивно.

Средний процент выполнения по РФ

Год

% по РФ

2024

56 %

2025

54 %

2026

62,4 %

Проценты — по методическим материалам ФИПИ. Задание повышенного уровня, одно из самых алгоритмизируемых: перенёс формулу в код — получил ответ.

Уровень сложности: повышенный.

Примерное время выполнения: 6 минут.

💡 Важный момент про способ решения

Задание 16 — питоновское. Формула из условия переносится в код почти дословно. Есть два способа: рекурсия с кэшем (lru_cache) — короче и ближе к условию, и таблица (заполняем массив от базы) — надёжнее на больших n. Мы покажем оба.