Question

У исполнителя Удвоитель две команды:
1. **Прибавь 1** — увеличивает число на 1.
2. **Умножь на 2** — удваивает число.

Программа — это последовательность команд. Сколько программ преобразуют число 2 в число 22?

Accepted Answer

37

Answer

Идея решения: обозначим $R(n)$ количество программ, преобразующих 2 в $n$, и выведем рекуррентное соотношение на основе того, какая команда была последней.

Ключевые наблюдения:

1. Если $n$ нечётно, то последняя команда — «Прибавь 1» (удвоение даёт чётное число). Значит, $R(n) = R(n-1)$.

2. Если $n$ чётно и $n > 2$, то последняя команда либо «Прибавь 1» (из $n-1$), либо «Умножь на 2» (из $n/2$). Поэтому $R(n) = R(n-1) + R(n/2)$.

3. Базовый случай: $R(2) = 1$ (начальное число).

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

$$R(2) = 1$$
$$R(3) = R(2) = 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$$

Альтернативное решение через рекурсию с мемоизацией:

```python
def count_programs(start, target, memo=None):
    if memo is None:
        memo = {}
    
    if start == target:
        return 1
    if start > target:
        return 0
    
    if start in memo:
        return memo[start]
    
    result = (count_programs(start + 1, target, memo) +
              count_programs(start * 2, target, memo))
    memo[start] = result
    return result

print(count_programs(2, 22))
```

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