Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены буквами:
A. Прибавить 1
B. Умножить на 2
Программа для исполнителя — это последовательность команд. Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы BAB при исходном числе 2 траектория вычислений содержит числа 4, 5, 10.
Сколько существует программ, которые преобразуют исходное число 1 в число 17 и при этом траектория вычислений содержит не более 4 чётных чисел?
Решение:
Решение на Python:
def F(x, y, k):
if x > y or k > 4:
return 0
if x == y:
return 1
return F(x + 1, y, k + ((x + 1) % 2 == 0)) + F(x * 2, y, k + ((x * 2) % 2 == 0))
print(F(1, 17, 0))Ответ: 8
Ответ:
8