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

Решение руками:

Заметим, что исходная число по условию 8. Команд, которые уменьшают число нет. По условию программа должна пройти через число 5. Мы никак не можем попасть в число 5, так как 8 никак нельзя уменьшить, следовательно, таких программ нет и ответ тогда 0.

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

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

1. Проверяем, если текущее число a стало больше b или равно запрещённому числу 20, то такая траектория невозможна, возвращаем 0.

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

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

- один раз с аргументом a+1, что соответствует команде "прибавить 1";

- второй раз с аргументом a*2, что соответствует команде "умножить на 2".

Суммируем результаты этих двух вызовов, чтобы получить общее количество программ для текущего состояния.

Так как условие требует, чтобы траектория проходила через число 5 и не содержала число 20, мы делим решение на два этапа: от 8 до 5 и от 5 до 36. Произведение f(8, 5) * f(5, 36) даст окончательное количество программ, удовлетворяющих всем условиям.

# Определяем рекурсивную функцию f(a, b) для подсчета программ
def f(a, b):
    # Если текущее число стало больше целевого или равно запрещённому числу 20,
    # путь невозможен, возвращаем 0
    if a > b or a == 20:
        return 0
    # Если текущее число совпало с целевым,
    # найден корректный путь, возвращаем 1
    if a == b:
        return 1
    # В остальных случаях считаем все возможные варианты переходов:
    # прибавление 1 и умножение на 2, и складываем результаты
    return f(a + 1, b) + f(a * 2, b)

# Вычисляем общее количество программ, проходящих через число 5 и не содержащих 20
print(f(8, 5) * f(5, 36))

—

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

Мы можем решить задачу динамическим способом, создавая массивы для хранения количества программ для каждого числа на траектории. Разделяем задачу на два этапа: от 8 до 5 и от 5 до 36.

1. Первый этап: от 8 до 5

- Создаем массив a длиной 37 (чтобы включить число 36).

- Записываем a[8] = 1, так как начальное число — 8, существует один способ быть в этом положении.

- Проходим по всем индексам от 9 до 5 включительно:

      - Если число чётное, можем прийти либо командой "+1"из i-1, либо командой "*2"из i//2; суммируем эти значения в a[i].

      - Если число нечётное, можем прийти только командой "+1 добавляем a[i-1].

2. Второй этап: от 5 до 36

- Создаем массив b длиной 37.

- Записываем b[5] = 1, начальное число 5.

- Проходим по всем индексам от 6 до 36 включительно:

      - Пропускаем число 20, так как траектория не должна его содержать.

      - Для чётных чисел добавляем суммы из b[i-1] и b[i//2].

      - Для нечётных чисел добавляем только b[i-1].

Общее количество программ равно произведению a[5] * b[36], так как каждый путь из первой части можно соединить с любым путем из второй части.

# Первый этап: от 8 до 5
a = [0] * (36 + 1)  # Создаем массив для чисел до 36 включительно
a[8] = 1  # Начальное положение — число 8
# Перебираем числа от 9 до 5 включительно
for i in range(9, 5 + 1):
    # Если число чётное, учитываем команды +1 и *2
    if i % 2 == 0:
        a[i] = a[i - 1] + a[i // 2]
    else:
        # Если число нечётное, учитываем только команду +1
        a[i] = a[i - 1]

# Второй этап: от 5 до 36
b = [0] * (36 + 1)  # Создаем массив для чисел до 36 включительно
b[5] = 1  # Начальное положение — число 5
# Перебираем числа от 6 до 36 включительно
for i in range(6, 36 + 1):
    # Пропускаем число 20, так как оно запрещено
    if i == 20:
        continue
    # Если число чётное, учитываем команды +1 и *2
    if i % 2 == 0:
        b[i] = b[i - 1] + b[i // 2]
    else:
        # Если число нечётное, учитываем только команду +1
        b[i] = b[i - 1]

# Выводим итоговое количество программ
print(a[5] * b[36])