Задание 16

Вычисление рекуррентных выражений · 26 заданий

Задание №16
№16
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n × F(n − 1), если n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n × F(n − 1), если n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = 1 при n = 2; F (n) =…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = 1 при n = 2; F (n) =…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = 2 при n = 2; F(n) = n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями: F(n) = 1 при n < 3; F(n) = F(n − 1) +…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n · F (n - 1), если n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n² + F (n - 1), если…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями: F(n) = 1, если n <= 1; F(n) = 3 + F (n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = 2 при n = 2; F(n) = n…
Рекурсия
Задание №16
№16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = n + 2 · F (n - 1), ес…
Рекурсия

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

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

12259388

Пояснение

Решение:

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

При $n = 2023$ : $F(2023) = 2023 \cdot 2022 + F(2022) + F(2021)$ , поэтому $F(2023) - F(2021) = 2023 \cdot 2022 + F(2022)$ .

При $n = 2022$ : $F(2022) = 2022 \cdot 2021 + F(2021) + F(2020)$ , а при $n = 2021$ : $F(2021) = 2021 \cdot 2020 + F(2020) + F(2019)$ . Подставив второе в первое, получаем $F(2022) = 2022 \cdot 2021 + 2021 \cdot 2020 + 2F(2020) + F(2019)$ .

Тогда все неизвестные значения сокращаются:

$F(2023) - F(2021) - 2F(2020) - F(2019) = 2023 \cdot 2022 + 2022 \cdot 2021 + 2021 \cdot 2020 = 4090506 + 4086462 + 4082420 = 12259388.$

Проверка программой (значения растут очень быстро, но в Python целые числа длинные, поэтому переполнения не будет):

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

print(F[2023] - F[2021] - 2 * F[2020] - F[2019])   # 12259388

Ответ: 12259388