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

#69609Задание №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 ( 2022 ) - 2 \cdot F ( 2021 ) - F ( 2020 ) ?$

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

12271520

Пояснение

Решение:

Значения $F(n)$ при $n$ около 2000 астрономически велики, поэтому выражение нужно упростить символьно, последовательно раскрывая соотношение $F(n) = n(n - 1) + F(n - 1) + F(n - 2)$ .

Шаг 1. Раскроем $F(2024) = 2024 \cdot 2023 + F(2023) + F(2022)$ и подставим в исходное выражение — слагаемые $F(2022)$ сократятся:

$F(2024) - F(2022) - 2F(2021) - F(2020) = 2024 \cdot 2023 + F(2023) - 2F(2021) - F(2020).$

Шаг 2. Раскроем $F(2023) = 2023 \cdot 2022 + F(2022) + F(2021)$ :

$= 2024 \cdot 2023 + 2023 \cdot 2022 + F(2022) - F(2021) - F(2020).$

Шаг 3. Раскроем $F(2022) = 2022 \cdot 2021 + F(2021) + F(2020)$ — оставшиеся значения функции сокращаются полностью:

$= 2024 \cdot 2023 + 2023 \cdot 2022 + 2022 \cdot 2021.$

Остаётся посчитать три произведения: $2024 \cdot 2023 = 4094552$ , $2023 \cdot 2022 = 4090506$ , $2022 \cdot 2021 = 4086462$ .

Их сумма: $4094552 + 4090506 + 4086462 = 12271520$ .

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

print(F[2024] - F[2022] - 2 * F[2021] - F[2020])   # 12271520
print(2024 * 2023 + 2023 * 2022 + 2022 * 2021)     # 12271520

Ответ: 12271520