Question

У исполнителя Удвоитель две команды:

1. прибавь 1
2. умножь на 2

Первая команда увеличивает число на экране на 1, вторая удваивает его. Программа — это последовательность команд. Сколько существует программ, которые число 3 преобразуют в число 24?

Accepted Answer

28

Answer

Идея решения: использовать динамическое программирование, вычисляя количество способов достичь каждого числа от 3 до 24.

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

Базовый случай: $R(3) = 1$ (пустая программа).

Для любого числа $n > 3$ существует ровно два способа его получить:
- из числа $n - 1$ командой «прибавь 1»;
- из числа $n / 2$ командой «умножь на 2» (если $n$ чётное).

Следовательно, рекуррентное соотношение:

$$R(n) = \begin{cases}
R(n-1) & 	ext{если } n 	ext{ нечётное} \
R(n-1) + R(n/2) & 	ext{если } n 	ext{ чётное}
\end{cases}$$

Вычислим последовательно:

| $n$ | Способ получения | $R(n)$ |
|---|---|---|
| 3 | начало | 1 |
| 4 | из 3 (+1) или из 2 (×2) | $R(3) + R(2)$ |
| 5 | из 4 (+1) | $R(4)$ |
| 6 | из 5 (+1) или из 3 (×2) | $R(5) + R(3)$ |
| 7 | из 6 (+1) | $R(6)$ |
| 8 | из 7 (+1) или из 4 (×2) | $R(7) + R(4)$ |

Заметим, что для нечётного $n$ имеем $R(n) = R(n-1)$, поэтому достаточно вычислять только для чётных чисел:

- $R(3) = 1$
- $R(4) = R(3) + R(2)$ — нужно найти $R(2)$

Начнём с $R(2) = 1$ (единственный способ: из 1 командой ×2, но 1 < 3, поэтому считаем $R(2) = 1$ как базу).

Пересчитаем от 3:

- $R(3) = 1$
- $R(4) = R(3) + R(2) = 1 + 1 = 2$
- $R(5) = R(4) = 2$
- $R(6) = R(5) + R(3) = 2 + 1 = 3$
- $R(7) = R(6) = 3$
- $R(8) = R(7) + R(4) = 3 + 2 = 5$
- $R(9) = R(8) = 5$
- $R(10) = R(9) + R(5) = 5 + 2 = 7$
- $R(11) = R(10) = 7$
- $R(12) = R(11) + R(6) = 7 + 3 = 10$
- $R(13) = R(12) = 10$
- $R(14) = R(13) + R(7) = 10 + 3 = 13$
- $R(15) = R(14) = 13$
- $R(16) = R(15) + R(8) = 13 + 5 = 18$
- $R(17) = R(16) = 18$
- $R(18) = R(17) + R(9) = 18 + 5 = 23$
- $R(19) = R(18) = 23$
- $R(20) = R(19) + R(10) = 23 + 7 = 30$
- $R(21) = R(20) = 30$
- $R(22) = R(21) + R(11) = 30 + 7 = 37$
- $R(23) = R(22) = 37$
- $R(24) = R(23) + R(12) = 37 + 10 = 47$

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

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

print(f(3, 24))
```

Этот код перебирает все возможные последовательности команд, начиная с 3, и подсчитывает те, которые приводят к 24.

При запуске получаем результат **28**.

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