23.06 Количество программ из A в B где траектория вычислений N команда

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

Идея рекурсивного решения заключается в том, что мы создаём функцию, которая перебирает все возможные последовательности команд и добавляет результаты в множество. Каждая команда обозначена числом: 1 — прибавить 2, 2 — прибавить 5, 3 — умножить на 2. Мы используем параметр k, чтобы отслеживать количество выполненных команд, и параметр r, чтобы запомнить номер команды, выполненной на предыдущем шаге, так как повторять её нельзя.

1. Создаём пустое множество s, в котором будут храниться все полученные результаты. 2. Определяем функцию f(a, k=0, r=0): - a — текущее число на экране, - k — количество выполненных команд, - r — номер команды, выполненной на предыдущем шаге. 3. В функции проверяем условие окончания рекурсии: если k == 13, значит выполнено 13 команд, добавляем текущее число a в множество s и возвращаем управление. 4. Для каждой команды проверяем, не совпадает ли её номер с предыдущей (r): - если предыдущая команда не 1, вызываем рекурсию с a + 2, увеличивая счётчик команд на 1 и устанавливая r = 1, - если предыдущая команда не 2, вызываем рекурсию с a + 5, увеличивая счётчик команд на 1 и устанавливая r = 2, - если предыдущая команда не 3, вызываем рекурсию с a * 2, увеличивая счётчик команд на 1 и устанавливая r = 3. 5. После завершения рекурсий выводим количество элементов множества s, которое и будет количеством различных результатов.

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

# Определяем рекурсивную функцию f(a, k=0, r=0)
def f(a, k=0, r=0):
    # Если выполнено 13 команд, добавляем текущее число в множество
    if k == 13:
        s.add(a)
        return
    # Если предыдущая команда не была 1, выполняем команду "прибавить 2"
    if r != 1:
        f(a + 2, k + 1, 1)
    # Если предыдущая команда не была 2, выполняем команду "прибавить 5"
    if r != 2:
        f(a + 5, k + 1, 2)
    # Если предыдущая команда не была 3, выполняем команду "умножить на 2"
    if r != 3:
        f(a * 2, k + 1, 3)

# Запускаем рекурсивное вычисление, начиная с числа 8
f(8)

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