ЕГЭ Информатика 2021: Рекурсия f(26) — решение

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

  • f(n) = 1, при n = 1
  • f(n) = n + f(n-1), если n чётное
  • f(n) = 2 * f(n-2), если n > 1 и n нечётное

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

Решение

Ручное вычисление f(26) затруднительно из-за большого значения аргумента. Например:

  1. f(26) = 26 + f(25) (так как 26 — чётное)
  2. f(25) = 2 * f(23) (так как 25 — нечётное)
    … и так далее.

Программное решение на Python

Эффективнее использовать программу. Приведённый ниже код на Python вычисляет значение функции:

def f(n):
    if n == 1:
        return 1
    elif n % 2 == 0:
        return n + f(n - 1)
    elif n > 1 and n % 2 != 0:
        return 2 * f(n - 2)

print(f(26))  # Вывод: 4122

Код реализует рекурсивную функцию f(n) согласно заданным соотношениям. Вызов f(26) возвращает 4122.

Для эффективного решения задачи 16 ЕГЭ по информатике 2021 года целесообразно использовать программный код. Ручной расчёт при больших значениях аргумента непрактичен и подвержен ошибкам.

Что будем искать? Например,программа