Question

Функция $F(n)$ определена следующим образом:
- $F(n) = n$, если $n \geq 2025$;
- $F(n) = n + 3 + F(n + 3)$, если $n < 2025$.

Найти значение $F(23) - F(21)$.

Accepted Answer

1338

Answer

Идея решения: вычислить функцию рекурсивно, заметив, что рекурсия идёт с шагом 3, и использовать мемоизацию или прямое вычисление.

**Способ 1: прямое вычисление с рекурсией**

```python
def F(n):
    if n >= 2025:
        return n
    return n + 3 + F(n + 3)

print(F(23) - F(21))
```

Функция $F(23)$ раскрывается как:
$$F(23) = 23 + 3 + F(26) = 26 + F(26)$$
$$F(26) = 26 + 3 + F(29) = 29 + F(29)$$

и так далее, пока не достигнем $n \geq 2025$. Каждый шаг добавляет текущее значение $n$ и переходит к $n + 3$.

Аналогично для $F(21)$:
$$F(21) = 21 + 3 + F(24) = 24 + F(24)$$

Разница между двумя цепочками состоит в том, что $F(23)$ начинается с 23, а $F(21)$ — с 21, и каждая цепочка содержит разные промежуточные значения.

**Способ 2: оптимизированное вычисление с циклом**

Поскольку рекурсия идёт с шагом 3, достаточно хранить три последних вычисленных значения (по остаткам от деления на 3):

```python
f = [0] * 3

# Инициализируем базовые случаи
for n in range(2025, 2028):
    f[n % 3] = n

# Вычисляем в обратном порядке до 21
for n in range(2024, 20, -1):
    f[n % 3] = n + 3 + f[n % 3]

print(f[23 % 3] - f[21 % 3])
```

На каждой итерации перезаписывается элемент массива, соответствующий остатку $n \bmod 3$, что позволяет избежать хранения всех промежуточных значений.

Оба подхода дают ответ **1338**.

![Рисунок](https://ege.sdamgia.ru/formula/svg/04/04be9c01c11c1d7d97d932f584851826.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/e4/e458f6a583d156a92801a749308aea2b.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/af/afd25aebef7794af01272d4a9a10f51a.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/98/98ed83940f55faeeeea4f03c33bdc886.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/3e/3e773d9e6569f81e2bff238a34b4797b.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/2c/2c48b2161aa8c2ecb99ea8ad45a3db92.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/d6/d6229b21378ac4269580eb8e63296372.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/6d/6dc1ae6bd74c0f3c53cfac1db0787c04.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/59/59d39dd059044a096f4c1a133174f899.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/9a/9ad1043a2b6b30d5ca26d2a6f77382da.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/cd/cdc50a7522b20567e32533d89fb946fe.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/53/530773e75eadf9c7ec74baa1e73ce71c.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/01/012eab41ce10c17144e26385d5974136.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/a8/a816f6ca8372be2db56e77861c233250.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/fd/fd1846dc2513bd907755ed9147525509.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/05/051a76023cc907e3f886dce850c1ff02.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/d5/d52c1c6c65f0fadb5ddce9ce3ad6b591.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/c2/c26d946336576383a1ed68e330a7f56d.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/bf/bfda587b3eb71a2a5e1f6dffc4df50c0.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/70/70ec2076841c7a2262de8d5bd7314ffe.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/8c/8c3f84102314b3db40c811d9af5e3d91.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/e5/e5493f90346f1c5c483d5a6983beaf5f.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/13/139f89d7e2040b6413c8ab49b3d55507.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/c0/c090ebcead70df89edca91604d44354b.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/8f/8f8a34a8e936e46b7f150cefa5fee984.svg)

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