Задача #3553
Количество программ
(Герасимчук В.) Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Умножить на 2
B. Возвести в квадрат
C. Возвести в куб
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 131072, при этом траектория вычислений не содержит одновременно 4 и 16?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ACB при исходном числе 2 траектория состоит из чисел 4, 64, 4096.
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
32
def f(a, b):
if a == b:
return 1
elif a > b:
return 0
else:
return f(a * 2, b) + f(a ** 2, b) + f(a ** 3, b)
# нам подойдут все траектории кроме тех,
# которые содержат одновременно 4 и 16 - найдем и вычтем их
ans1 = f(2, 131072)
ans2 = f(2, 4) * f(4, 16) * f(16, 131072)
print(ans1 - ans2)