23.08 Прочие прототипы

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

Мы решаем эту задачу с помощью рекурсии, создавая функцию, которая будет подсчитывать количество программ, приводящих число к числу , соблюдая все дополнительные условия.

1. Сначала мы определяем функцию f(a, b, c=0, r=False), где:

- — текущее число на экране,

- — целевое число,

- — номер команды, выполненной на предыдущем шаге (0, если команда еще не была использована),

- — логический флаг, который показывает, встречалось ли число 6 в траектории.

2. Внутри функции проверяем условия, которые запрещают продолжение программы:

- если текущее число стало больше или равно запрещённому числу 18, возвращаем 0, так как такие траектории не подходят;

- если текущее число совпадает с и флаг равен True (т.е. число 6 уже встречалось), возвращаем 1, так как найден корректный путь.

3. После этого проверяем, не достигли ли мы числа 6:

- если , устанавливаем , чтобы зафиксировать факт появления числа 6 в траектории.

4. Далее мы рекурсивно считаем количество программ, вызывая функцию для каждого возможного шага:

- вызов f(a * 2, b, 2, r) соответствует применению команды 2 "умножь на 2 мы фиксируем предыдущую команду как 2;

- вызов f(a * 3, b, 3, r) выполняется только если предыдущая команда не была 1 (команда "увеличь на 4"), что соответствует условию задачи;

- вызов f(a + 4, b, 1, r) выполняется только если предыдущая команда не была 2 (команда "умножь на 2").

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

6. В конце мы вызываем функцию с начальными значениями f(2, 296), чтобы получить ответ.

# Определяем функцию f(a, b, c=0, r=False), где
# a - текущее число, b - целевое число
# c - предыдущая команда, r - флаг наличия числа 6
def f(a, b, c = 0, r = False):
    # Если текущее число превысило целевое или равно запрещённому числу 18,
    # то путь невозможен, возвращаем 0
    if a > b or a == 18:
        return 0
    # Если текущее число совпадает с целевым и число 6 встречалось,
    # значит найден подходящий путь, возвращаем 1
    if a == b and r:
        return 1
    # Если текущее число равно 6, фиксируем факт его появления
    if a == 6:
        r = True

    # Применяем команду 2 "умножь на 2" всегда
    s = f(a * 2, b, 2, r)
    # Применяем команду 3 "умножь на 3", только если предыдущая команда не была 1
    if c != 1:
        s += f(a * 3, b, 3, r)
    # Применяем команду 1 "увеличь на 4", только если предыдущая команда не была 2
    if c != 2:
        s += f(a + 4, b, 1, r)
    # Возвращаем общее количество программ для текущего состояния
    return s

# Вызываем функцию от 2 до 296 и выводим результат
print(f(2, 296))