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

# set может хранить только по одному экземпляру каждого числа,
# то есть все числа внутри будут различными
a = set()
# каждая последовательность команд будет содержать 7 команд
# последовательность команд состоит из чисел 1 2 3
# в алфавите 3СС тоже три числа
# необходимо рассмотреть все семиразрядные числа в 3СС
# каждая из них будет представлять последовательность команд
for i in range(3**7):
    t = i # какая-то последовательность команды (в 10СС)
    n = 1 # тут хранится результат работы данной последовательности
    # перевод последовательности команд в 3СС
    # мы сами переназвали команды, теперь *2 это 0-вая команда и тд
    for j in range(7):
        if t % 3 == 0:
            n*=2
        if t%3==1:
            n = n*2 +1
        if t%3==2:
            n = n*3 + 1
        t //= 3
    # добавляем число в множество, если оно там уже есть,
    # то ничего не произойдет
    a.add(n)
print(len(a))

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

Мы определяем функцию 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))

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

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

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

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

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

4. Если команд осталось, рекурсивно вызываем функцию для каждой из трёх команд:

- прибавить 1: st + 1, увеличивая count на 1;

- умножить на 2: st * 2, увеличивая count на 1;

- прибавить 4: st + 4, увеличивая count на 1.

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

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

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

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

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

Решение через перебор всех комбинаций с использованием itertools

1. Используем функцию product из модуля itertools для генерации всех последовательностей команд длины 8, где каждая команда кодируется числами 1, 2 или 3.

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

3. Для каждой последовательности команд из product:

- начинаем с числа 2;

- последовательно применяем команды:

* если команда 1, прибавляем 1;

* если команда 2, умножаем на 2;

* если команда 3, прибавляем 4;

- добавляем полученный результат в множество c.

4. После обработки всех комбинаций количество различных результатов — это размер множества c.

from itertools import product

# Генерация всех последовательностей команд длины 8
t = product([1, 2, 3], repeat = 8)

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

# Перебираем все последовательности команд
for i in t:
    a = 2  # Начальное число
    for j in i:
        if j == 1:
            a += 1
        elif j == 2:
            a *= 2
        else:
            a += 4
    # Добавляем результат в множество
    c.add(a)

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

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

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

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))

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

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

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

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

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

4. Если команд осталось, проверяем каждую команду и условие кратности 5:

- Если (st + st**2) % 5 != 0, применяем команду прибавить квадрат числа, увеличиваем count на 1.

- Если (st - 12) % 5 != 0, применяем команду вычесть 12, увеличиваем count на 1.

- Если st >= 0 и (st + int(st**0.5)) % 5 != 0, применяем команду прибавить целую часть квадратного корня числа, увеличиваем count на 1.

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

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

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

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

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

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

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

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

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

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

* Если (i + i**2) % 5 != 0, добавляем i + i**2 в can_get.

* Если (i - 12) % 5 != 0, добавляем i - 12.

* Если i >= 0 и (i + int(i**0.5)) % 5 != 0, добавляем i + int(i**0.5).

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

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

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

# Последовательно применяем 5 команд
for operations in range(5):
    can_get = set()
    for i in ans:
        if (i + i ** 2) % 5 != 0:
            can_get.add(i + i ** 2)
        if (i - 12) % 5 != 0:
            can_get.add(i - 12)
        if i >= 0:
            if (i + int(i ** 0.5)) % 5 != 0:
                can_get.add(i + int(i ** 0.5))
    ans = can_get

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

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

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

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

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))

Идея решения:

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

2. Множество s будет хранить уникальные результаты.

3. Если количество команд от 1 до 8, добавляем текущее число в множество.

4. Если команд больше 8, прекращаем рекурсию.

5. Для каждой команды рекурсивно применяем: прибавление и умножение на .

Решение

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

# Рекурсивная функция
def f(a, k = 0):
    # Если количество команд в допустимом диапазоне, добавляем результат
    if 1 <= k <= 8:
        s.add(a)
    # Если команд больше 8, прекращаем рекурсию
    elif k > 8:
        return
    # Применяем команду прибавить 3
    f(a + 3, k + 1)
    # Применяем команду умножить на 4
    f(a * 4, k + 1)

# Запуск функции с исходного числа 2
f(2)

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

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

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))

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

1. Используем рекурсивную функцию , где

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

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

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

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

3. Если , прекращаем рекурсию.

4. Если предыдущая команда нечётная, можно применять только чётные команды (2,4,6). Команду 6 применяем только если чётное.

