Question

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

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

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

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.

Accepted Answer

200

Answer

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

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

Рекуррентное соотношение:
- Если $x > y$ или $x = 13$, то $f(x, y) = 0$ (невозможно достичь или запрещённое число).
- Если $x = y$, то $f(x, y) = 1$ (пустая программа).
- Иначе $f(x, y) = f(x+1, y) + f(x+2, y) + f(x \cdot 3, y)$ (применяем одну из трёх команд).

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