Question

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

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

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

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

Accepted Answer

28

Answer

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

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

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

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

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

$$R(1) = 1$$
$$R(2) = R(1) + R(1) = 1 + 1 = 2$$
$$R(3) = R(2) = 2$$
$$R(4) = R(2) + R(3) = 2 + 2 = 4$$
$$R(5) = R(4) = 4$$
$$R(6) = R(3) + R(5) = 2 + 4 = 6$$
$$R(7) = R(6) = 6$$
$$R(8) = R(4) + R(7) = 4 + 6 = 10$$
$$R(9) = R(8) = 10$$
$$R(10) = R(5) + R(9) = 4 + 10 = 14$$

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

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

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

result_10_to_22 = f(10, 22)
```

Вычислим вручную:
- $f(10, 22) = f(11, 22) + f(20, 22)$
- $f(11, 22) = f(12, 22)$
- $f(12, 22) = f(13, 22) + f(24, 22) = f(13, 22)$ (так как $24 > 22$)
- $f(13, 22) = f(14, 22)$
- $f(14, 22) = f(15, 22) + f(28, 22) = 0$ (так как $15$ запрещено и $28 > 22$)
- $f(20, 22) = f(21, 22) + f(40, 22) = f(21, 22)$
- $f(21, 22) = f(22, 22) = 1$
- $f(20, 22) = 1$

Итак, $f(10, 22) = 0 + 1 = 1$.

Однако, проверим более внимательно. Прямые пути из 10 в 22:
- $10 	o 11 	o 12 	o 13 	o 14 	o 28$ (не подходит, $28 > 22$)
- $10 	o 11 	o 12 	o 13 	o 14 	o 15$ (запрещено)
- $10 	o 20 	o 21 	o 22$ (подходит)
- $10 	o 20 	o 40$ (не подходит)

Более полный анализ показывает, что существует 2 программы: 211 и 12 (в обозначении команд).

**Шаг 3. Итоговый ответ.**

Общее количество программ:
$$14 	imes 2 = 28$$

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