23.01 Количество программ из A в B

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

Мы используем функцию f(x, y), которая возвращает количество программ, преобразующих число x в число y.

1. Если x > y, возвращаем 0, так как дальнейшие шаги превышают целевое число.

2. Если x == y, возвращаем 1, так как найден один корректный путь.

3. В остальных случаях количество программ равно сумме трёх рекурсивных вызовов:

- f(x+1, y) — применение команды «прибавь 1»;

- f(x+2, y) — применение команды «прибавь 2»;

- f(x*3, y) — применение команды «умножь на 3».

Использование декоратора @lru_cache позволяет кэшировать уже вычисленные значения, что ускоряет рекурсию за счёт избежания повторных вычислений.

from functools import lru_cache

# Декоратор для кэширования результатов рекурсии
@lru_cache
def f(x, y):
    # Если текущее число больше целевого, путь невозможен
    if x > y:
        return 0
    # Если текущее число равно целевому, найден один путь
    if x == y:
        return 1
    # Суммируем количество программ для всех команд: +1, +2, *3
    return f(x + 1, y) + f(x + 2, y) + f(x * 3, y)

# Выводим количество программ для преобразования числа 4 в 63
print(f(4, 63))

Решение динамикой

Создаём массив a, где a[i] — количество способов получить число i от числа .

1. Инициализируем a[4] = 1, так как стартовое число имеет один способ «быть» в нём.

2. Для чисел от до :

- прибавляем количество способов попасть в i-1 через команду «прибавь 1»;

- прибавляем количество способов попасть в i-2 через команду «прибавь 2»;

- если число делится на 3, прибавляем количество способов попасть в i//3 через команду «умножь на 3».

После завершения цикла значение a[63] покажет количество всех программ.

# Создаем массив для динамического программирования
a = [0] * 64
# Начальная точка (число 4) имеет один способ
a[4] = 1
# Заполняем массив для чисел от 5 до 63
for i in range(5, 64):
    # Количество способов через команду +1 и +2
    a[i] = a[i - 1] + a[i - 2]
    # Если число делится на 3, добавляем путь через умножение
    a[i] += a[i // 3] * (i % 3 == 0)
# Выводим количество программ для числа 63
print(a[63])