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

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

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

1. a — текущее число на экране.

2. c — количество уже использованных команд.

Мы проверяем два условия:

- Если c == 10, то мы достигли предела команд. В этом случае проверяем, равно ли текущее число a цели (1). Если да, возвращаем 1 (найден путь), иначе 0.

- Если c < 10, мы пробуем три варианта команды: прибавить 4, прибавить 7 и разделить на 2 нацело. Каждый вариант увеличивает c на 1, и мы рекурсивно вызываем функцию для нового числа. Результаты трёх вызовов суммируются, чтобы получить общее количество программ.

# Определяем рекурсивную функцию f(a, c)
# a - текущее число на экране
# c - количество использованных команд
def f(a, c):
    # Проверяем, достигли ли 10 команд
    # Если достигли, проверяем, равно ли число 1
    # Если равно, возвращаем 1 (найден путь), иначе 0
    if c == 10:
        return a == 1
    # Если команд меньше 10, пробуем все три варианта:
    # 1) прибавить 4 и увеличить счетчик команд на 1
    # 2) прибавить 7 и увеличить счетчик команд на 1
    # 3) разделить на 2 нацело и увеличить счетчик команд на 1
    # Складываем количество программ для всех вариантов
    return f(a + 4, c + 1) + f(a + 7, c + 1) + f(a // 2, c + 1)

# Запускаем функцию от исходного числа 1 и нулевого количества команд
# Выводим общее количество программ, которые из числа 1 после 10 команд возвращают 1
print(f(1, 0))

—

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

Мы можем использовать динамический подход, чтобы последовательно строить все состояния после каждой команды. Идея: создаём список a, который хранит все возможные числа после каждой команды.

1. Начинаем с a = [1] — исходное число на экране.

2. Проходим 10 итераций (по количеству команд).

- На каждой итерации берём текущее количество элементов n = len(a).

- Для каждого элемента из списка (берём по индексу j от 0 до n-1), убираем его из списка (pop(0)) и создаём три новых значения:

* прибавляем 4

* прибавляем 7

* делим нацело на 2

- Добавляем эти новые значения в конец списка (append).

3. После всех 10 итераций считаем количество элементов, равных 1 (a.count(1)). Это и есть количество программ, которые после 10 команд вернули число 1.

# Инициализируем список с исходным числом
a = [1]
# Проходим 10 итераций, соответствующих 10 командам
for i in range(10):
    # Сохраняем текущую длину списка
    n = len(a)
    # Проходим по всем текущим элементам
    for j in range(n):
        # Берем первый элемент списка
        l = a.pop(0)
        # Применяем все три команды и добавляем результаты в конец списка
        a.append(l + 4)
        a.append(l + 7)
        a.append(l // 2)
# Подсчитываем, сколько элементов равно 1 после 10 команд
print(a.count(1))