23.03 Количество программ из A в B где траектория вычислений содержит число(-а)

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

Решение через рекурсию заключается в том, чтобы подсчитать количество программ, которые преобразуют число в число . Для этого определяем функцию f(x, y), которая возвращает количество таких программ.

1. Если текущее число совпало с числом , значит найден корректный путь, функция возвращает 1.

2. Если текущее число меньше числа , дальнейшие команды не приведут к , функция возвращает 0.

3. В остальных случаях выполняем рекурсивный подсчет: сумма количества программ при применении каждой из команд. Первая команда уменьшает число на 1, вторая — на 3, третья — берет целую часть от деления на 3. Таким образом, сумма трёх рекурсивных вызовов даст общее количество программ, ведущих из в .

Поскольку траектория должна содержать число 14, общее количество программ, которые из числа 38 приводят к числу 1 через число 14, вычисляется как произведение f(38, 14) * f(14, 1). Первый множитель считает количество программ от 38 до 14, второй — от 14 до 1. Произведение учитывает, что для каждого пути из первой части можно выбрать любой путь из второй части.

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

# Вычисляем общее количество программ от 38 до 1 через 14
print(f(38, 14) * f(14, 1))