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