Алгоритм решения задания 14. Часть 1
Учимся решать 15 задания первого типа
Читать
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 1 в число 24, и при этом никакая команда не повторяется более двух раз подряд?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы BAB при исходном числе 1 траектория состоит из чисел 2, 3, 6.
Правильный ответ:
6
def f(x, y, path=""):
# Проверка команд
if "AAA" in path or "BBB" in path:
return 0
if x == y:
return 1
if x > y:
return 0
if x < y:
return (f(x + 1, y, path + "A") +
f(x * 2, y, path + "B"))
print(f(1, 24))
