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

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

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

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

2. В функции f(n, c) реализуем проверку:

- если c == 8 (все команды выполнены), то проверяем знак числа:

      - если n >= 0, добавляем n в множество a.

- если c < 8, то выполняем оба возможных действия:

      - вычесть 3 (передаем n-3 в следующий вызов с увеличением счетчика команд на 1)

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

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

3. Запускаем функцию с исходным числом 82 и нулевым счетчиком команд (f(82, 0)). После завершения всех рекурсивных вызовов в множестве a будут храниться все возможные неотрицательные результаты. Выводим это множество, чтобы получить ответ.

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

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

# Запускаем рекурсию с исходного числа 82 и 0 выполненных команд
f(82, 0)

# Выводим множество всех возможных неотрицательных результатов
print(a)