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

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

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

- если текущее число больше или равно запрещённым числам 42 или 56, путь невозможен и функция возвращает 0; - если текущее число совпало с целевым , значит найден корректный путь и функция возвращает 1; - в остальных случаях функция вызывает саму себя четыре раза, соответствуя четырём командам: прибавляем 2, прибавляем 5, умножаем на 3 и прибавляем до ближайшего кратного 2 (вычисляется как ), затем суммируем результаты этих вызовов, чтобы получить общее количество программ.

Так как в условии задачи траектория должна содержать числа 15 и 23, а запрещены числа 42 и 56, для подсчёта общего количества программ решение разделяется на три этапа: от 4 до 15, от 15 до 23 и от 23 до 66. Результаты этапов перемножаются, так как для каждого пути первой части можно выбрать любой путь из второй и третьей частей. Для ускорения рекурсии используется декоратор lru_cache, который запоминает уже вычисленные значения функции.

# Импортируем lru_cache для запоминания результатов рекурсивных вызовов
from functools import lru_cache

# Определяем рекурсивную функцию f(a, b) с декоратором lru_cache
@lru_cache(None)
def f(a,b):
    # Если текущее число больше целевого или равно запрещённым числам 42 или 56,
    # путь невозможен, возвращаем 0
    if a > b or a == 42 or a == 56:
        return 0
    # Если текущее число совпало с целевым числом b,
    # значит найден подходящий путь, возвращаем 1
    if a == b:
        return 1
    # В остальных случаях считаем все возможные переходы:
    # 1) прибавить 2
    # 2) прибавить 5
    # 3) умножить на 3
    # 4) прибавить до ближайшего кратного 2 (не ноль)
    # Складываем количество способов из всех этих переходов
    return f(a+2,b) + f(a+5,b) + f(a*3,b) + f(a+(2-a%2),b)

# Вычисляем общее количество программ с учётом обязательных чисел в траектории
# Считаем отдельно путь от 4 до 15, от 15 до 23 и от 23 до 66, затем перемножаем результаты
print(f(4,15) * f(15,23) * f(23,66))