Задание повышенного уровня сложности, на вычисление рекуррентных выражений, предполагает время выполнения около 5 минут.
Алгоритм и проблема рекурсии
Рассматривается алгоритм вычисления значения функции f(n), где n – натуральное число, определяемой следующими соотношениями:
- f(n) = 1, при n = 1
- f(n) = n * f(n-1), при n > 1
Необходимо найти значение выражения f(2023) / f(2020).
Прямое применение рекурсии для вычисления f(2023) приведёт к ошибке из-за слишком глубокой рекурсии и переполнения стека. Проблема заключается в огромных числах, получаемых в процессе вычислений.
Решение через факториал
Рассмотрим вычисление f(5):
f(5) = 5 * f(4) = 5 * 4 * f(3) = 5 * 4 * 3 * f(2) = 5 * 4 * 3 * 2 * f(1) = 5 * 4 * 3 * 2 * 1 = 5!
Функция f(n) вычисляет факториал числа n. Для решения задачи можно использовать вычисление факториала с помощью языка программирования.
Решение на Python
Используем Python и модуль math с функцией factorial().
import math
print(math.factorial(2023) / math.factorial(2020))Программа быстро вычисляет результат. В ответе необходимо указать целое значение, отбрасывая дробную часть.
Итеративное решение
Если непосредственное определение факториала не очевидно, задачу можно решить итеративно, без использования рекурсии. Итеративный подход эффективнее рекурсивного, особенно для больших значений n.
Создадим список f длиной 2100, заполненный единицами:
f = [1] * 2100Переберём элементы списка, вычисляя значения f(n) по формуле f(n) = n * f(n-1):
for n in range(2, 2100):
f[n] = n * f[n-1]
print(f[2023] / f[2020])Этот код также выдает правильный ответ и работает значительно быстрее, чем рекурсивный подход.
Задание 16 демоверсии ЕГЭ по информатике 2023 года эффективно решается вычислением факториала или итеративным подходом. Использование рекурсии неэффективно и может привести к ошибкам. Итеративный подход предпочтительнее из-за скорости и устойчивости к переполнению стека.