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

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

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

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

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

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