Question

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

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

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

Accepted Answer

14

Answer

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

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

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

Вычислим $R(n)$ для $n$ от 1 до 10:

$$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$$

Таким образом, из 1 в 10 существует 14 программ.

Теперь найдём количество программ из 10 в 21, не проходящих через 17. Используем рекурсивный подход с условием: если текущее число равно 17, путь невозможен; если число превышает 21, путь невозможен; если число равно 21, найден один путь.

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

result = f(1, 10) * f(10, 21)
print(result)
```

Функция $f(10, 21)$ вычисляет количество путей из 10 в 21 без прохождения через 17. Результат: $f(10, 21) = 1$ (единственный путь: $10 	o 20 	o 21$).

Финальный ответ: $14 	imes 1 = 14$.

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