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

Рекурсия:

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

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

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

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

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 36 необходимо знать количество траекторий до чисел 34, 18, 12.

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

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

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

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

    # Всегда можно прийти командой Прибавить 2
    ways = a[i-2]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += a[i // 2]

    # Можно прийти командой Умножить на 3 (только для чисел кратных 3)
    if i % 3 == 0:
        ways += a[i // 3]

    a[i] = ways

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

# Перебираем все числа от 29 до 35 включительно
for i in range(29, 35 + 1):
    # Всегда можно прийти командой Прибавить 2
    ways = b[i-2]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += b[i // 2]

    # Можно прийти командой Умножить на 3 (только для чисел кратных 3)
    if i % 3 == 0:
        ways += b[i // 3]
                                                                                                  
                                                                                                  

    b[i] = ways

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