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

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

Мы определяем функцию f(start, com), где start — текущее число на экране, com — оставшееся количество команд.

1. Создаём пустое множество ans, чтобы хранить все уникальные результаты после выполнения всех команд.

2. В функции проверяем: если com == 0, значит, команд больше нет, добавляем текущее число start в ans.

3. Если команды ещё остались, рекурсивно вызываем функцию:

- сначала с командой «прибавь 2» (start + 2), уменьшив счётчик команд на 1;

- затем с командой «умножь на 2 и прибавь 1» (start * 2 + 1), также уменьшив счётчик команд на 1.

4. После рекурсивных вызовов множество ans будет содержать все уникальные результаты после выполнения 12 команд.

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

# Рекурсивная функция, которая перебирает все варианты применения команд
def f(start, com):
    if com == 0:
        # Добавляем текущее число в множество результатов
        ans.add(start)
        return 0
    # Применяем команду прибавить 2
    f(start + 2, com - 1)
    # Применяем команду умножить на 2 и прибавить 1
    f(start * 2 + 1, com - 1)

# Запускаем функцию от исходного числа 6 с 12 командами
f(6, 12)

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

Решение динамикой

Мы создаём множество ans, в котором будем хранить все возможные числа после выполнения каждой команды.

1. Инициализируем множество ans числом .

2. Для каждой из 12 команд:

- создаём новое множество can_get, куда добавляем все результаты применения двух команд к каждому числу из текущего множества ans:

- число + 2;

- число * 2 + 1.

- присваиваем ans = can_get, чтобы перейти к следующему шагу.

3. После 12 итераций множество ans будет содержать все уникальные результаты, полученные после выполнения всех 12 команд.

# Инициализация множества с исходным числом
ans = set()
ans.add(6)

# Проходим по 12 командам
for cnt in range(12):
    can_get = set()
    # Для каждого числа применяем обе команды
    for i in ans:
        can_get.add(i + 2)
        can_get.add(i * 2 + 1)
    # Обновляем множество возможных чисел
    ans = can_get

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