Question

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

**1. Прибавить 1**
**2. Умножить на 2**

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

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

Accepted Answer

28

Answer

Идея решения: разбить задачу на два независимых этапа — найти количество программ из 1 в 10, затем из 10 в 21, и перемножить результаты.

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

Для вычисления $R(a, b)$ используем рекуррентное соотношение:
- Если $a > b$: $R(a, b) = 0$ (невозможно уменьшить число).
- Если $a = b$: $R(a, b) = 1$ (пустая программа).
- Если $a < b$: $R(a, b) = R(a+1, b) + R(a \cdot 2, b)$ (либо прибавляем 1, либо умножаем на 2).

Вычислим $R(1, 10)$:

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

Таким образом, $R(1, 10) = 14$.

Вычислим $R(10, 21)$:

| $n$ | $R(10, n)$ |
|---|---|
| 10 | 1 |
| 11 | 1 |
| 12 | 1 |
| 13 | 1 |
| 14 | 1 |
| 15 | 1 |
| 16 | 1 |
| 17 | 1 |
| 18 | 1 |
| 19 | 1 |
| 20 | 2 |
| 21 | 2 |

Таким образом, $R(10, 21) = 2$.

Итоговое количество программ: $R(1, 10) 	imes R(10, 21) = 14 	imes 2 = 28$.

Проверка с помощью рекурсивной функции:

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

print(f(1, 10) * f(10, 21))
```

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

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