23.08 Прочие прототипы

Решение рекурсией

Идея рекурсивного решения заключается в построении функции f(st, fn, en, comand), которая рассматривает все возможные последовательности команд для достижения цели и одновременно отслеживает оставшуюся энергию и количество сделанных ходов.

1. Мы создаем функцию с аргументами:

- st — текущая ступенька, на которой находится исполнитель;

- fn — целевая ступенька, на которую нужно попасть (в нашем случае 25);

- en — количество оставшейся энергии;

- comand — количество использованных команд.

2. Внутри функции выполняются следующие проверки:

- Если st == fn и энергия en >= 0, значит мы достигли цели:

- Если текущее количество команд меньше глобального минимального, обновляем минимальное количество команд и сохраняем текущую энергию.

- Если текущее количество команд равно глобальному минимальному и энергия больше сохранённой, обновляем максимальную энергию.

- Возвращаемся из функции, так как дальнейшие шаги не нужны.

- Если en < 0, то дальнейшие шаги невозможны, функция также завершает выполнение.

3. Если ни одно из условий не выполнено, мы рекурсивно вызываем функцию для всех трёх команд:

- Подняться на одну ступеньку и потратить 1 единицу энергии (f(st + 1, fn, en - 1, comand + 1));

- Подняться на две ступеньки и потратить 3 единицы энергии (f(st + 2, fn, en - 3, comand + 1));

- Подняться на три ступеньки и потратить 6 единиц энергии (f(st + 3, fn, en - 6, comand + 1)).

4. С помощью lru_cache мы кэшируем результаты вызовов функции, чтобы избежать повторных вычислений для одинаковых комбинаций аргументов и ускорить работу программы.

5. Изначально глобальные переменные:

- count — большое число для минимизации команд,

- ener — минимально возможная энергия, которую будем обновлять при нахождении лучших решений.

6. Запускаем функцию с начальными параметрами: первая ступенька, целевая 25-я, 60 единиц энергии и 0 команд. После завершения рекурсии выводим найденные значения минимального числа команд и максимальной энергии.

# Импортируем кэширование для ускорения рекурсии
from functools import lru_cache

# Создаем функцию f с аргументами: текущая ступенька st, конечная fn, энергия en, количество команд comand
@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)

—

Решение динамикой

Идея динамического подхода заключается в том, чтобы постепенно строить список всех достижимых состояний на каждом шаге, начиная с первой ступеньки. Каждое состояние представляет собой кортеж: текущая ступенька, оставшаяся энергия, количество сделанных команд.

1. Создаем список ans и помещаем туда начальное состояние: первая ступенька, 60 единиц энергии, 0 команд.

2. В цикле перебираем возможные шаги до тех пор, пока есть новые состояния: - Для каждого состояния проверяем: - Если текущая ступенька больше 25 или энергия отрицательна — игнорируем это состояние. - Если достигнута 25-я ступенька и энергия неотрицательна: - Если количество команд равно текущему минимальному, обновляем максимальную энергию. - Если количество команд меньше минимального, обновляем минимальное количество команд и сохраняем энергию. - Для остальных состояний добавляем новые возможные ходы: - Подняться на 1 ступеньку и потратить 1 единицу энергии. - Подняться на 2 ступеньки и потратить 3 единицы энергии. - Подняться на 3 ступеньки и потратить 6 единиц энергии.

3. После обработки всех состояний нового уровня копируем их в ans для следующей итерации.

4. Цикл продолжается до тех пор, пока возможные новые ходы существуют. В конце выводим минимальное количество команд и максимальную энергию, которые были найдены.

# Инициализация списка достижимых состояний
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)