Question

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

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

Программа — это последовательность команд. Траектория вычислений — последовательность результатов выполнения всех команд.

Сколько существует программ, для которых при исходном числе 3 результатом является число 37, и при этом траектория вычислений содержит число 18?

Accepted Answer

28

Answer

Идея решения: найти количество путей из 3 в 37, проходящих через 18, используя динамическое программирование для подсчёта количества программ, преобразующих одно число в другое.

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

Рекуррентное соотношение:
- Если $n$ нечётно: $R(n) = R(n - 1)$ (можно только прибавить 1).
- Если $n$ чётно: $R(n) = R(n - 1) + R(n / 2)$ (либо прибавить 1, либо получить путём умножения на 2).

Начальное условие: $R(3) = 1$.

Вычислим значения:

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

Количество программ, проходящих через 18 и заканчивающихся в 37, равно:
$$R(3 	o 18) 	imes R(18 	o 37)$$

Вычислим $R(18 	o 37)$. Заметим, что 37 нечётно, поэтому $R(37) = R(36)$.

Для чётного 36: $R(36) = R(35) + R(18)$.

Число 35 нечётно, поэтому $R(35) = R(34) = \ldots = R(18) = 14$ (из 18 в 35 можно только прибавлять единицы).

Таким образом:
$$R(18 	o 37) = R(36) = R(35) + R(18) = 14 + 14 = 28$$

Но нам нужны программы, которые начинаются в 3, проходят через 18 и заканчиваются в 37. Это означает:
$$	ext{Количество} = R(3 	o 18) 	imes R(18 	o 37) = 14 	imes 2 = 28$$

Альтернативное решение на Python:

```python
def count_paths(start, end):
    memo = {}
    
    def f(x):
        if x > end:
            return 0
        if x == end:
            return 1
        if x in memo:
            return memo[x]
        
        result = f(x + 1)
        if x * 2 <= end:
            result += f(x * 2)
        
        memo[x] = result
        return result
    
    return f(start)

paths_3_to_18 = count_paths(3, 18)
paths_18_to_37 = count_paths(18, 37)
answer = paths_3_to_18 * paths_18_to_37

print(answer)
```

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