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

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

Мы используем рекурсивный метод для подсчета всех программ, которые приводят от числа 1 к числу 25, избегая числа 21. Для этого мы определяем функцию f(n, m), которая возвращает количество таких программ. Основная логика функции строится на проверках текущего числа относительно целевого числа и запрещённого числа 21:

1. Сначала проверяем, равно ли текущее число целевому .

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

2. Затем проверяем, превысило ли текущее число целевое или равно запрещённому числу 21.

- Если или , путь невозможен, возвращаем 0.

3. Если ни одно из этих условий не выполнено, мы рассматриваем два возможных действия, которые может выполнить исполнитель:

- Выполнить команду "прибавить 1 что соответствует рекурсивному вызову f(n+1, m).

- Выполнить команду "сделай нечётное что соответствует рекурсивному вызову f(n*2 + 1, m).

Мы складываем результаты этих двух рекурсивных вызовов, чтобы получить общее количество программ для текущего числа . Начальный вызов функции f(1, 25) перебирает все возможные последовательности команд от 1 до 25, соблюдая условие исключения числа 21.

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

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