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

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

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

# Импортируем декоратор lru_cache, чтобы запоминать
# результаты предыдущих вызовов функции и не пересчитывать их заново
from functools import lru_cache

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

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