Задание №16 — Рекурсия

#69586Задание №16ФИПИ

Рекурсия

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = 2 при n = 2;
$F ( n ) = n \cdot ( n - 1 ) + F ( n - 1 ) - F ( n - 2 ) ,$ если n > 2.
Чему равно значение выражения $F ( 2024 ) + F ( 2020 ) - F ( 2019 ) ?$

Правильный ответ

4102638

Пояснение

Решение:

Вычислять $F(2024)$ целиком не нужно — выражение сворачивается, потому что рекуррентное соотношение связывает три подряд идущих значения.

Запишем правило при $n = 2021$ : $F(2021) = 2021 \cdot 2020 + F(2020) - F(2019)$ , откуда $F(2020) - F(2019) = F(2021) - 2021 \cdot 2020$ . Значит искомое выражение равно $F(2024) + F(2021) - 2021 \cdot 2020$ .

Теперь раскроем $F(2024)$ . При $n = 2024$ : $F(2024) = 2024 \cdot 2023 + F(2023) - F(2022)$ , а при $n = 2023$ : $F(2023) = 2023 \cdot 2022 + F(2022) - F(2021)$ , то есть $F(2023) - F(2022) = 2023 \cdot 2022 - F(2021)$ . Поэтому $F(2024) = 2024 \cdot 2023 + 2023 \cdot 2022 - F(2021)$ .

Слагаемые с $F(2021)$ взаимно уничтожаются:

$F(2024) + F(2020) - F(2019) = 2024 \cdot 2023 + 2023 \cdot 2022 - 2021 \cdot 2020 = 4094552 + 4090506 - 4082420 = 4102638.$

Тот же ответ даёт программа. Рекурсию «в лоб» здесь применять нельзя (каждый вызов порождает два новых, время растёт экспоненциально) — заполняем таблицу значений по возрастанию $n$ :

F = [0] * 2025
F[1], F[2] = 1, 2
for n in range(3, 2025):
    F[n] = n * (n - 1) + F[n - 1] - F[n - 2]

print(F[2024] + F[2020] - F[2019])   # 4102638

Ответ: 4102638