13. Анализ хода исполнения алгоритма: Вычесть 1, Вычесть 2, Найти целую часть от деления на 3
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть $1$
B. Вычесть $2$
C. Найти целую часть от деления на $3$
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе $19$ результатом является число $3$, при этом траектория вычислений не содержит чисел $9$ и $16$?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе $13$ траектория состоит из чисел $4$, $2$, $1$.
Так как все команды уменьшают число, будем считать количество программ, переводящих число $19$ в число $3$. Числа $9$ и $16$ запрещаем.
def f(x, y):
if x == y:
return 1
if x < y or x == 9 or x == 16:
return 0
return f(x - 1, y) + f(x - 2, y) + f(x // 3, y)
print(f(19, 3))
Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$. Если получено число $9$ или $16$, такая траектория не подходит. Если значение стало меньше $y$, прийти обратно к $y$ уже невозможно.
Программа выведет: $180$.