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

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

Определим функцию f(a, b), которая будет вызывать саму себя. Она подсчитает количество программ, преобразующих число a в b. Функция возвращает:

• 0, если a > b или если в процессе встречается запрещённое число 14, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
• 1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
• сумму значений для трёх возможных переходов (прибавление 1, прибавление 3, умножение на 2), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

Так как нужно, чтобы траектория содержала число 9, но не содержала число 14, то общее количество программ равно произведению f(1, 9) и f(9, 20). Первая часть считает количество способов дойти от 1 до 9, вторая — от 9 до 20, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

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

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа, опираясь на подсчеты для предыдущих значений. Для подсчета количества траекторий до числа 20 необходимо знать количество траекторий до чисел 19, 10 (для команды умножения на 2) и 17 .

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1, i//2 (для четных чисел) и i-3.

По условию траектория не должна содержать число 14, поэтому при подсчете количества траекторий значение в ячейке с индексом 14 должно остаться 0. Также по условию траектория должна содержать число 9. Для этого разделим вычисления на два независимых этапа: из 1 в 9, из 9 в 20. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 1 до 9 (с обязательным исключением числа 14)
# Создаем массив для хранения количества путей до чисел от 0 до 9
# a[i] - количество программ, которые преобразуют число 1 в число i
a = [0] * (9 + 1)
a[1] = 1  # Исходное положение - только один способ быть в числе 1

# Перебираем все числа от 2 до 9 включительно
for i in range(2, 9 + 1):
    if i == 14:
        continue  # Пропускаем запрещенное число согласно условию задачи

    # Для всех чисел учитываем команду +1
    ways = a[i - 1]

    # Для четных чисел добавляем команду *2
    if i % 2 == 0:
        ways += a[i // 2]

    # Для чисел >= 4 добавляем команду +3
    if i >= 4:
        ways += a[i - 3]

    a[i] = ways

# Второй этап: от 9 до 20 (также исключаем число 14)
# Массив для чисел от 0 до 20
# b[i] - количество программ, которые преобразуют число 9 в число i
b = [0] * (20 + 1)
b[9] = 1  # Начинаем из числа 9, которое должно быть в траектории

# Перебираем все числа от 10 до 20 включительно
for i in range(10, 20 + 1):
    if i == 14:
        continue  # Пропускаем запрещенное число согласно условию задачи

    # Для всех чисел учитываем команду +1
    ways = b[i - 1]

    # Для четных чисел добавляем команду *2
    if i % 2 == 0:
        ways += b[i // 2]

                                                                                                  
                                                                                                  
    # Для чисел >= 12 добавляем команду +3
    if i >= 12:
        ways += b[i - 3]

    b[i] = ways

# Общее количество программ равно произведению путей до 9 и от 9 до 20
print(a[9] * b[20])