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

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

Решение кодом через рекурсию заключается в том, что мы создаём функцию f(x, y, is_8=0, is_13=0), которая считает количество программ, преобразующих число в число , с учётом того, встречались ли уже числа 8 или 13 в траектории.

1. В начале функции мы проверяем, достигло ли текущее число числа 8 или 13:

- Если , то устанавливаем is_8 = 1, что означает, что число 8 встречено на траектории.

- Если , то устанавливаем is_13 = 1, что означает, что число 13 встречено на траектории.

2. Далее проверяем базовые условия завершения рекурсии:

- Если текущее число превысило целевое число , значит этот путь не приведёт к цели, и возвращаем 0.

- Если текущее число равно целевому числу , проверяем условие задачи о траектории: число 8 и 13 должны встречаться не одновременно и не отсутствовать полностью. Для этого проверяем is_8 != is_13. Если условие выполнено, возвращаем 1 — найден корректный путь.

3. Если текущее число меньше , продолжаем рекурсию:

- Вызываем функцию с аргументом , что соответствует команде 1 «прибавить 1».

- Вызываем функцию с аргументом , что соответствует команде 2 «умножить на 2».

- Вызываем функцию с аргументом , что соответствует команде 3 «прибавить 2».

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

4. Запускаем функцию для исходного числа 3 и целевого числа 23 и выводим результат.

# Определяем рекурсивную функцию подсчета программ
def f(x, y, is_8 = 0, is_13 = 0):
    # Проверяем, достигли ли числа 8
    if x == 8:
        is_8 = 1
    # Проверяем, достигли ли числа 13
    if x == 13:
        is_13 = 1

    # Если текущее число больше целевого, путь невозможен
    if x > y:
        return 0
    # Если достигли целевого числа, проверяем условие по траектории
    if x == y and is_8 != is_13:
        return 1
    # Если число меньше целевого, суммируем количество программ для всех команд
    if x < y:
        return f(x + 1, y, is_8, is_13) + f(x * 2, y, is_8, is_13) + f(x + 2, y, is_8, is_13)
    return 0

# Вычисляем количество программ от 3 до 23, учитывая условие про числа 8 и 13
print(f(3, 23))