Исполнитель Щелчок находится на первой ступеньке очень длинной лестницы. У исполнителя есть 3 команды:
1. Подняться на одну ступеньку и потратить одну единицу энергии.
2. Перешагнуть через одну ступеньку (подняться на две) и потратить 3 единицы энергии
3. Перешагнуть через две ступеньки (подняться на 3 ступеньки) и потратить 6 единиц энергии
Программа для исполнителя — это последовательность команд.
У исполнителя в запасе 60 единиц энергии, длина лестницы 25 ступенек. За какое минимальное количество команд исполнитель сможет добраться до последней ступеньки и сохранить максимальный для такого количества команд запас энергии. Если запас энергии исполнителя кончается, он отчаивается и не идет дальше, кроме случая, если он уже на 25 ступеньке. В ответе укажите количество команд и максимальный сохраненный запас энергии.
Решение 1 (Рекурсия)
from functools import lru_cache
@lru_cache(None)
def f(st, fn, en, comand):
global count, ener
if st == fn and en >= 0:
if comand < count:
count = comand
ener = en
#если количество шагов совпало,
# то мы берем максимум энергии
elif comand == count and en > ener:
ener = en
return # вылет из программы
if en < 0:
return
f(st + 1, fn, en - 1, comand + 1)
f(st + 2, fn, en - 3, comand + 1)
f(st + 3, fn, en - 6, comand + 1)
count = 10000000
ener = -1
f(1, 25, 60, 0)
print(count, ener)
Решение 2 (Динамика)
ans = []
ans.append((1, 60, 0))
# (текущая ступенька, текущее кол-во энергии, кол-во сделанных ходов)
otv, mn_com = -100000000, 100000000
for operations in range(1000):
can_get = []
for i in ans:
step, energy, go = i
if (step > 25) or (energy < 0):
continue
if (step == 25) and (energy >= 0):
if mn_com == go: # берем минимум команд и максимум энергии
mn_com = go
otv = max(otv, energy)
continue
elif mn_com > go:
mn_com = go
otv = energy
continue
# все возможные ходы
can_get.append((step + 1, energy - 1, go + 1))
can_get.append((step + 2, energy - 3, go + 1))
can_get.append((step + 3, energy - 6, go + 1))
# если больше ходов нет, выходим из цикла
if len(can_get) == 0:
break
ans = can_get.copy()
print(mn_com, otv)