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

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

1. Введём рекурсивную функцию , где:

- — текущее число на экране,

- — номер предыдущей команды,

- — количество выполненных команд.

2. Если , добавляем в множество .

3. Если предыдущая команда была сложением (1 или 2), на следующем шаге разрешены только команды умножения (3 или 4), и наоборот.

4. Начальное значение , чтобы первый шаг мог использовать любую команду.

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

# Рекурсивная функция
def f(a, c=0, k=0):
    if k == 18:
        s.add(a)
        return
    # Если предыдущая команда не была сложением, можно сложить
    if c != 1 and c != 2:
        f(a + 3, 1, k + 1)
        f(a + 5, 2, k + 1)
    # Если предыдущая команда не была умножением, можно умножить
    if c != 3 and c != 4:
        f(a * 2, 3, k + 1)
        f(a * 3, 4, k + 1)

# Запуск рекурсии от исходного числа 35
f(35)

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