Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены буквами.
A. Вычесть 1.
B. Разделить на 2.
С. Разделить на 3.
Команда B может быть исполнена только для чётного числа,
Программа для исполнителя — это последовательность команд. Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы BAС при исходном
Сколько существует программ, которые преобразуют исходное число 22 в число 1 и при этом траектория вычислений не содержит
Приведём решение на языке Python.
def f(x, y):
if x < y or x == 10 or x == 15:
return 0
if x == y:
return 1
if x%2==0 and x%3==0 :
return f(x - 1, y) + f(x // 2, y) + f(x // 3, y)
if x%2==0 and x%3!=0 :
return f(x - 1, y) + f(x // 2, y)
if x%3==0 and x%2!=0:
return f(x - 1, y) + f(x // 3, y)
if x%2!=0 and x%3!=0:
return f(x - 1, y)
print(f(22, 1))
Ответ: 53.