Задача #3548
Количество программ
(Герасимчук В.) Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Умножить на 2
B. Умножить на 4
C. Прибавить 1
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 36 результатом является число 156, при этом траектория вычислений (не считая конечного числа) не содержит чисел, больших 150?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы BСС при исходном числе 13 траектория состоит из чисел 52, 53, 54.
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
6
def f(a, b):
if a == b:
return 1
elif a > 150:
return 0
else:
return f(a * 2, b) + f(a * 4, b) + f(a + 1, b)
print(f(36, 156))