Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. вычти 3
B. подели на 2
Первая команда уменьшает число на экране на 3, вторая команда делит число на 2 (нецелый результат округляется до ближайшего целого в большую сторону). Программа для исполнителя — это последовательность команд.
Сколько существует таких программ, которые исходное число 120 преобразуют в число 20, при этом траектория вычислений не содержит чисел 35 и 51?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы ABA при исходном числе 100 траектория состоит из
Приведём решение на языке Python.
def f(x, y):
if x < y :
return 0
if x == 35 or x == 51:
return 0
if x == y:
return 1
else:
return f(x - 3, y) + f(x // 2 + x % 2, y)
print(f(120, 20))
Ответ: 10.

