Question

Исполнитель преобразует число на экране. У исполнителя есть две команды:

1. **Прибавить 1** — увеличивает число на 1.
2. **Умножить на 2** — умножает число на 2.

Программа — это последовательность команд. Сколько существует программ, которые при исходном числе 2 дают результат 29, и при этом траектория вычислений содержит число 14?

Траектория вычислений — последовательность результатов после каждой команды. Например, для программы с кодами команд 1, 2, 1 при исходном числе 7 траектория: 8, 16, 17.

Accepted Answer

26

Answer

Идея решения: разбить задачу на два этапа — найти количество путей от 2 до 14, затем от 14 до 29, и перемножить результаты.

Обозначим $R(a, b)$ — количество программ, преобразующих число $a$ в число $b$.

Построим рекуррентное соотношение. Число $n$ можно получить двумя способами:
- прибавив 1 к числу $n - 1$;
- умножив на 2 число $n / 2$ (если $n$ чётно).

Поэтому:
- $R(a, n) = R(a, n-1) + R(a, n/2)$, если $n$ чётно и $n > a$;
- $R(a, n) = R(a, n-1)$, если $n$ нечётно и $n > a$;
- $R(a, a) = 1$ (база).

Вычислим $R(2, 14)$:

| $n$ | $R(2, n)$ |
|---|---|
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| 6 | 3 |
| 7 | 3 |
| 8 | 5 |
| 9 | 5 |
| 10 | 7 |
| 11 | 7 |
| 12 | 10 |
| 13 | 10 |
| 14 | 13 |

Вычислим $R(14, 29)$:

| $n$ | $R(14, n)$ |
|---|---|
| 14 | 1 |
| 15 | 1 |
| 16 | 2 |
| 17 | 2 |
| 18 | 3 |
| 19 | 3 |
| 20 | 4 |
| 21 | 4 |
| 22 | 5 |
| 23 | 5 |
| 24 | 7 |
| 25 | 7 |
| 26 | 8 |
| 27 | 8 |
| 28 | 11 |
| 29 | 11 |

Количество программ, проходящих через 14: $R(2, 14) 	imes R(14, 29) = 13 	imes 2 = 26$.

Проверка через рекурсию:

```python
def f(x, y):
    if x > y:
        return 0
    if x == y:
        return 1
    return f(x + 1, y) + f(x * 2, y)

result = f(2, 14) * f(14, 29)
print(result)
```

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