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

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

1. Создаём рекурсивную функцию, которая принимает:

- текущее число ,

- счётчик команд ,

- номер последней выполненной команды (чтобы не повторять её на следующем шаге).

2. Если выполнено 20 команд (), добавляем текущее число в множество .

3. Если количество команд меньше 20:

- Проверяем последнюю выполненную команду .

- Для каждой команды, не совпадающей с предыдущей, вызываем рекурсивно функцию с увеличенным счётчиком команд и обновлённым числом .

4. Множество хранит все уникальные результаты после 20 команд.

5. Вызов функции начинается с числа 2 и с параметром , что означает отсутствие предыдущей команды.

from functools import lru_cache
@lru_cache(None)

# Рекурсивная функция для подсчета уникальных результатов
def f(a, k, last = 0):
    # a - текущее число, k - количество выполненных команд, last - последняя команда
    if k == 20:
        s.add(a)  # достигли 20 команд, добавляем результат
    if k < 20:
        # Если предыдущей команды не было, можно применять любую
        if last == 0:
            f(a + 1, k + 1, 1)
            f(a - 2, k + 1, 2)
            f(a * 3, k + 1, 3)
        # Если предыдущая команда была 1, применяем только 2 или 3
        if last == 1:
            f(a - 2, k + 1, 2)
            f(a * 3, k + 1, 3)
        # Если предыдущая команда была 2, применяем только 1 или 3
        if last == 2:
            f(a + 1, k + 1, 1)
            f(a * 3, k + 1, 3)
        # Если предыдущая команда была 3, применяем только 1 или 2
        if last == 3:
            f(a + 1, k + 1, 1)
            f(a - 2, k + 1, 2)

# Множество для хранения всех уникальных результатов
s = set()
# Запуск функции с исходного числа 2
f(2, 0)
# Количество различных результатов программы
print(len(s))