Question

Задана рекурсивная функция вычисления $F(n)$ для натурального числа $n$:

$$F(n) = \begin{cases} 7, & n < 7 \ 2n + F(n-1), & n \geq 7 \end{cases}$$

Найти значение $F(2024) - F(2022)$.

Accepted Answer

8094

Answer

Идея решения: развернуть рекурсию для двух близких значений и заметить, что большая часть слагаемых сокращается.

Распишем $F(2024)$ через рекурсивное определение:

$$F(2024) = 2 \cdot 2024 + F(2023)$$

$$F(2023) = 2 \cdot 2023 + F(2022)$$

Подставим второе выражение в первое:

$$F(2024) = 2 \cdot 2024 + 2 \cdot 2023 + F(2022) = 4048 + 4046 + F(2022) = 8094 + F(2022)$$

Следовательно:

$$F(2024) - F(2022) = 8094 + F(2022) - F(2022) = 8094$$

Проверим вычислением на Python:

```python
import sys
sys.setrecursionlimit(10**6)

def F(n):
    if n < 7:
        return 7
    else:
        return 2 * n + F(n - 1)

print(F(2024) - F(2022))
```

Альтернативный подход с мемоизацией (заполнение таблицы):

```python
f = {}
for n in range(0, 2050):
    if n < 7:
        f[n] = 7
    else:
        f[n] = 2 * n + f[n - 1]

print(f[2024] - f[2022])
```

Задание №16Алгоритмы и исполнителиЕГЭ по информатике