ЕГЭ Информатика 2020: Разбор задачи 11 (рекурсия)

Задание 11 демонстрационного варианта ЕГЭ по информатике 2020 года предполагает анализ рекурсивного алгоритма и определение последовательности вывода чисел.

Рекурсивная функция

Рекурсивная функция — это функция, которая вызывает саму себя. Рассмотрим фрагмент кода на языке Python:

def f(n):
    print(n)
    if n >= 3:
        f(n // 2)
        f(n - 1)

Функция f(n) выводит значение переменной n. Если n больше или равно 3, она рекурсивно вызывает себя дважды: f(n // 2) (целочисленное деление n на 2) и f(n — 1).

Анализ вызова f(5)

Разберем по шагам вызов f(5):

1. Вызывается f(5). Выводится 5.
2. Условие n >= 3 истинно (5 >= 3).
3. Вызывается f(5 // 2), эквивалентно f(2).
4. Вызывается f(5 — 1), эквивалентно f(4).
5. В f(2) условие n >= 3 ложно, выводится 2.
6. В f(4) условие n >= 3 истинно:
   • Вызывается f(4 // 2), эквивалентно f(2). Выводится 2.
   • Вызывается f(4 — 1), эквивалентно f(3).
7. В f(3) условие n >= 3 истинно:
   • Вызывается f(3 // 2), эквивалентно f(1).
   • Вызывается f(3 — 1), эквивалентно f(2). Выводится 2.
8. В f(1) условие n >= 3 ложно, выводится 1.
9. В f(2) условие n >= 3 ложно, выводится 2.

Последовательность вывода

Последовательность вывода чисел при вызове f(5): 5242312.

Порядок вывода

Вывод переменной n происходит перед проверкой условия. Изменение порядка операций повлияло бы на результирующую последовательность.

Правильный ответ на задание 11 — 5242312. Решение основано на понимании рекурсии и порядка выполнения операций.