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

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

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

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

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

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

- com1 — предпоследняя выполненная команда.

- com2 — последняя выполненная команда.

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

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

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

- Проверяем, не повторяется ли какая-либо команда более двух раз подряд:

- Если com1 == com2 == "1" — команда 1 повторяется дважды, поэтому можно выполнить только команду 2.

- Если com1 == com2 == "2" — команда 2 повторяется дважды, поэтому можно выполнить только команду 1.

- В остальных случаях обе команды доступны, создаем два рекурсивных вызова для команд 1 и 2.

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

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

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

# Рекурсивная функция для перебора всех программ
def f(a, c, com1, com2):
    # Если выполнено 11 команд, добавляем число в множество
    if c == 11:
        d.add(a)
        return
    # Если команда 1 повторяется дважды, выполняем только команду 2
    if com1 == com2 == "1":
        f(a * 2, c + 1, com2, "2")
    # Если команда 2 повторяется дважды, выполняем только команду 1
    elif com1 == com2 == "2":
        f(a + 2, c + 1, com2, "1")
    # Иначе обе команды доступны
    else:
        f(a * 2, c + 1, com2, "2")
        f(a + 2, c + 1, com2, "1")

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

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