23.05 Количество программ из A в B смешанное

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

Мы создаём функцию f(st, fn, exit_number, count, end_count), которая будет рекурсивно подсчитывать количество программ, приводящих число st к числу fn, учитывая: - исключение числа exit_number из траектории; - количество уже выполненных команд count и необходимое общее количество end_count.

Алгоритм работы функции следующий:

1. Проверяем, достигли ли мы целевого числа с нужным количеством команд:

- если st == fn и count == end_count, возвращаем 1 — найден один корректный путь.

2. Проверяем условия выхода:

- если st > fn (число стало больше целевого),

- или count > end_count (исполнено больше команд, чем нужно),

- или st == exit_number (текущий элемент траектории запрещён), то возвращаем 0 — такой путь недопустим.

3. Вычисляем возможные переходы из текущего числа:

- переменная x — результат рекурсивного вызова при выполнении команды «прибавить 2», если число кратно 3;

- переменная y — результат рекурсивного вызова при выполнении команды «прибавить 3», если число кратно 2;

- переменная z — результат рекурсивного вызова при выполнении команды «прибавить 1», если число не кратно ни 2, ни 3;

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

# Определяем рекурсивную функцию f
def f(st, fn, exit_number, count, end_count):
    # Если достигли целевого числа с нужным количеством команд,
    # считаем, что найден один путь
    if st == fn and count == end_count:
        return 1
    # Если текущее число превысило целевое,
    # количество команд превышено или число запрещено, путь недопустим
    if st > fn or count > end_count or st == exit_number:
        return 0
    # Рекурсивно проверяем вариант прибавления 2, если число кратно 3
    x = f(st + 2, fn, exit_number, count + 1, end_count) * (st % 3 == 0)
    # Рекурсивно проверяем вариант прибавления 3, если число кратно 2
    y = f(st + 3, fn, exit_number, count + 1, end_count) * (st % 2 == 0)
    # Рекурсивно проверяем вариант прибавления 1, если число не кратно 2 и 3
    z = f(st + 1, fn, exit_number, count + 1, end_count) * (st % 2 != 0
                                                            and st % 3 != 0)
    # Возвращаем сумму всех допустимых вариантов
    return x + y + z

# Запускаем функцию с начальным числом 3, конечным 27, запретом числа 22,
# с 0 выполненными командами и общим числом команд 12
print(f(3, 27, 22, 0, 12))

—

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

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

Далее мы последовательно выполняем 12 шагов (по количеству команд):

1. Создаём временный список can_get, куда будем добавлять новые числа, полученные после применения команд.

2. Для каждого числа i в списке ans:

- если i == 22, пропускаем это число, так как траектория не должна его содержать;

- если i % 3 == 0, добавляем i+2 в can_get — команда 1;

- если i % 2 == 0, добавляем i+3 в can_get — команда 2;

- если i % 2 != 0 и i % 3 != 0, добавляем i+1 в can_get — команда 3;

3. После обработки всех чисел текущего шага обновляем список ans как can_get.

После выполнения всех 12 операций в ans будут все числа, которых можно достичь за 12 шагов, обходя запрещённое число 22. Подсчёт количества элементов, равных 27, даст количество программ, удовлетворяющих условиям.

# Создаем список возможных чисел на каждом шаге
ans = []
ans.append(3)  # Начальное число 3
# Выполняем 12 шагов (команд)
for operations in range(12):
    can_get = []  # Временный список для чисел, полученных на этом шаге
    for i in ans:
        # Пропускаем число 22, так как оно запрещено
        if i == 22:
            continue
        # Применяем команду 1, если число кратно 3
        if i % 3 == 0:
            can_get.append(i + 2)
        # Применяем команду 2, если число кратно 2
        if i % 2 == 0:
            can_get.append(i + 3)
        # Применяем команду 3, если число не кратно ни 2, ни 3
        if (i % 2 != 0) and (i % 3 != 0):
            can_get.append(i + 1)
    # Обновляем список ans для следующего шага
    ans = can_get
# Подсчитываем количество программ, которые приводят к числу 27
print(ans.count(27))