23.06 Количество программ из A в B где траектория вычислений N команда

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

Мы можем решить задачу рекурсивно, определяя функцию f(x, k), которая будет считать все возможные значения, получаемые после применения оставшихся команд к числу . Идея решения заключается в следующем:

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

2. В функции f(x, k) проверяем, сколько команд осталось:

- Если , значит команд больше нет, и текущее значение добавляем в множество a как результат.

- Если , то делаем два рекурсивных вызова:

- f(x - 4, k - 1), что соответствует применению команды "вычесть 4"и уменьшению количества оставшихся команд на 1.

- f(x * -1, k - 1), что соответствует применению команды "умножить на -1"и также уменьшению количества оставшихся команд на 1.

3. После выполнения всех рекурсивных вызовов множество a будет содержать все возможные значения, полученные после применения 10 команд к числу 123.

4. Чтобы посчитать количество неотрицательных результатов, мы перебираем все элементы множества a и считаем те, которые больше или равны 0.

# Создаем множество для хранения всех уникальных значений
a = set()

# Определяем рекурсивную функцию для подсчета всех значений
def f(x, k):
    # Если команд больше нет, добавляем текущее число в множество
    if k == 0:
        a.add(x)
        return 0
    # Применяем команду "вычесть 4" и уменьшаем количество команд на 1
    f(x - 4, k - 1)
    # Применяем команду "умножить на -1" и уменьшаем количество команд на 1
    f(x * -1, k - 1)

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

# Считаем количество неотрицательных чисел в множестве
kol = 0
for i in a:
    if i >= 0:
        kol += 1

# Выводим результат
print(kol)

—

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

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

1. Создаем список a, содержащий текущее множество чисел, начинаем со списка [123].

2. Для каждой из 10 команд (в цикле for i in range(10)) выполняем следующие действия:

- Преобразуем список a в множество и обратно в список, чтобы исключить повторяющиеся значения.

- Сохраняем текущее количество элементов в переменную n.

- Для каждого элемента списка a (от 0 до n-1):

      - Извлекаем первый элемент с помощью pop(0) и сохраняем его в l.

      - Добавляем два новых элемента в конец списка: l - 4 (применение первой команды) и l * (-1) (применение второй команды).

3. После всех 10 итераций получаем множество всех возможных чисел.

4. Считаем количество неотрицательных чисел в множестве с помощью генератора списка и функции len.

# Инициализируем список с исходным числом
a = [123]

# Повторяем процесс для 10 команд
for i in range(10):
    # Убираем повторяющиеся значения
    a = list(set(a))
    # Сохраняем текущее количество элементов
    n = len(a)
    # Для каждого элемента применяем обе команды
    for j in range(n):
        # Извлекаем первый элемент
        l = a.pop(0)
        # Добавляем результат применения команды "вычесть 4"
        a.append(l - 4)
        # Добавляем результат применения команды "умножить на -1"
        a.append(l * (-1))

# Преобразуем список в множество для уникальных значений
a = set(a)

# Считаем количество неотрицательных чисел
print(len([j for j in a if j >= 0]))