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

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

Рекурсивный способ решения заключается в построении функции f(a, b), которая считает количество различных программ преобразования числа в число . На каждом шаге функция проверяет условия: если текущее число превысило целевое или оказалось чётным, то такая траектория невозможна и возвращается ; если совпадает с , значит найден правильный путь, возвращается ; если ни одно из условий не выполнено, то функция вызывает саму себя для четырёх возможных переходов. Первый вызов соответствует команде «прибавить 1» (f(a+1, b)), второй — «прибавить 2» (f(a+2, b)), третий — «умножить на 3» (f(a*3, b)), четвёртый — «прибавить до кратного 3», то есть f(a + (3 - a%3), b). Результат вычислений складывается, так как каждый вариант задаёт отдельную программу. Таким образом, при вызове f(3, 77) происходит полный перебор всех допустимых траекторий с учётом ограничения, что на пути не встречаются чётные числа.

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

# Запускаем функцию от 3 до 77 и выводим количество программ
print(f(3,77))