Question

Исполнитель преобразует число на экране. Доступны две команды:
- **A.** Вычти 2.
- **B.** Найди целую часть от деления на 2.

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

Траектория вычислений — последовательность результатов выполнения всех команд. Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.

Accepted Answer

36

Answer

Идея решения: разбить задачу на два этапа — найти количество путей от 38 до 16, затем от 16 до 2, и перемножить результаты.

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

Рекуррентное соотношение:
- Если $x < y$: невозможно достичь $y$ из $x$ (обе операции не увеличивают число), поэтому $f(x, y) = 0$.
- Если $x = y$: пустая программа, $f(x, y) = 1$.
- Если $x > y$: можно применить команду A (вычесть 2) или команду B (разделить на 2), поэтому $f(x, y) = f(x - 2, y) + f(x \div 2, y)$.

Ответ на задачу: $f(38, 16) 	imes f(16, 2)$.

```python
def f(x, y):
    if x < y:
        return 0
    if x == y:
        return 1
    return f(x - 2, y) + f(x // 2, y)

print(f(38, 16) * f(16, 2))
```

Вычисляем:
- $f(38, 16)$: количество путей от 38 к 16.
- $f(16, 2)$: количество путей от 16 к 2.
- Произведение даёт итоговое количество программ, проходящих через 16.

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