Теория и практика по заданию №16 ЕГЭ 2025 по информатике. Рекурсивные алгоритмы (задания и ответы)

Теория и практика по заданию №16 ЕГЭ 2025 по информатике. Рекурсивные алгоритмы (задания и ответы) ЕГЭ 2025. В задании 16 нужно вычислить значение функции, заданной рекуррентным выражением. В этом выражении формула для вычисления следующего элемента последовательности зависит от некоторых условий, которым должен соответствовать аргумент функции.

Скачать теорию и практику ОГЭ: Скачать

В задании 16 требуется вычислить значение функции, заданной рекуррентным выражением. В этом выражении формула для вычисления следующего элемента последовательности зависит от некоторых условий, которым должен удовлетворять аргумент функции.

Демоверсия-2024:
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n при n > 2024;
F(n) = n × F(n + 1), если n ≤ 2024.
Чему равно значение выражения F(2022) / F(2024)?

Запишите подряд без пробелов и разделителей все числа, которые будут выведены на экран при выполнении вызова F(5). Числа должны быть записаны в том же порядке, в котором они выводятся на экран. Можно заметить, что задания достаточно похожи, хоть запись выражения и представлена в разных формах. То есть от сдающего требуют проанализировать рекуррентное выражение (рекурсивную функцию) и найти его значение при определенных параметрах. Также можно сказать, что задание в текущем его виде предполагает большую математическую строгость. Так как, например, вычисление факториала для 2022 достаточно сложная задача даже для компьютера (операции с длинными числами выполняются тем дольше, чем больше их длина).

Поэтому можно сделать вывод, что ФИПИ хочет, чтобы подобные задания решались аналитически. Что ж, желание ФИПИ оставим ФИПИ. И разберемся с наиболее популярными методами решения таких заданий.

Примеры решения заданий
Пример ручного решения задачи из демоверсии-2024 Заметим, что с каждым шагом рекурсии значение параметра увеличивается. Поэтому начнем
F(2022) / F(2024) = 2022⸱F(2023) / F(2024) = 2022⸱2023⸱F(2024) / F(2024)

На втором шаге в числителе и знаменателе заметим вызов F(2024), которые можно сократить по правилам математики.

Следовательно, F(2022) / F(2024) = 2022⸱F(2023) / F(2024) = 2022⸱2023⸱F(2024) / F(2024) = 2022⸱2023
Ответ: 4090506

Пример ручного решения из демоверсии-2020
При вызове F(5) алгоритм сначала выведет значение 5, после чего выполнит вызов F(5 // 2) = F(2). Для F(2) выведет 2 и передаст управление вверх (продолжит выполнять F(5)). Выполнится вызов F(4) – будет выведено 4 и вызвана функция F(4 // 2) = F(2), которая выведет 2 и передаст управление обратно F(4). Вызывается F(3), в ходе выполнения которой печатается 3 и вызывается F(3//2) = F(1). Печатается 1 и вызывается F(3-1) = F(2) – печатается 2 и управление передается на уровень выше, после чего завершается выполнение F(3), далее F(4) и F(5). Также данное рассуждение можно представить в виде изображения
Ответ: 5242312

Пример программного решения из демоверсии-2020 Просто перепишем код из задания и запустим его.
def F(n):
print(n, end=»)
if n >= 3:
F(n // 2)
F(n — 1)
print(F(5))
>> 5242312

Как можно заметить, ничего сложного. Однако, могут быть постановки, где придется подумать больше. Таковые были и на экзамене. Поэтому рассмотрим методы детальнее и попробуем максимально обезопасить себя от ловушек на экзамене. Также становится понятно, почему ФИПИ ушел от постановки задачи в виде программы – при такой постановке задача сдающего сводится к переписыванию кода и его запуску. Однако, существует ряд задач, которые при подобной предполагают либо существенное изменение кода, либо вообще аналитическое решение (из-за невозможности в приемлемое время ответить на вопрос задачи). Аналитический подход В первую очередь необходимо ввести несколько определений. Выход из рекурсии – определение значения рекурсивной функции (рекуррентного выражения) без повторного обращения к этой самой функции. В задании из демоверсии-2024 это было выражение F(n) = n.

Глубина рекурсии – максимальное количество вычисляемых в определенный момент времени значений функции или максимальное количество вложенных вызовов рекурсивной функции. Так, например, при вызове F(2022) из условия демо-2024 нужно было вычислить F(2023) для этого вычислить F(2024), значение которой уже определялось без следующего шага рекурсии. Таким образом глубина рекурсии была 3 (пока не определилось значение F(2024), нельзя было определить значение F(2023), а без него нельзя было определить значение F(2022)). Шаг рекурсии (рекурсивный вызов) – вложенный вызов функцией самой себя. Так запись F(n) = n ⸱ F(n+1) осуществляет шаг рекурсии. Принято считать, что рекурсия «шагает» вглубь. Далее мы ответим на вопрос почему.

Вам будет интересно:

Практика по заданию №12 ЕГЭ 2025 по русскому языку. Правописание личных окончаний глаголов и суффиксов причастий (задания и ответы)

Поделиться:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *