Исполнитель Щелчок преобразует число на экране. У исполнителя есть две команды:
1. Прибавить 4
2. Вычесть 5
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числe 1 результатом является число 20. При этом исполнитель не может посетить одно и то же число дважды и может двигаться пока не перейдет границы отрезка [-20; 40], при переходе границ исполнитель разрушается.
Решение 1 (Рекурсия)
def f(start, finish, limits, visited):
if (start == finish):
return 1
if (start < limits[0]) or (start > limits[1]):
return 0
if (start in visited):
return 0
vis = visited.copy()
vis.add(start)
x = f(start + 4, finish, limits, vis)
y = f(start - 5, finish, limits, vis)
return x + y
print(f(1, 20, (-20, 40), set()))
Решение 2 (Динамика)
ans = []
ans.append((1, set([1])))
otv = 0
for operations in range(1000):
can_get = []
for i in ans:
a, vis = i
vis_first = vis.copy()
vis_second = vis.copy()
if a == 20:
otv += 1
continue
if ((a + 4) in vis) == 0 and (a + 4 <= 40):
vis_first.add(a + 4)
can_get.append((a + 4, vis_first))
if ((a - 5) in vis) == 0 and (a - 5 >= -20):
vis_second.add(a - 5)
can_get.append((a - 5, vis_second))
if len(can_get) == 0:
break
ans = can_get
print(otv)