Исполнитель Щелчок преобразует число на экране. У исполнителя есть три команды:
1. Поделить на 2, если число четное
2. Прибавить 1
3. Прибавить треть числа, если число кратно трем
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числe 1 результатом является число 60, при этом программа содержит 25 команд, при этом одно и то же число может встречаться несколько раз в траектории вычислений исполнителя.
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 12223 при исходном числе 6 траектория будет состоять из чисел 3, 4, 5, 6, 8.
Решение 1 (Рекурсия)
from functools import lru_cache # программа будет долго считать, если
# не хранить результаты в кэше
@lru_cache(None)
def f(st, fn, count, end_count):
if st == fn and count == end_count:
return 1
if count > end_count:
return 0
x = f(st // 2, fn, count + 1, end_count) * (st % 2 == 0)
y = f(st + 1, fn, count + 1, end_count)
z = f(st + st // 3, fn, count + 1, end_count) * (st % 3 == 0)
return x + y + z
print(f(1, 60, 0, 25))
Решение 2 (Динамика)
ans = []
ans.append(1)
for operations in range(25):
can_get = []
for i in ans:
if i % 2 == 0:
can_get.append(i // 2)
can_get.append(i + 1)
if i % 3 == 0:
can_get.append(i + i // 3)
ans = can_get
print(ans.count(60))