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

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

Мы будем использовать рекурсивный метод для подсчета всех допустимых программ. Введем функцию f(a, b, c1, c2), где:

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

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

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

- — номер команды, использованной два шага назад.

На каждом шаге проверяем условия:

- если , дальнейшее выполнение команд невозможно, возвращаем ;

- если , значит достигнут результат, возвращаем .

Далее вычисляем единицы и десятки числа :

- — цифра единиц,

- — цифра десятков.

Для каждой команды проверяем:

- Если команда не была выполнена два шага назад (c2 != номер команды) и применение команды изменит число и не приведет к 0, то рекурсивно вызываем функцию с новым значением числа и обновленными и .

- Суммируем результаты всех возможных рекурсивных вызовов.

Функция кешируется с помощью lru_cache, чтобы ускорить вычисления за счет запоминания ранее вычисленных значений. Вызов f(25, 111) вернет количество всех допустимых программ.

# Импортируем кеширование для ускорения рекурсии
from functools import lru_cache

# Определяем рекурсивную функцию f(a, b, c1, c2)
# a - текущее число, b - целевое число
# c1 - предыдущая команда, c2 - команда два шага назад
@lru_cache(None)
def f(a, b, c1 = 0, c2 = 0):
    # Если текущее число больше целевого, путь невозможен
    if a > b:
        return 0
    # Если текущее число равно целевому, найден допустимый путь
    if a == b:
        return 1
    # Инициализируем счетчик программ на этом шаге
    s = 0
    # Определяем цифру единиц числа a
    x = a % 10
    # Определяем цифру десятков числа a
    y = a // 10 % 10

    # Команда 1: прибавить разряд единиц
    if c2 != 1 and x != 0:
        s += f(a + x, b, 1, c1)

    # Команда 2: прибавить разряд десятков
    if c2 != 2 and y != 0:
        s += f(a + y, b, 2, c1)

    # Команда 3: умножить на разряд единиц
    if c2 != 3 and x != 0 and x != 1:
        s += f(a * x, b, 3, c1)

    # Команда 4: умножить на разряд десятков
    if c2 != 4 and y != 0 and y != 1:
        s += f(a * y, b, 4, c1)

    # Команда 5: прибавить 1
    if c2 != 5:
        s += f(a + 1, b, 5, c1)

    # Возвращаем суммарное количество программ с этого шага
                                                                                                  
                                                                                                  
    return s

# Вычисляем и выводим количество программ от 25 до 111
print(f(25, 111))