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

Идея решения:

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

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

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

Решение:

# Функция считает количество программ преобразования a -> b
def f(a, b):
    # Если число меньше целевого или равно запрещённому 7
    if a < b or a == 7:
        return 0
    # Если дошли до целевого числа
    if a == b:
        return 1
    # Считаем все возможные переходы
    return f(a - 1, b) + f(a - 4, b) + f(a // 3, b)

# Условие: траектория проходит через 13
print(f(19, 13) * f(13, 2))