Задача
Дано:
- F(1)=1 при n <= 1
- F(n)=n+F(n−1) при n>1
- n - натуральное число
Найти: F(2023)−F(2020)
Аналитическое решение. Разбор
Принцип: Поиск закономерности
Раскроем рекурсию:
F(n)=n+F(n−1)
F(n)=n+(n−1)+F(n−2)
F(n)=n+(n−1)+(n−2)+F(n−3)
...
F(n)=n+(n−1)+(n−2)+...+2+F(1)
F(n)=n+(n−1)+(n−2)+...+2+1
Это сумма первых n натуральных чисел:
\(F(n) = \frac{n \cdot (n+1)}{2}\)
Проверка:
-
F(1)=1⋅2 / 2 = 1 ✓
-
F(2)=2⋅3 / 2 = 3 ✓
-
F(3)=3⋅4 / 2 = 6 ✓
Вычисление разности:
F(2023)−F(2020)=2023⋅2024 / 2 − 2020⋅2021/ 2 = 6066