Question

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

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

Программа — последовательность команд. Найти количество программ, которые:
- начинают с числа 3
- заканчиваются числом 18
- траектория содержит число 14
- траектория не содержит число 8

Accepted Answer

360

Answer

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

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

Рекуррентное соотношение:
- если $x > y$ или $x = 8$: $f(x, y) = 0$ (выход за границы или запретное число)
- если $x = y$: $f(x, y) = 1$ (достигли цели)
- иначе: $f(x, y) = f(x+1, y) + f(x+2, y) + f(x 	imes 2, y)$ (применяем все три команды)

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