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

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

Мы определяем рекурсивную функцию f(a, c, com), которая строит все допустимые последовательности команд и добавляет полученные результаты в множество d.

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

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

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

- com — тип предыдущей команды:

- "1"— предыдущая команда была сложением (1 или 2).

- "2"— предыдущая команда была умножением (3 или 4).

- ” — начальное состояние, когда команды еще не выполнялись.

2. В функции выполняем следующие действия:

- Проверяем, не превысили ли количество команд 12:

- Если c > 12, прекращаем выполнение функции.

- Проверяем, достигли ли точно 12 команд:

- Если c == 12, добавляем текущее число a во внешнее множество d и выходим из функции.

- Если c < 12, продолжаем выполнять команды. При этом проверяем ограничение на последовательные одинаковые типы команд:

- Если предыдущая команда была сложением (com == "1"), можно выполнять только команды умножения (*2, *3), чтобы не было двух последовательных сложений.

- Если предыдущая команда была умножением (com == "2"), можно выполнять только команды сложения (+1, +3), чтобы не было двух последовательных умножений.

- Если предыдущей команды не было (com == ), можно выполнить любую команду.

3. Создаем пустое множество d для хранения уникальных значений и запускаем рекурсию с начального числа 6, 0 команд и пустой предыдущей командой.

4. После завершения рекурсии выводим размер множества d, который соответствует количеству различных значений.

# Создаем множество для хранения уникальных результатов
d = set()

# Рекурсивная функция для перебора всех программ
def f(a, c, com):
    # Если число команд больше 12, прекращаем выполнение
    if c > 12:
        return 0
    # Если достигнуто ровно 12 команд, добавляем число в множество
    if c == 12:
        d.add(a)
        return
    # Если команд меньше 12, продолжаем выполнение
    if c < 12:
        # Если предыдущая команда была сложением, выполняем только умножение
        if com == "1":
            f(a * 2, c+1, "2")
            f(a * 3, c+1, "2")
        # Если предыдущая команда была умножением, выполняем только сложение
        elif com == "2":
            f(a + 1, c+1, "1")
            f(a + 3, c+1, "1")
        # Если предыдущей команды не было, выполняем все команды
        else:
            f(a + 1, c+1, "1")
            f(a + 3, c+1, "1")
            f(a * 2, c+1, "2")
            f(a * 3, c+1, "2")

# Запускаем рекурсию с начального числа 6, 0 команд, без предыдущей команды
f(6, 0, "")

# Выводим количество уникальных значений, достигнутых за 12 команд
print(len(d))