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

Пусть — количество программ, которые число 1 преобразуют в число n. Тогда верно следующее утверждение:

— если число не делится на 2.

— если число делится на 2.

Заполним таблицу по данной формуле до 6:

Так как по условию сказано, что траектория должна содержать число 6, значит последующие числа мы можем получать только из 6. Продолжим заполнять таблицу:

Аналогично с 9. Сразу можно сказать, что число 13 нельзя никак получить, так как по условию траектория не должна через него проходить. Значит . Заполним таблицу до конца:

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

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

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

# Функция для подсчета количества программ преобразования a -> b
def f(c, m):
    if c > m or c == 13: # Если число стало больше нужного или 13
        return 0
    if c == m: # Если дошли до нужного числа
        return 1
    return f(c + 2, m) + f(c + 3, m) + f(c * 2, m) # Количество путей до текущего числа

print(f(1, 6) * f(6, 9) * f(9, 15)) # Найдем ответ по условию задачи