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

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

Мы решаем задачу рекурсивно, создавая функцию f(x, y), которая считает количество программ, преобразующих число x в число y. Идея решения состоит в том, что каждая программа — это последовательность команд, а каждая команда уменьшает текущее число на 5 или на 7. Поэтому количество программ, ведущих от x к y, можно выразить через количество программ, ведущих от x-5 к y и от x-7 к y.

1. Сначала проверяем условие: если текущее число x стало меньше целевого y, значит путь невозможен, и мы возвращаем 0.

- Это означает, что мы не можем дальше уменьшать число и достигнуть y.

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

- Это учитывает случай, когда мы достигли нужного числа без лишних шагов.

3. Если ни одно из условий не выполнено (то есть x > y), мы делаем два рекурсивных вызова:

- Первый вызов: f(x-5, y), который соответствует применению команды "вычти 5".

- Второй вызов: f(x-7, y), который соответствует применению команды "вычти 7".

- Сумма результатов этих двух вызовов даёт общее количество программ для текущего x.

Так как в условии задачи требуется, чтобы траектория проходила через число 37, мы делим процесс на два этапа:

1) от 101 до 37,

2) от 37 до 20.

Количество всех программ равно произведению f(101, 37) * f(37, 20), потому что каждая программа из первой части может сочетаться с любой программой из второй части.

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

# Вычисляем количество программ, проходящих через 37
# Сначала считаем пути от 101 до 37
# Затем пути от 37 до 20
# Результат — произведение двух значений
print(f(101, 37) * f(37, 20))