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

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

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

1. — текущее число на экране;

2. — целевое число;

3. — номер команды, выполненной на предыдущем шаге (по умолчанию , если это старт);

4. — флаг, указывающий, что число 21 уже встречено в траектории;

5. — флаг, указывающий, что число 68 уже встречено в траектории.

Логика работы функции:

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

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

2. Проверяем, совпадает ли текущее число с целевым, и встречены ли оба числа 21 и 68.

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

3. Обновляем флаги наличия чисел 21 и 68:

- Если , устанавливаем .

- Если , устанавливаем .

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

- Если предыдущая команда была 1 или 3, разрешена только команда 2.

- Если предыдущая команда была 2, разрешены команды 1 и 3.

- Если это первый шаг (), разрешены все три команды.

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

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

Таким образом, при запуске функции f(1, 824) она рекурсивно переберет все возможные последовательности команд, учитывая ограничения на смену команд и наличие чисел 21 и 68 в траектории, и вернет общее количество корректных программ.

# Определяем рекурсивную функцию f(a, b, c=0, r1=False, r2=False)
# a — текущее число, b — целевое число
# c — номер предыдущей команды, r1 и r2 — флаги наличия чисел 21 и 68
def f(a, b, c = 0, r1 = False, r2 = False):
    # Если текущее число превысило целевое,
    # путь невозможен, возвращаем 0
    if a > b:
        return 0
    # Если достигли целевого числа и оба числа 21 и 68 уже встречены,
    # то путь корректен, возвращаем 1
    if a == b and r1 and r2:
        return 1
    # Обновляем флаги наличия чисел 21 и 68
    if a == 21:
        r1 = True
    if a == 68:
        r2 = True

    # Проверяем предыдущую команду и разрешенные следующие шаги
    if c == 1 or c == 3:
        # Если предыдущая команда 1 или 3, разрешена только команда 2
        return f(a + 3, b, 2, r1, r2)
    if c == 2:
        # Если предыдущая команда 2, разрешены команды 1 и 3
        return f(a + 1, b, 1, r1, r2) + f(a * 4, b, 3, r1, r2)

    # Если предыдущей команды не было, разрешены все три команды
    return f(a + 1, b, 1, r1, r2) + f(a + 3, b, 2, r1, r2) + f(a * 4, b, 3, r1, r2)

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