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