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 + 3, y) — соответствует применению команды «прибавь 3».

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

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

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

Второй способ — динамическое программирование.

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

1. В начальной точке a[5] = 1, так как число — стартовое, и есть один способ «быть» в нём.

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

- количество способов попасть в число равно a[i-1] + a[i-3], так как в него можно попасть командой «+1» из и командой «+3» из .

После завершения цикла значение a[42] будет равно количеству всех программ, преобразующих в .

# Создаём массив для хранения количества способов
a = [0] * 100
# Начальная точка (число 5) имеет один способ
a[5] = 1
# Заполняем массив для чисел от 6 до 42
for i in range(6, 43):
    # Количество способов попасть в число i
    a[i] = a[i - 1] + a[i - 3]
# Выводим количество программ для числа 42
print(a[42])