Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены буквами.
A. Вычесть 1.
B. Разделить на 2.
С. Разделить на 3.
Команда B может быть исполнена только для чётного числа,
Программа для исполнителя — это последовательность команд. Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы BAС при исходном
Сколько существует программ, которые преобразуют исходное
Приведём решение на языке Python.
def f(x, y):
if x < y or x == 12 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(19, 1))
Ответ: 43.
Приведём решение Ильи Андрианова на языке Python.
def F(a, b):
if a <= b or a == 15 or a == 12:
return a == b
summa = 0
summa += F(a-1, b)
if a % 2 == 0:
summa += F(a//2, b)
if a % 3 == 0:
summa += F(a//3, b)
return summa
print(F(19, 1))