Question

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

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

Найти значение $F(2023) - F(2021)$.

Accepted Answer

4041

Answer

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

Применим рекурсивное определение:

$$F(2023) = 2023 - 2 + F(2022) = 2021 + F(2022)$$

$$F(2022) = 2022 - 2 + F(2021) = 2020 + F(2021)$$

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

$$F(2023) = 2021 + 2020 + F(2021) = 4041 + F(2021)$$

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

$$F(2023) - F(2021) = 4041 + F(2021) - F(2021) = 4041$$

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

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

def F(n):
    if n == 1:
        return 1
    else:
        return n - 2 + F(n - 1)

print(F(2023) - F(2021))
```

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