23.07 Количество результатов выполнения программ

Рекурсивное решение:

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

1. Если количество совершённых команд k равно 10, проверяем, является ли текущее число a натуральным (больше или равно 1). Если да, добавляем его в множество s для хранения различных результатов. Затем возвращаемся, чтобы исследовать другие варианты.

2. Вызываем рекурсивно функцию для каждой команды:

- Команда 1: прибавляем 8 к текущему числу и увеличиваем счётчик команд на 1, помечая предыдущую команду как 1.

- Команда 2: вычитаем 4, увеличиваем счётчик команд на 1, помечаем предыдущую команду как 2.

- Команда 3: делим на 2 только если текущее число чётное и предыдущая команда не была 3, увеличиваем счётчик команд на 1 и помечаем предыдущую команду как 3.

Таким образом, функция перебирает все возможные комбинации команд, учитывая ограничения, и собирает все различные натуральные числа, которые могут получиться после 10 команд.

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

# Рекурсивная функция для перебора всех траекторий
def f(a, c = 0, k = 0):
    # Если выполнено ровно 10 команд
    if k == 10:
        # Если число натуральное, добавляем в множество результатов
        if a >= 1:
            s.add(a)
        return 0
    # Применяем команду 1: прибавляем 8
    f(a + 8, 1, k + 1)
    # Применяем команду 2: вычитаем 4
    f(a - 4, 2, k + 1)
    # Применяем команду 3: делим на 2, если число четное и команда не повторяется
    if c != 3 and a % 2 == 0:
        f(a // 2, 3, k + 1)

# Запускаем рекурсивный перебор с начального числа 16
f(16)

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