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

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

Мы будем использовать рекурсивный подход, создавая функцию f(x, y), которая считает количество способов из числа получить число . При реализации функции мы рассматриваем следующие ситуации:

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

- Если текущее число стало меньше , значит достигнут тупик — дальнейшие преобразования не ведут к результату, возвращаем 0.

- В остальных случаях мы рассматриваем все возможные действия:

   - Вычесть 5: вызываем f(x - 5, y)

   - Вычесть 2: вызываем f(x - 2, y)

   - Разделить на 5: вызываем f(x // 5, y), но только если делится на 5 без остатка

Таким образом, на каждом шаге мы суммируем количество программ для всех допустимых действий. Чтобы учесть условие, что траектория должна содержать число 13, мы разбиваем вычисления на два этапа: сначала считаем количество программ от 49 до 13, затем от 13 до 1, и перемножаем результаты, так как любой путь первой части можно соединить с любым путем второй части.

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

# Считаем количество программ от 49 до 13 и от 13 до 1, затем перемножаем
print(f(49, 13) * f(13, 1))