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

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

Рекурсивный способ решения

Мы определяем рекурсивную функцию f(st, fn, count_2, count_3), которая подсчитывает количество программ, ведущих из числа st в число fn, учитывая сколько раз уже использовались команды 2 и 3.

1. В функции проверяем:

- Если текущее число st равно целевому числу fn и количество использований команды 3 больше, чем команды 2, возвращаем 1 — программа подходит.

- Если st больше fn, программа не подходит, возвращаем 0.

2. Создаём рекурсивные вызовы для каждой команды:

- x = f(st + 3, fn, count_2, count_3) — прибавление 3 не меняет счетчики команд 2 и 3.

- y = f(st * 2, fn, count_2 + 1, count_3) — умножение на 2 увеличивает счетчик команды 2 на 1.

- Для команды 3 создаём массив из 10 элементов z[i], каждый элемент соответствует добавлению цифры от 0 до 9: st * 10 + i, увеличивая счетчик команды 3 на 1.

3. Возвращаем сумму результатов всех возможных веток: return x + y + sum(z).

4. Запускаем функцию с начального числа 1 и счетчиков команд 2 и 3 равных нулю. Выводим результат.

# Рекурсивная функция подсчета количества программ
def f(st, fn, count_2, count_3):
    # Если текущее число равно целевому и команда 3 встречается чаще, программа подходит
    if st == fn and count_3 > count_2:
        return True
    # Если текущее число больше целевого, программа невозможна
    if st > fn:
        return False
    # Применяем команду 1: прибавляем 3
    x = f(st + 3, fn, count_2, count_3)
    # Применяем команду 2: умножаем на 2, увеличиваем счетчик команды 2
    y = f(st * 2, fn, count_2 + 1, count_3)
    # Применяем команду 3: приписываем любую цифру от 0 до 9 справа
    z = [0] * 10
    for i in range(10):
        z[i] = f(st * 10 + i, fn, count_2, count_3 + 1)
    # Возвращаем сумму всех возможных вариантов
    return x + y + sum(z)

# Вычисляем и выводим количество подходящих программ
print(f(1, 48, 0, 0))

Динамический способ решения

Динамический способ использует множество ans, где храним кортежи (текущее число, счетчик команды 2, счетчик команды 3) для всех возможных состояний:

1. Инициализируем ans = set() и добавляем стартовое состояние (1, 0, 0).

2. Задаем переменную otv = 0 для подсчета подходящих программ.

3. Выполняем цикл с достаточно большим числом итераций (например, 1000):

- Создаем пустое множество can_get для хранения новых состояний.

- Для каждого состояния i из ans:

- Распаковываем a, cnt_2, cnt_3.

- Если a == 48 и cnt_3 > cnt_2, увеличиваем otv на 1 и продолжаем.

- Применяем команду 1: если a + 3 <= 48, добавляем новое состояние.

- Применяем команду 2: если a * 2 <= 48, добавляем новое состояние с увеличением счетчика команды 2.

- Применяем команду 3: приписываем цифры 0–9 справа, если результат не превышает 48, добавляем новое состояние с увеличением счетчика команды 3.

- Если can_get пуст, прекращаем цикл.

- Иначе присваиваем ans = can_get для следующей итерации.

4. После завершения цикла выводим otv — количество подходящих программ.

# Инициализация множества для текущих состояний
ans = set()
# Стартовое состояние: число 1, счетчики команд 2 и 3 равны 0
ans.add((1, 0, 0))
# Переменная для подсчета подходящих программ
otv = 0

# Основной цикл перебора возможных операций
for operations in range(1000):
    # Множество для хранения новых состояний после текущей итерации
    can_get = set()
    # Перебираем все текущие состояния
    for i in ans:
        a, cnt_2, cnt_3 = i
        # Если достигли числа 48 и команда 3 встречается чаще команды 2, считаем программу
        if (a == 48) and (cnt_2 < cnt_3):
            otv += 1
            continue
        # Применяем команду 1: прибавляем 3
        if a + 3 <= 48:
            can_get.add((a + 3, cnt_2, cnt_3))
        # Применяем команду 2: умножаем на 2
        if a * 2 <= 48:
            can_get.add((a * 2, cnt_2 + 1, cnt_3))
        # Применяем команду 3: приписываем цифры 0–9 справа
        for j in range(10):
            new_numb = int(str(a) + str(j))
            if new_numb <= 48:
                can_get.add((new_numb, cnt_2, cnt_3 + 1))
    # Если новые состояния не получены, завершаем цикл
    if len(can_get) == 0:
        break
    # Обновляем текущее множество состояний
    ans = can_get

# Выводим количество подходящих программ
print(otv)