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

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

Мы будем использовать рекурсивный способ решения, чтобы подсчитать все возможные результаты после выполнения ровно 6 команд. Идея решения такова: мы определяем функцию f(n, c), где n — текущее число на доске, а c — количество уже совершённых команд.

1. Если количество совершённых команд c достигло 6, то мы добавляем текущее число n в множество результатов a. Множество автоматически исключает повторения, поэтому каждый уникальный результат сохраняется один раз.

2. Если количество команд меньше 6, мы вызываем функцию рекурсивно для трёх возможных команд:

- прибавить 1 к числу (n+1) и увеличить счётчик команд на 1 (c+1);

- прибавить 10 к числу (n+10) и увеличить счётчик команд на 1;

- умножить число на 3 (n*3) и увеличить счётчик команд на 1.

3. После того как все рекурсивные вызовы завершатся, множество a будет содержать все различные результаты, которые можно получить после 6 команд. Длина множества (len(a)) и будет ответом на задачу.

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

# Определяем рекурсивную функцию f(n, c)
# n - текущее число на доске
# c - количество уже выполненных команд
def f(n, c):
    # Если выполнено ровно 6 команд,
    # добавляем текущее число в множество результатов
    if c == 6:
        a.add(n)
    else:
        # Иначе, для каждого из трёх вариантов команд
        # выполняем рекурсивный вызов с увеличением счётчика команд на 1
        f(n+1, c+1)   # Команда "прибавить 1"
        f(n+10, c+1)  # Команда "прибавить 10"
        f(n*3, c+1)   # Команда "умножить на 3"

# Запускаем рекурсивный перебор, начиная с числа 8 и 0 совершённых команд
f(8, 0)

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