ЕГЭ Задание 16
Рекурсивные алгоритмы
Штана Альберт Игоревич
Типы заданий № 16
В этой статье будет разобрано задание 16.
Рассмотрим типовые задачи из шестнадцатого задания ЕГЭ по информатике.
Данное задание относится к повышенному уровню сложности.
Время выполнения задания ≈ 5 минут.
Данный тип задач проверяет умение вычислять рекуррентные выражения.
В коде Python мы использовали декоратор функции. Подробнее о декораторах в статье: Декораторы.
Задача 1
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = n + F(n − 1), если n – чётно,
F(n) = F(n–1) * n + F(n–2) * (n – 1), при n > 2 и при этом n – нечётно. \
Чему равно значение функции F(12)? В ответе запишите только натуральное число.
Решение:
Данный тип задач можно анализировать и решать аналитически, но мы будем рассматривать только решение с помощью Python. Подразумевается что решать такую задачу на самом экзамене учащийся будет с помощью программирования за пяти минут.
Решение Python
# Функция, которая вызывает сама себя
def f(n): # Названия функций в Python принято писать с маленькой буквы
if n == 1:
return 1
if n % 2 == 0:
return n + f(n - 1)
if n > 2 and n % 2 != 0:
return f(n - 1) * n + f(n - 2) * (n - 1)
# Основная часть программы
print(f(12))
Ответ: 568907
Задача 2
Алгоритм вычисления значения функций F(n) и G(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 0, если n <= 2,
F(n) = G(n - 2), если n > 2
G(n) = 0, n <= 1,
G(n) = F(n - 1) + n, если n > 1
Чему равно значение функции F(8)? В ответе запишите только натуральное число.
Решение:
Решение Python
# Функции вызывающие друг друга
def f(n):
if n <= 2:
return 0
if n > 2:
return G(n - 2)
def G(n):
if n <= 1:
return 0
if n > 1:
return f(n - 1) + n
# Запуск
print(f(8))
Ответ: 9
Задача 3
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 2, если n = 1,
F(n) = 2 · F(n – 1), если n > 1.
Чему равно значение выражения
Решение:
Решение Python
from functools import lru_cache
@lru_cache(None)
def f(n):
if n == 1:
return 2
if n > 1:
return 2 * f(n - 1)
for i in range(2, 1900):
f(i)
print(int(f(1900) / 2 ** 1890))
В данной и подобных задачах используем кэширование с помощью декоратора функции @lru_cache из встроенного пакета functools. В задаче функция вызывает сама себя на значение n-1 и т.д. За счёт этого происходят длинные вычисления для каждого числа n. Если n будет большим числом, то без кэширования(сохранения вычисленных результатов) мы не сможем получить результат вызова функции с большим числом n. Используем декоратор @lru_cache для рекурсивной функции, затем пробегаемся в цикле по значениям n в возрастающем порядке, и для каждого значения сохраняем в кэше результат функции. Таким образом, вычисляя очередное значение, интерпретатор python будет опираться на уже готовый результат из кэша, и тем самым цепочка вызовов функции будет меньше.
Ответ: 1024
Задача 4
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n ≤ 2;
F(n) = n * F(n - 2), если n > 2.
Чему равно значение выражение F(3000)/F(2996) ?
Решение:
Решение Python
from functools import lru_cache
@lru_cache(None)
def f(n):
if n <= 2:
return 1
if n > 2:
return n * f(n - 2)
for i in range(2, 3000):
f(i)
print(int(f(3000) / f(2996)))
Ответ: 8994000
Задача 5
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = 2 при n = 2;
F(n) = n * (n - 1) + F(n - 1) + F(n - 2), если n > 2.
Чему равно значение функции F(2023) - F(2021) - 2 * F(2020) - F(2019)?
Решение:
Решение Python
from functools import lru_cache
@lru_cache(None)
def f(n):
if n == 1:
return 1
if n == 2:
return 2
if n > 2:
return n * (n - 1) + f(n - 1) + f(n - 2)
for i in range(2, 2023):
f(i)
print(int(f(2023) - f(2021) - 2 * f(2020) - f(2019)))
Ответ: 12259388
Задача 6
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n при n ≥ 2025;
F(n) = n + F(n + 2), если n < 2025.
Чему равно значение выражения F(2020) - F(2023)?
Решение:
Решение Python
from functools import lru_cache
@lru_cache(None)
def f(n):
if n >= 2025:
return n
if n < 2025:
return n + f(n + 2)
for i in range(2025, 0, -1):
f(i)
print(f(2020) - f(2023))
Здесь мы видим что функция запускается с достаточно большими числами n, поэтому решаем с помощью декоратора функции @lru_cache. Функция возрастающая, поэтому запускаем функцию в цикле в начале с большими числами, а потом числа убывают (на это указывает третий параметр: шаг -1) функции range.
Ответ: 4044
Задача 7
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 2 * n * n * n + 1, при n > 25
F(n) = F(n + 2) + 2 * F(n + 3), при n ≤ 25
Определите количество натуральных значений n из отрезка [1; 1000], для которых значение F(n) кратно 11.
Решение:
Решение Python
def f(n):
if n > 25:
return 2 * n * n * n + 1
if n <= 25:
return f(n + 2) + 2 * f(n + 3)
k = 0
for i in range(1, 1001):
if f(i) % 11 == 0:
k += 1
print(k)
В начале формируем функцию f. Затем перебираем числа из диапазона от 1 до 1000. Каждое число подставляем в функцию f. Если значение функции f делится на 11, то мы зачитываем такое значение i.
Ответ: 91
Задача 8
Определите сколько символов * выведет эта функция при вызове f(35):
def f(n):
print("*")
if n >= 1:
print("*")
f(n - 1)
f(n - 2)
print("*")
Решение:
Решение Python
def f(n):
global s
s += 1
if n >= 1:
s += 1
f(n - 1)
f(n - 2)
s += 1
s = 0
f(35)
print(s)
Внутри функции ссылаемся на глобальную переменную s через оператор global, которая будет подсчитывать количество напечатанных звёздочек. За счёт оператора global переменную s интерпретатору видно при любом вызове функции, и при каждом вызове функции она будет одна и та же. Вместо печати звёздочек пишем конструкцию s += 1, чтобы посчитать. В основной части программы перед первым запуском функции переменной s присваиваем 0. Программа может медленно работать из-за большой глубины рекурсии, но через минуту выведет ответ.
Ответ: 96631265
Задача 9 (Демоверсия ЕГЭ 2024)
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n при n > 2024;
F(n) = n × F(n + 1), если n ≤ 2024.
Чему равно значение выражения F(2022) / F(2024)?
Решение:
Решение Python
from functools import lru_cache
@lru_cache(None)
def f(n):
if n > 2024:
return n
return n * f(n + 1)
print(int(f(2022) / f(2024)))
Чтобы уменьшить цепочку вызовов функции, используется декоратор @lru_cache из встроенного модуля functools. Если его не использовать, то получим ошибку: RecursionError: maximum recursion depth exceeded in comparison. Функцию пишем с двумя условиями(как по условию задачи) и что функция в одном из случаев вызывает сама себя. Не забываем декорировать её(сразу перед её определением) как @lru_cache(None). Опять же достаточно прописать одно условие где n > 2024, второе указать как инструкцию return, потому что рассматриваются все возможные значения n только с обратным знаком(тогда нет смысла прописывать новое условие можно просто записать return).
Ответ: 4090506
Задача 10 (Демоверсия ЕГЭ 2025)
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = (n – 1)× F(n − 1), если n > 1.
Чему равно значение выражения (F(2024) + 2 × F(2023)) / F(2022)?
Решение:
Решение Python
from functools import lru_cache
@lru_cache(None)
def f(n):
if n == 1:
return 1
return (n - 1) * f(n - 1)
for i in range(1, 2024):
f(i)
print(int((f(2024) + 2 * f(2023)) / f(2022)))
Чтобы уменьшить цепочку вызовов функции, используется декоратор @lru_cache из встроенного модуля functools. Если его не использовать, то получим ошибку: RecursionError: maximum recursion depth exceeded in comparison. Поэтому вначале напишем from functools import lru_cache. Функцию пишем с двумя условиями(как по условию задачи) и что функция в одном из случаев вызывает сама себя. Не забываем декорировать её(сразу перед её определением) как @lru_cache(None). Опять же достаточно прописать одно условие где n == 1, второе указать как инструкцию return, потому что рассматриваются все возможные значения n. Пробегаемся в цикле по значениям n в возрастающем порядке, и для каждого значения сохраняем результаты функции. В конце в функции print делаем вызов согласно условию из выражения задачи и получаем ответ.
Аналитическое решение задачи:
Начнём расписывать выражение с функциями(p.s. Необходимо упростить выражение делая вызовы функций, которые больше чем знаменатель): (F(2024) + 2 * F(2023)) / F(2022)
Получается: (F(2024) + 2 * F(2023)) / F(2022) = (2023 * F(2023) + 2 * F(2023)) / F(2022) = (2023 * 2022 * F(2022) + 2 * 2022 * F(2022)) / F(2022) = 2023 * 2022 + 2 * 2022 = 4090506 + 4044 = 4094550
Ответ: 4094550
Задача 11 (Демоверсия ЕГЭ 2026)
Алгоритм вычисления значения функции F(n) и G(n), где n – целое число, задан следующими соотношениями:
F(n) = 2 × (G(n-3)+8);
G(n) = 2 × n, если n < 10;
G(n) = G(n-2) + 1, если n ≥ 10.
Чему равно значение выражения F(15548)?
Решение:
Решение Python
from functools import lru_cache
@lru_cache(None)
def g(n):
if n >= 10:
return g(n - 2) + 1
return 2 * n
@lru_cache(None)
def f(n):
return 2 * (g(n - 3) + 8)
for i in range(15548):
f(i)
print(int(f(15548)))
Чтобы уменьшить цепочку вызовов функции, используется декоратор @lru_cache из встроенного модуля functools. Если его не использовать, то получим ошибку: RecursionError: maximum recursion depth exceeded in comparison. Поэтому вначале напишем from functools import lru_cache. Функции пишем с условиями(как по условию задачи) и что функция в одном из случаев вызывает сама себя. Не забываем декорировать её(сразу перед её определением) как @lru_cache(None). Опять же достаточно прописать одно условие где n >= 10, второе указать как инструкцию return, потому что рассматриваются все возможные значения n. Пробегаемся в цикле по значениям n в возрастающем порядке, и для каждого значения сохраняем результаты функции. В конце в функции print делаем вызов согласно условию из выражения задачи и получаем ответ.
Ответ: 15588
Попробуйте сами запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.