Question

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

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

Первая команда увеличивает число на экране на 1, вторая умножает его на 2.

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

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

Accepted Answer

14

Answer

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

**Подсчёт программ из 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$$

**Подсчёт программ из 10 в 21, не проходящих через 18:**

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

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

result = f(10, 21)
```

Проверим вручную: из 10 можно перейти в 11 или 20. Из 11 — в 12 или 22 (22 > 21, отсекается). Из 20 — в 21 или 40 (40 > 21, отсекается). Путь 10 → 20 → 21 — единственный допустимый маршрут.

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

**Итоговый ответ:**

$$14 	imes 1 = 14$$

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