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

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

Идея рекурсивного решения заключается в том, чтобы построить функцию, которая считает количество различных программ, преобразующих число в число . На каждом шаге проверяются условия: если текущее число стало меньше числа , то дальнейшие преобразования невозможны и возвращается ; если совпало с , то найден один корректный путь, и функция возвращает ; если ни одно из условий не выполнено, то функция вызывает саму себя дважды — первый раз с аргументом , что соответствует команде «уменьшить на 2», второй раз с аргументом , что соответствует команде «поделить нацело на 3». Результаты этих двух вызовов складываются, чтобы получить общее количество программ. Таким образом, при вызове функции f(123, 2) она будет рекурсивно перебирать все возможные последовательности команд и возвращать итоговое число способов преобразования.

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

# Запускаем функцию от 123 до 2 и выводим результат
print(f(123,2))