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

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

Мы будем использовать рекурсию для перебора всех возможных траекторий команд:

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

2. Определяем рекурсивную функцию f(st, count, end_count), где st — текущее число, count — количество применённых команд, end_count — общее количество команд.

3. Если count == end_count, добавляем текущее число st в множество A, так как достигли конца программы.

4. Если команд осталось, проверяем знак текущего числа:

- Если st > 0:

- Применяем команду умножить на -2: st * (-2), увеличиваем count на 1.

- Применяем команду вычесть 10, если результат отрицателен (st - 10 < 0), увеличиваем count на 1.

- Если st < 0:

- Применяем команду модуль числа: abs(st), увеличиваем count на 1.

- Применяем команду умножить на -2: st * (-2), увеличиваем count на 1.

5. После всех рекурсивных вызовов множество A содержит все уникальные результаты.

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

# Рекурсивная функция для перебора всех последовательностей команд
def f(st, count, end_count):
    if count == end_count:
        # Добавляем текущее число в множество уникальных результатов
        A.add(st)
    else:
        if st > 0:
            # Команда умножить на -2
            f(st * (-2), count + 1, end_count)
            # Команда вычесть 10, только если результат отрицателен
            if st - 10 < 0:
                f(st - 10, count + 1, end_count)
        if st < 0:
            # Команда модуль числа
            f(abs(st), count + 1, end_count)
            # Команда умножить на -2
            f(st * (-2), count + 1, end_count)

# Запускаем функцию с исходным числом 1 и 10 командами
f(1, 0, 10)

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

Решение через итеративное множество

1. Создаём множество ans с исходным числом 1.

2. Для каждой из 10 команд выполняем следующие шаги:

- Создаём новое множество can_get.

- Для каждого числа i в ans:

* если i > 0:

- добавляем i * (-2);

- если i - 10 < 0, добавляем i - 10;

* если i < 0:

- добавляем abs(i);

- добавляем i * (-2).

- После обработки всех чисел обновляем ans = can_get.

3. В конце размер множества ans даёт количество уникальных результатов.

# Множество для хранения текущих результатов
ans = set()
ans.add(1)

# Последовательно применяем 10 команд
for operations in range(10):
    can_get = set()
    for i in ans:
        if i > 0:
            can_get.add(i * (-2))
            if i - 10 < 0:
                can_get.add(i - 10)
        else:
            can_get.add(abs(i))
            can_get.add(i * (-2))
    ans = can_get

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