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

Стоит сказать, что динамическое решение данной задачи получается достаточно трудоемким. Поэтому рекомендуется решать эту задачу с помощью рекурсии.

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

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

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

2. Определяем рекурсивную функцию f(start, cnt_step, cnt_nch, max_step), где:

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

- cnt_step — количество применённых команд,

- cnt_nch — количество нечётных чисел в траектории,

- max_step — общее количество команд (10).

3. Если достигли конца программы (cnt_step == max_step) и количество нечётных чисел не превышает 3, добавляем текущее число start в множество A.

4. Если команд больше, чем допустимо, или нечётных чисел больше 3, прекращаем рекурсию.

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

- start + 1, start + 3, start * 3 с соответствующим увеличением cnt_nch, если новое число нечётное.

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

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

# Рекурсивная функция
def f(start, cnt_step, cnt_nch, max_step):
    # Если достигли конца программы и количество нечётных чисел <= 3
    if cnt_step == max_step and cnt_nch <= 3:
        A.add(start)
    # Прекращаем рекурсию, если команд больше допустимого или нечётных чисел > 3
    if cnt_step > max_step or cnt_nch > 3:
        return
    # Применяем команду прибавить 1
    f(start + 1, cnt_step + 1, cnt_nch + ((start + 1) % 2), max_step)
    # Применяем команду прибавить 3
    f(start + 3, cnt_step + 1, cnt_nch + ((start + 3) % 2), max_step)
    # Применяем команду умножить на 3
    f(start * 3, cnt_step + 1, cnt_nch + ((start * 3) % 2), max_step)

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

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

Решение через динамику

1. Создаём множество ans, где элементы — кортежи (число, количество_нечётных); изначально (2,0).

2. Для каждой из 10 команд выполняем:

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

- Для каждого кортежа (ch, chet) проверяем каждую команду:

* Если результат команды допустим (новое количество нечётных ), добавляем его в can_get.

- Обновляем ans = can_get.

3. После 10 шагов множество ans содержит все возможные комбинации числа и количества нечётных.

4. Извлекаем только числа и помещаем их в множество otv для подсчёта уникальных результатов.

# Множество для хранения текущих чисел с количеством нечётных
ans, otv = set(), set()
ans.add((2, 0))

# Последовательно применяем 10 команд
for operations in range(10):
    can_get = set()
    for i in ans:
        ch, chet = i
        # Команда прибавить 1
        if chet + (ch + 1) % 2 <= 3:
            can_get.add((ch + 1, chet + (ch + 1) % 2))
        # Команда прибавить 3
        if chet + (ch + 3) % 2 <= 3:
            can_get.add((ch + 3, chet + (ch + 3) % 2))
        # Команда умножить на 3
        if chet + (ch * 3) % 2 <= 3:
            can_get.add((ch * 3, chet + (ch * 3) % 2))
    ans = can_get

# Извлекаем только числа для подсчёта уникальных результатов
for i in ans:
    a, b = i
    otv.add(a)

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