Вычисление рекуррентных выражений · 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), ес…
Рекурсия
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = 2 при n = 2;
F(n)=n⋅(n−1)+F(n−1)−F(n−2), если n > 2.
Чему равно значение выражения F(2024)+F(2020)−F(2019)?
Правильный ответ
4102638
Пояснение
Решение:
Вычислять F(2024) целиком не нужно — выражение сворачивается, потому что рекуррентное соотношение связывает три подряд идущих значения.
Запишем правило при n=2021: F(2021)=2021⋅2020+F(2020)−F(2019), откуда F(2020)−F(2019)=F(2021)−2021⋅2020. Значит искомое выражение равно F(2024)+F(2021)−2021⋅2020.
Теперь раскроем F(2024). При n=2024: F(2024)=2024⋅2023+F(2023)−F(2022), а при n=2023: F(2023)=2023⋅2022+F(2022)−F(2021), то есть F(2023)−F(2022)=2023⋅2022−F(2021). Поэтому F(2024)=2024⋅2023+2023⋅2022−F(2021).
Слагаемые с F(2021) взаимно уничтожаются:
F(2024)+F(2020)−F(2019)=2024⋅2023+2023⋅2022−2021⋅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