Question

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

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

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Май15 — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Accepted Answer

13

Answer

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

**Шаг 1. Подсчёт программ из 2 в 14.**

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

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

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

Вычислим последовательно:
- $R(3) = R(2) = 1$
- $R(4) = R(2) + R(3) = 1 + 1 = 2$
- $R(5) = R(4) = 2$
- $R(6) = R(3) + R(5) = 1 + 2 = 3$
- $R(7) = R(6) = 3$
- $R(8) = R(4) + R(7) = 2 + 3 = 5$
- $R(9) = R(8) = 5$
- $R(10) = R(5) + R(9) = 2 + 5 = 7$
- $R(11) = R(10) = 7$
- $R(12) = R(6) + R(11) = 3 + 7 = 10$
- $R(13) = R(12) = 10$
- $R(14) = R(7) + R(13) = 3 + 10 = 13$

Итак, $R(14) = 13$.

**Шаг 2. Подсчёт программ из 14 в 29, не проходящих через 25.**

Используем рекурсивную функцию с мемоизацией. Функция $f(x, y)$ возвращает количество программ, преобразующих $x$ в $y$, не проходящих через 25.

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

Вычислим $f(14, 29)$:
- Из 14 можно перейти в 15 (прибавить 1) или в 28 (умножить на 2).
- Из 15 → 16 или 30 (30 > 29, не подходит).
- Из 28 → 29 или 56 (56 > 29, не подходит).

Единственный путь: $14 	o 28 	o 29$ (команды: умножить на 2, прибавить 1).

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

**Шаг 3. Итоговый результат.**

Общее количество программ: $R(14) 	imes f(14, 29) = 13 	imes 1 = 13$.

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