Question

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

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

Accepted Answer

10

Answer

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

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

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

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