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

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

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

1. Сначала определяем вспомогательную функцию sum_of_digits(number), которая считает сумму цифр числа.

- Если число равно 0, возвращаем 0.

- Иначе берем последнюю цифру числа через оператор % 10 и прибавляем результат рекурсивного вызова для числа без последней цифры (целочисленное деление на 10).

- Мы используем @lru_cache(None), чтобы кешировать результаты вызовов функции и ускорить вычисления при повторных обращениях к одной и той же сумме цифр.

2. В функции f(a, b) проверяем следующие условия:

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

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

- В остальных случаях мы применяем все три команды:

      - прибавляем 1 к и вызываем функцию рекурсивно,

      - умножаем на 3 и вызываем функцию рекурсивно,

      - прибавляем сумму цифр числа (через функцию sum_of_digits(a)) и вызываем функцию рекурсивно.

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

3. Запускаем функцию f(11, 60), чтобы получить количество всех программ, которые начинают с числа 11 и приводят к числу 60.

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

# Определяем функцию для подсчета суммы цифр числа с кэшированием
@lru_cache(None)
def sum_of_digits(number):
    # Если число равно 0, сумма цифр равна 0
    if number == 0:
        return 0
    else:
        # Суммируем последнюю цифру и рекурсивно вызываем для числа без последней цифры
        return number % 10 + sum_of_digits(number // 10)

# Определяем рекурсивную функцию f(a, b) для подсчета количества программ
def f(a, b):
    # Если текущее число равно целевому, найден путь
    if a == b:
        return 1
    # Если текущее число больше целевого, путь невозможен
    elif a > b:
        return 0
    else:
        # Считаем количество программ, применяя все три команды
        return f(a + 1, b) + f(a * 3, b) + f(a + sum_of_digits(a), b)

# Вызываем функцию для подсчета всех программ от 11 до 60
print(f(11, 60))