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

Стоит сказать, что динамическое решение данной задачи более трудоемкое и занимает большее количество времени для исполнения. Поэтому рекомендуется использовать именно рекурсивную реализацию.

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

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

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

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

- fn — целевое число, которое должно получиться после выполнения всех команд.

- flag — булева переменная, показывающая, была ли достигнута проверочная точка flag_number.

- flag_number — число, через которое должна пройти траектория (в данном случае 15).

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

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

2. Логика работы функции:

- Если текущее число равно целевому fn, количество команд достигло end_count, и флаг flag установлен (число 15 уже встречалось), возвращаем 1 — найден подходящий путь.

- Если текущее число больше целевого или количество команд превышает end_count, возвращаем 0 — путь недопустим.

- Если текущее число равно проверочной точке flag_number, устанавливаем флаг flag = True.

- Рекурсивно считаем количество путей для всех трёх команд:

- st + 1 — прибавить 1.

- st * 2 — умножить на 2.

- st + st * 0.75 — прибавить к числу 0.75 его самого, учитываем только если st % 8 == 0 (для этого умножаем на булеву проверку (st % 8 == 0)).

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

3. Запускаем рекурсию с исходного числа 3, целевого числа 50, флага False, проверочной точки 15, текущего количества команд 0 и общего числа команд 20.

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

# Запуск функции с исходного числа 3 и целевого числа 50
print(f(3, 50, False, 15, 0, 20))

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

Мы используем динамический способ, создавая список ans, где каждая пара (число, флаг) показывает текущее число на экране и информацию о том, достигнута ли проверочная точка 15.

1. Инициализация:

- В список ans добавляем исходное число 3 с флагом 0, что означает, что проверочная точка ещё не достигнута.

2. Основной цикл:

- Для каждой из 20 команд создаём новый список can_get, который будет хранить все возможные значения после применения команд.

- Для каждой пары (a, flag) из ans:

- Если a + 1 == 15, добавляем (a + 1, 1), иначе (a + 1, flag).

- Если a % 8 == 0, проверяем команду 2:

- Если int(a + a * 0.75) == 15, добавляем (int(a + a * 0.75), 1), иначе (int(a + a * 0.75), flag).

- Для команды 3 добавляем (a * 2, flag).

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

3. Подсчёт результата:

- Перебираем все элементы ans, если число равно 50 и флаг равен 1 (т.е. траектория проходила через 15), увеличиваем счётчик otv.

- Выводим otv — количество подходящих программ.

# Динамическое решение
ans = []
ans.append((3, 0))  # Начальное число 3, проверочная точка не достигнута
for operations in range(20):
    can_get = []
    for i in ans:
        a, flag = i
        # Применяем команду 1: прибавить 1
        if a + 1 == 15:
            can_get.append((a + 1, 1))
        else:
            can_get.append((a + 1, flag))
        # Применяем команду 2: прибавить 0.75 числа, если число кратно 8
        if a % 8 == 0:
            if int(a + a * 0.75) == 15:
                can_get.append((int(a + a * 0.75), 1))
            else:
                can_get.append((int(a + a * 0.75), flag))
        # Применяем команду 3: умножить на 2
        can_get.append((a * 2, flag))
    ans = can_get
# Подсчет количества программ, результат которых 50 и проходящих через 15
otv = 0
for i in ans:
    a, flag = i
    if (a == 50) and (flag):
        otv += 1
print(otv)