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

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

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

- — текущее значение на экране;

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

- — номер последней команды, которая была выполнена (0 для первого шага, когда предыдущей команды нет).

1. На каждом шаге мы проверяем, достигли ли количества команд, равного 10:

- если да, добавляем текущее значение в множество s, чтобы фиксировать уникальные результаты, и завершаем текущий путь рекурсии;

2. Если это первый шаг (), разрешены все команды, поэтому вызываем функцию рекурсивно для всех шести команд: прибавление 1, 2, 3 и умножение на 2, 3, 4;

3. Если это не первый шаг, проверяем номер последней команды и разрешаем только команды с номерами, отличающимися на 1:

- Например, если , то на следующем шаге разрешены команды 1 и 3, так как их номера отличаются на 1 от 2;

- Для разрешена только команда 2;

- Для разрешена только команда 5;

- Для промежуточных номеров выполняем оба варианта (влево и вправо), чтобы соблюсти условие различия номеров на 1.

На каждом рекурсивном вызове мы увеличиваем счётчик шагов на 1 и передаём новый номер выполненной команды, чтобы следующий вызов функции мог правильно определить доступные команды. Когда рекурсия достигает 10 шагов, значение добавляется в множество s. После завершения всех рекурсивных веток количество уникальных значений в s даёт ответ на задачу.

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

# Определяем рекурсивную функцию
def f(a, h, c):
    # Если выполнено 10 команд, добавляем результат в множество
    if h == 10:
        s.add(a)
        return
    # Если это первый шаг, можно использовать любую команду
    if c == 0:
        f(a + 1, h + 1, 1)   # прибавляем 1
        f(a + 2, h + 1, 2)   # прибавляем 2
        f(a + 3, h + 1, 3)   # прибавляем 3
        f(a * 2, h + 1, 4)   # умножаем на 2
        f(a * 3, h + 1, 5)   # умножаем на 3
        f(a * 4, h + 1, 6)   # умножаем на 4
    # Если последняя команда была 1, следующий шаг только команда 2
    elif c == 1:
        f(a + 2, h + 1, 2)
    # Если последняя команда была 2, следующий шаг команды 1 и 3
    elif c == 2:
        f(a + 1, h + 1, 1)
        f(a + 3, h + 1, 3)
    # Если последняя команда была 3, следующий шаг команды 2 и 4
    elif c == 3:
        f(a + 2, h + 1, 2)
        f(a * 2, h + 1, 4)
    # Если последняя команда была 4, следующий шаг команды 3 и 5
    elif c == 4:
        f(a + 3, h + 1, 3)
        f(a * 3, h + 1, 5)
    # Если последняя команда была 5, следующий шаг команды 4 и 6
    elif c == 5:
        f(a * 2, h + 1, 4)
        f(a * 4, h + 1, 6)
    # Если последняя команда была 6, следующий шаг только команда 5
    elif c == 6:
                                                                                                     
                                                                                                     
        f(a * 3, h + 1, 5)

# Запускаем рекурсию с начальным числом 1, нулевым количеством шагов и отсутствием предыдущей команды
f(1, 0, 0)

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

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

В динамическом подходе мы моделируем все возможные состояния после каждого шага программы с помощью списка a, где каждый элемент — это пара [значение, номер последней команды].

1. Изначально в списке только одно состояние: [1, ’0’] — число 1 и отсутствие предыдущей команды.

2. Для каждого из 10 шагов:

- Создаём новый список состояний после выполнения текущего шага.

- Для каждого состояния определяем список всех возможных команд: прибавление 1,2,3 и умножение на 2,3,4.

- Если предыдущая команда ’0’ (первый шаг), добавляем все команды в новый список.

- Если предыдущая команда крайняя (1 или 6), добавляем только соседнюю команду, чтобы не выйти за границы.

- Для остальных случаев добавляем две соседние команды: c-1 и c+1.

3. После 10 шагов остаётся множество всех возможных конечных значений. Преобразуем его в множество, чтобы исключить повторения, и считаем длину множества — это и есть количество различных результатов.

# Начальное состояние: число 1, предыдущая команда отсутствует
a = [[1, ’0’]]

# Выполняем 10 шагов программы
for i in range(10):
    n = len(a)
    for j in range(n):
        l = a.pop(0)
        # Список всех возможных команд
        command = [[l[0] + 1, ’1’], [l[0] + 2, ’2’], [l[0] + 3, ’3’],
                   [l[0] * 2, ’4’], [l[0] * 3, ’5’], [l[0] * 4, ’6’]]
        # Первый шаг - все команды доступны
        if l[1] == ’0’:
            for k in range(6):
                a.append(command[k])
        # Крайние команды: только одна соседняя
        elif l[1] == ’1’:
            a.append(command[1])
        elif l[1] == ’6’:
            a.append(command[4])
        # Для остальных команд: добавляем соседние по номерам
        else:
            a.append(command[int(l[1]) - 2])
            a.append(command[int(l[1])])

# Преобразуем все значения в множество, чтобы исключить дубликаты
a = set([j[0] for j in a])

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