23.05 Количество программ из A в B смешанное

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

Мы используем динамическое программирование, чтобы посчитать количество программ, которые приводят число 1 к числу 16, учитывая ограничения на числа 8 и 10. Идея заключается в том, чтобы создать массив, где индекс соответствует числу на экране, а значение в ячейке — количество способов добраться до этого числа, используя команды.

1. Создаем массив a из 17 элементов (от 0 до 16) и заполняем нулями.

2. Инициализируем начальное положение: a[1] = 1, так как мы стартуем с числа 1, существует один способ быть в этом состоянии.

3. Проходим по всем числам от 2 до 16:

- Сначала добавляем количество способов прийти из командой «прибавить 1» (a[i] = a[i-1]).

- Если , добавляем количество способов из командой «прибавить 5» (a[i] += a[i-5]).

- Если четное, добавляем количество способов из командой «умножить на 2» (a[i] += a[i//2]).

- Если , обнуляем ячейку a[i] = 0, так как число 10 запрещено.

- Если , обнуляем все ячейки перед 8 (for j in range(8): a[j] = 0), чтобы гарантировать, что траектория обязательно содержит число 8.

После прохода по всем числам, a[16] содержит количество программ, соответствующих условию задачи.

# Создаем массив для чисел от 0 до 16
a = [0]*17
# Начальное положение: число 1
a[1] = 1
# Проходим по всем числам от 2 до 16
for i in range(2, 17):
    # Добавляем количество способов прийти из i-1 командой "+1"
    a[i] = a[i-1]
    # Добавляем количество способов прийти из i-5 командой "+5", если i>5
    if i > 5:
        a[i] += a[i-5]
    # Добавляем количество способов прийти из i//2 командой "*2" для четных i
    if i % 2 == 0:
        a[i] += a[i//2]
    # Обнуляем ячейку, если i == 10, так как число 10 запрещено
    if i == 10:
        a[i] = 0
    # Если i == 8, обнуляем все предыдущие ячейки, чтобы гарантировать проход через 8
    if i == 8:
        for j in range(8):
            a[j] = 0
# Выводим количество программ, которые преобразуют 1 в 16
print(a[16])

—

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

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

1. Если или , возвращаем 0, так как путь невозможен или число запрещено.

2. Если , возвращаем 1, так как найден корректный путь.

3. В противном случае функция рекурсивно вызывает себя для всех трех команд:

- f(x+1, y) — добавление 1

- f(x*2, y) — умножение на 2

- f(x+5, y) — добавление 5

Так как траектория должна проходить через число 8, мы делим задачу на два этапа: от 1 до 8 и от 8 до 16. Итоговое количество программ равно произведению результатов двух этапов: f(1,8) * f(8,16).

# Определяем рекурсивную функцию f(x, y)
def f(x, y):
    # Если текущее число больше цели или равно запрещенному числу 10
    if x > y or x == 10:
        return 0
    # Если достигли цели, путь корректен
    if x == y:
        return 1
    # Суммируем количество программ для всех трех команд
    return f(x + 1, y) + f(x + 5, y) + f(x * 2, y)

# Вычисляем количество программ, проходящих через 8
print(f(1, 8) * f(8, 16))