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

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

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

1. Создаем список ans и добавляем начальное состояние: число 1, флаг 0 (число 13 пока не встречалось).

2. Для каждой из 9 команд делаем следующие шаги:

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

- Для каждой пары (a, flag) из текущего списка ans проверяем:

- Если число равно 11, пропускаем этот вариант, так как траектория через 11 запрещена.

- Для каждой команды вычисляем новое число и обновляем флаг, если новое число равно 13.

- Добавляем новые пары((новое число, новый флаг) в can_get.

- После обработки всех пар обновляем ans новым списком can_get.

3. После 9 шагов перебора считаем количество пар, где число равно 28 и флаг равен 1 (число 13 встречалось).

# Инициализация списка с начальным состоянием
ans = []
ans.append((1, 0))  # (текущее число, флаг посещения 13)

# Перебор всех 9 команд
for operations in range(9):
    can_get = []
    for i in ans:
        a, flag = i
        if a == 11:
            continue  # Пропускаем состояния с числом 11
        # Применяем команду +3
        if a + 3 == 13:
            can_get.append((a + 3, 1))
        else:
            can_get.append((a + 3, flag))
        # Применяем команду +1
        if a + 1 == 13:
            can_get.append((a + 1, 1))
        else:
            can_get.append((a + 1, flag))
        # Применяем команду умножение на 2
        if 2 * a == 13:
            can_get.append((2 * a, 1))
        else:
            can_get.append((2 * a, flag))
    ans = can_get

# Подсчет количества программ, достигающих 28 с посещением 13
otv = 0
for i in ans:
    a, flag = i
    if (a == 28) and (flag):
        otv += 1
print(otv)

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

Мы определяем функцию f(st, fn, flag, flag_number, exit_number, count, end_count), которая рекурсивно проверяет все программы:

1. Аргументы функции:

- st — текущее число на экране.

- fn — целевое число (28).

- flag — флаг, встречалось ли число 13 в траектории.

- flag_number — число 13, которое должно встретиться.

- exit_number — число 11, через которое проходить нельзя.

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

- end_count — общее количество команд (9).

2. Логика функции: - Если st == fn, count == end_count и flag=True, возвращаем 1 (найден подходящий путь).

- Если st > fn или count > end_count или st == exit_number, возвращаем 0 (недопустимый путь).

- Если st == flag_number, устанавливаем flag=True.

- Рекурсивно вызываем функцию для каждой команды (+1, +3, умножить на 2) с увеличением счетчика команд на 1.

- Суммируем результаты трех рекурсий и возвращаем.

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

# Запуск рекурсии с начального числа 1
print(f(1, 28, False, 13, 11, 0, 9))