Задача #1523
Количество программ
(М. Ишимов) Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавить 2
B. Прибавить 4
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 9 результатом является число 37, и при этом траектория вычислений содержит числа 27 и 29, но не содержит число 32?
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
275
def f(s, e):
if s >= e or s == 32: return s == e
return f(s + 2, e) + f(s + 4, e)
print(f(9, 27) * f(27, 29) * f(29, 37))