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

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

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

1. Создаем пустое множество a = set(), которое будет хранить все уникальные результаты. Множество автоматически исключает дубликаты, поэтому если одно и то же число получится разными способами, оно будет учтено только один раз.

2. Определяем функцию f(n, c):

- Проверка количества команд: если c == 13, значит мы выполнили ровно 13 команд. В этом случае:

      - Добавляем текущее число n в множество a, используя a.add(n).

- Иначе: если команд меньше 13, продолжаем рекурсивный перебор всех вариантов команд:

      - Вызываем f(n+1, c+1), что соответствует выполнению команды «прибавить 1».

      - Вызываем f(n*3, c+1), что соответствует выполнению команды «умножить на 3».

      - Вызываем f(n*2, c+1), что соответствует выполнению команды «умножить на 2».

3. Запускаем функцию с начальными значениями f(7, 0), где 7 — исходное число, а 0 — количество выполненных команд.

4. После завершения рекурсивных вызовов множество a будет содержать все уникальные числа, которые можно получить после 13 команд. Чтобы узнать количество различных результатов, выводим длину множества через print(len(a)).

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

# Определяем рекурсивную функцию f(n, c)
# n — текущее число на доске
# c — количество выполненных команд
def f(n, c):
    # Если выполнено ровно 13 команд,
    # добавляем текущее число в множество результатов
    if c == 13:
        a.add(n)
    else:
        # Иначе продолжаем выполнение рекурсивно для всех трех команд
        # 1) Прибавляем 1 и увеличиваем счетчик команд на 1
        f(n+1, c+1)
        # 2) Умножаем на 3 и увеличиваем счетчик команд на 1
        f(n*3, c+1)
        # 3) Умножаем на 2 и увеличиваем счетчик команд на 1
        f(n*2, c+1)

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

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