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

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

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

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