Продолжаем разбирать демоверсию ЕГЭ по информатике 2022 года. Сегодня разберём задание №16, посвящённое вычислению рекуррентных выражений, то есть заданию на рекурсию и рекурсивные функции.
Рекурсия
Вкратце, рекурсия в программировании — это использование функции, которая в процессе своего выполнения ссылается сама на себя. Рекурсивная функция вызывает саму себя.
Условие задачи
Алгоритм вычисления значения функции f(n), где n — натуральное число, задан следующими соотношениями:
- f(n) = 1, при n = 1
- f(n) = n + f(n-1), если n > 1 и n — чётное
- f(n) = 2 * f(n-2), если n > 1 и n — нечётное
Необходимо вычислить значение функции f(26). В предыдущие годы значения функции были меньше, позволяя решить задачу вручную. Сейчас же, учитывая увеличенные значения, необходимо программирование.
Решение задачи
Для решения создадим рекурсивную функцию на Python:
def f(n):
if n == 1:
return 1
elif n % 2 == 0: # n чётное
return n + f(n - 1)
else: # n нечётное
return 2 * f(n - 2)
print(f(26))Код начинается с ключевого слова def, далее следует имя функции f, принимающей один параметр n.
- Если n равно 1, функция возвращает 1.
- Если n больше 1 и чётное (n % 2 == 0), функция возвращает n + f(n — 1).
- В противном случае (n нечётное), функция возвращает 2 * f(n — 2).
Функция вызывается с аргументом 26: print(f(26)). Это выведет результат на экран.
Результат
Запустив код, получаем результат: 4122. Это правильный ответ на задание.