5. Если предыдущая команда чётная, можно применять только нечётные команды (1,3,5).

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

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

# Рекурсивная функция
def f(a, c = 0.5, k = 0):
    if 1 <= k <= 8:
        s.add(a)
    elif k > 8:
        return 0

    if c % 2 != 0:  # Предыдущая команда нечётная, используем чётные
        f(a + 7, 2, k + 1)
        f(a * 2, 4, k + 1)
        if a % 2 == 0:  # Команду 6 можно применять только для чётных
            f(int(a * 1.5), 6, k + 1)

    if c % 2 != 1:  # Предыдущая команда чётная, используем нечётные
        f(a + 3, 1, k + 1)
        f(a + 1, 3, k + 1)
        f(a * 4, 5, k + 1)

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

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

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

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))

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

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

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

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

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

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

3. Первую команду всегда можно выполнить.

4. Вторую команду выполняем только если предыдущая команда была не вторая.

5. Третью команду выполняем только если предыдущая команда была не третья.

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

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

# Рекурсивная функция
def f(a, c=0, k=0):
    if k == 9:
        s.add(a)
        return
    # Первую команду можно всегда
    f(a + 6, 1, k + 1)
    # Вторую команду, если предыдущая не была 2
    if c != 2:
        f(a + 9, 2, k + 1)
    # Третью команду, если предыдущая не была 3
    if c != 3:
        f(a * 3, 3, k + 1)

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

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

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

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

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

- — целевое число,

- — номер команды, выполненной на предыдущем шаге.

2. Если , возвращаем 0 (превышено целевое число).

3. Если , возвращаем 1 (найдена программа, ведущая к цели).

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

5. В остальных случаях можно применить любую команду:

- (команда 1)

- (команда 2)

- (команда 3)

def f(a, b, c=0):
    # a - текущее число на экране
    # b - целевое число
    # c - номер команды, выполненной на предыдущем шаге (0 означает, что команды ещё не было)

    if a > b:
        # Если текущее число больше целевого, пути нет
        return 0

    if a == b:
        # Если текущее число равно целевому, найден один путь
        return 1

    if c == 2:
        # Если предыдущая команда была 2 (умножить на 2),
        # следующая обязательно должна быть команда 3 (умножить на 3)
        return f(a * 3, b, 3)

    # В остальных случаях можно применить любую из трёх команд:
    # 1. прибавить 1
    # 2. умножить на 2
    # 3. умножить на 3
    return f(a + 1, b, 1) + f(a * 2, b, 2) + f(a * 3, b, 3)

# Запускаем функцию с исходным числом 8, целевым числом 123
print(f(8, 123))

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

Мы используем рекурсивную функцию для перебора всех возможных траекторий выполнения команд. Функция f(a, c, k) имеет три параметра: a — текущее число на экране, c — номер команды, которая была использована на предыдущем шаге, и k — количество уже совершённых команд.

1. Если количество совершённых команд k равно 10, проверяем, является ли текущее число a натуральным (больше или равно 1). Если да, добавляем его в множество s для хранения различных результатов. Затем возвращаемся, чтобы исследовать другие варианты.

2. Вызываем рекурсивно функцию для каждой команды:

- Команда 1: прибавляем 8 к текущему числу и увеличиваем счётчик команд на 1, помечая предыдущую команду как 1.

- Команда 2: вычитаем 4, увеличиваем счётчик команд на 1, помечаем предыдущую команду как 2.

- Команда 3: делим на 2 только если текущее число чётное и предыдущая команда не была 3, увеличиваем счётчик команд на 1 и помечаем предыдущую команду как 3.

Таким образом, функция перебирает все возможные комбинации команд, учитывая ограничения, и собирает все различные натуральные числа, которые могут получиться после 10 команд.

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

# Рекурсивная функция для перебора всех траекторий
def f(a, c = 0, k = 0):
    # Если выполнено ровно 10 команд
    if k == 10:
        # Если число натуральное, добавляем в множество результатов
        if a >= 1:
            s.add(a)
        return 0
    # Применяем команду 1: прибавляем 8
    f(a + 8, 1, k + 1)
    # Применяем команду 2: вычитаем 4
    f(a - 4, 2, k + 1)
    # Применяем команду 3: делим на 2, если число четное и команда не повторяется
    if c != 3 and a % 2 == 0:
        f(a // 2, 3, k + 1)

# Запускаем рекурсивный перебор с начального числа 16
f(16)

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