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

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

Идея рекурсивного решения заключается в построении функции, которая подсчитывает количество программ, преобразующих число в число , проверяя при этом условия задачи. На каждом шаге функции проверяется:

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

- если текущее число кратно 5, то траектория нарушает условие задачи, возвращаем ;

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

- если ни одно из условий не выполнено, функция рекурсивно вызывает саму себя дважды: первый раз с (команда "прибавить 4"), второй раз с (команда "прибавить 5"), и складывает результаты этих вызовов, чтобы получить общее количество программ.

# Определяем функцию f(a, b) для подсчета количества программ
def f(a, b):
    # Если текущее число больше целевого b
    # или кратно 5, путь невозможен
    if a > b or a % 5 == 0:
        return 0  # Возвращаем 0, так как траектория недопустима

    # Если текущее число равно целевому, найден путь
    if a == b:
        return 1  # Возвращаем 1, увеличивая счетчик корректных траекторий

    # В остальных случаях рекурсивно суммируем количество траекторий
    # для двух возможных команд: прибавить 4 и прибавить 5
    return f(a + 4, b) + f(a + 5, b)

# Запускаем функцию от исходного числа 31 до 113
print(f(31, 113))

—

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

Идея динамического решения состоит в построении массива, где индекс соответствует числу, а значение по этому индексу показывает количество траекторий, ведущих к этому числу, начиная с числа 31. Сначала создаём массив длиной , заполненный нулями, и устанавливаем , так как существует ровно один способ находиться в начальном числе. Далее проходим циклом по всем числам от 32 до 113 и вычисляем количество траекторий для каждого числа:

- если число не кратно 5, значит в него можно попасть;

- количество программ для числа равно сумме программ для и , так как это соответствующие команды прибавления.

Итоговое количество программ хранится в .

# Создаем массив для хранения количества программ для всех чисел до 113
a = [0] * (113 + 1)  # Индексы от 0 до 113
# Начальное число 31 имеет одну траекторию
a[31] = 1

# Перебираем числа от 32 до 113 включительно
for i in range(32, 113 + 1):
    # Проверяем условие: число не должно быть кратно 5
    if i % 5 != 0:
        # Количество программ для числа i равно сумме
        # программ для i-4 и i-5
        a[i] = a[i - 4] + a[i - 5]

# Выводим количество программ, ведущих от 31 к 113
print(a[113])