Алгоритм решения задания 14. Часть 1
Учимся решать 15 задания первого типа
Читать
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены буквами:
A. Прибавить 2
B. Прибавить 3
C. Умножить на 3 и прибавить 1
Программа для исполнителя – это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 2 в число 44, и при этом траектория содержит не более 12 нечётных чисел.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы BAC при исходном числе 2 траектория будет состоять из чисел 5, 7, 22.
Правильный ответ:
71932
from functools import lru_cache
@lru_cache(None)
def f(x, y, cnt=0):
if x % 2:
cnt += 1
if x == y and cnt <= 12:
return 1
if x > y:
return 0
return f(x + 2, y, cnt) + f(x + 3, y, cnt) + f(x * 3 + 1, y, cnt)
print(f(2, 44))
