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

Рекурсия:

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

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

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

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

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

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

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

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

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

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

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

    a[i] = ways

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

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

    # Можно прийти командой Прибавить 2
    ways = b[i-2]

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

    b[i] = ways

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

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

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

    c[i] = ways

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