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

Исполнитель Лето преобразует число, записанное на доске. У исполнителя есть две команды:

1. Прибавить 2 2. Умножить на 2

Программа для исполнителя Лето — это последовательность команд. Сколько различных результатов можно получить из исходного числа 3 в ходе исполнения программы, содержащей ровно 8 команд?

—

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

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

1. На каждом вызове функции проверяем условие завершения: - если c == 8, это значит, что выполнено ровно 8 команд, и текущий результат n добавляется в множество a, чтобы учесть его как один из возможных результатов; - если c < 8, мы продолжаем рекурсивно применять команды.

2. Для рекурсивного перехода применяем обе доступные команды: - вызываем f(n+2, c+1), что соответствует прибавлению 2 к текущему числу и увеличению счётчика команд на 1; - вызываем f(n*2, c+1), что соответствует умножению текущего числа на 2 и увеличению счётчика команд на 1.

3. После завершения всех рекурсивных вызовов множество a будет содержать все уникальные числа, которые можно получить из числа 3 с помощью ровно 8 команд. Количество различных результатов вычисляется с помощью функции len(a).

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

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

# Запускаем рекурсивный перебор с начальным числом 3 и 0 выполненных команд
f(3, 0)
# Выводим количество уникальных результатов после 8 команд
print(len(a))