Задача #1529
Количество программ
(М. Ишимов) Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 5
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 42 результатом является число 9, и при этом траектория вычислений содержит числа 23 и 22, но не содержит число 32?
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
1160
def f(s, e):
if s <= e or s == 32: return s == e
return f(s - 1, e) + f(s - 5, e)
print(f(42, 23) * f(23, 22) * f(22, 9))