Задача #3551
Количество программ
(Герасимчук В.) Исполнитель преобразует число на экране. У исполнителя есть четыре команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 2
C. Прибавить 4
D. Прибавить 8
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 16 результатом является число 48, при этом траектория вычислений содержит ровно одно число из множества {24, 32}?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы ABD при исходном числе 10 траектория состоит из чисел 11, 13, 21.
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
22681617
def f(a, b, not_number):
if a == b:
return 1
elif a > b or a == not_number:
return 0
else:
return (f(a + 1, b, not_number) + f(a + 2, b, not_number) +
f(a + 4, b, not_number) + f(a + 8, b, not_number))
# траектория содежит 24, но при этом не содержит 32
ans1 = f(16, 24, 32) * f(24, 48, 32)
# траектория содежит 32, но при этом не содержит 24
ans2 = f(16, 32, 24) * f(32, 48, 24)
print(ans1 + ans2)
