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

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

Идея рекурсивного решения заключается в построении функции, которая считает количество программ, переводящих число в число . Функция проверяет три условия: - если текущее число больше или равно запрещённому числу 33, то путь невозможен и возвращаем ; - если совпало с , то найден подходящий путь, возвращаем ; - если ни одно из условий не выполнено, вызываем функцию рекурсивно трижды: для команды "прибавить 2 для команды "прибавить 3 для команды "умножь на 4".

Затем суммируем все результаты для всех от 50 до 60, чтобы получить общее количество программ.

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

# Переменная для накопления общего числа программ
c = 0
# Перебираем все целевые числа от 50 до 60 включительно
for i in range(50,61):
    # Добавляем количество программ, которые переводят 12 в i
    c += f(12,i)

# Выводим итоговое количество программ
print(c)