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

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

Идея рекурсивного решения заключается в том, чтобы определить функцию f(a, b), которая будет подсчитывать количество программ, преобразующих число в число . Для этого на каждом шаге функции проверяются условия: - Если текущее число стало меньше числа , то дальнейшие команды не приведут к цели, и функция возвращает . - Если равно , значит найден один корректный путь, и функция возвращает . - Если ни одно из условий не выполнено, функция рекурсивно вызывает себя трижды: 1) с аргументом , что соответствует команде «уменьши на 1»; 2) с аргументом , что соответствует команде «уменьши на 4»; 3) с аргументом , что соответствует команде «подели нацело на 2».

Сумма этих трёх вызовов даёт общее количество программ для данного промежутка. Так как траектория должна проходить через числа 56, 30 и 18, мы разбиваем общий путь на этапы: от 60 до 56, от 56 до 30, от 30 до 18 и от 18 до 10, и перемножаем результаты всех этапов.

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

# Перемножаем результаты всех этапов, чтобы учесть прохождение
# через числа 56, 30 и 18, и выводим общее количество программ
print(f(60,56)*f(56,30)*f(30,18)*f(18,10))