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

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

Мы используем рекурсивный подход для подсчёта количества всех возможных программ, которые преобразуют число 1 в число 20, соблюдая условия о границах и уникальности посещения чисел.

Мы определяем функцию f(start, finish, limits, visited), где: - start — текущее число, на котором находится исполнитель; - finish — число, до которого нужно дойти; - limits — кортеж, содержащий минимальное и максимальное допустимое число на экране; - visited — множество чисел, которые уже были посещены, чтобы не допустить повторов.

Шаг за шагом алгоритм работает следующим образом:

1. Проверяем, достигли ли мы цели:

- Если start == finish, мы нашли одну допустимую программу и возвращаем 1.

2. Проверяем границы:

- Если start меньше limits[0] или больше limits[1], путь невозможен и возвращаем 0.

3. Проверяем повторное посещение:

- Если текущее число уже есть в visited, путь недопустим, возвращаем 0.

4. Если ни одно из условий не выполнено:

- Создаем копию множества visited и добавляем текущее число в неё, чтобы отслеживать посещенные позиции на этом ветвлении рекурсии.

- Рекурсивно считаем количество программ, используя первую команду (start + 4) и вторую команду (start - 5).

- Складываем результаты двух рекурсивных вызовов, чтобы получить общее количество программ для текущего start.

5. Запускаем функцию с начальными значениями start=1, finish=20, limits=(-20,40) и пустым множеством visited.

# Определяем рекурсивную функцию для подсчета программ
def f(start, finish, limits, visited):
    # Если достигли целевого числа, возвращаем 1
    if (start == finish):
        return 1
    # Если текущее число вышло за границы допустимого интервала, возвращаем 0
    if (start < limits[0]) or (start > limits[1]):
        return 0
    # Если текущее число уже посещено, возвращаем 0
    if (start in visited):
        return 0
    # Создаем копию множества посещенных чисел и добавляем текущее число
    vis = visited.copy()
    vis.add(start)
    # Считаем количество программ, если выполнить команду "прибавить 4"
    x = f(start + 4, finish, limits, vis)
    # Считаем количество программ, если выполнить команду "вычесть 5"
    y = f(start - 5, finish, limits, vis)
    # Общее количество программ для текущего числа — сумма двух вариантов
    return x + y

# Запускаем функцию от 1 до 20 с указанными границами и пустым множеством посещенных чисел
print(f(1, 20, (-20, 40), set()))

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

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

Далее выполняем итеративный цикл по количеству операций (здесь ограничиваем до 1000 шагов, чтобы цикл завершился):

1. Создаем пустой список can_get, куда будем добавлять все новые состояния, достижимые на этом шаге.

2. Перебираем каждое текущее состояние из списка ans:

- Если текущее число равно целевому 20, увеличиваем на 1 и продолжаем к следующему состоянию.

- Иначе создаем две копии множества посещённых чисел: vis_first и vis_second для двух возможных команд.

- Проверяем возможность хода "прибавить 4": число не должно быть уже посещено и не должно превышать верхнюю границу 40. Если допустимо, добавляем новое число в множество и заносим в список возможных следующих состояний.

- Проверяем возможность хода "вычесть 5": число не должно быть уже посещено и не должно быть меньше нижней границы -20. Если допустимо, добавляем новое число в множество и заносим в список возможных следующих состояний.

3. Если после обработки всех состояний на шаге can_get пустой, значит новых ходов нет, выходим из цикла.

4. Обновляем ans новым списком can_get для следующей итерации.

После завершения цикла в переменной otv будет храниться общее количество допустимых программ из числа 1 в число 20.

# Инициализируем список ans состоянием: текущее число 1 и множество {1}
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
        # Проверяем возможность прибавить 4
        if ((a + 4) in vis) == 0 and (a + 4 <= 40):
            vis_first.add(a + 4)
            can_get.append((a + 4, vis_first))
        # Проверяем возможность вычесть 5
        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)