23.02 Количество программ из A в B (на убывание)

Рекурсия:

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

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

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

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

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

1. Если , можно применить команду 3 (взять остаток от деления на 4), а также команды 1 и 2 (вычесть 1 и вычесть 3).

2. Если , команда 3 недоступна, применяем только команды 1 и 2.

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

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

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

—

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

Динамический подход заключается в построении массива, где индекс соответствует числу, а значение по индексу — количество программ, ведущих к этому числу, начиная с 22.

- Создаем массив длиной 23 (индексы от 0 до 22) и устанавливаем , так как существует один способ быть в начале.

- Проходим циклом по числам от 22 до 2 в обратном порядке (с помощью reversed(range(2,23))), чтобы суммировать пути для меньших чисел.

- Для каждого числа обновляем массив:

   - прибавляем к количество программ для , так как можно вычесть 1;

   - прибавляем к количество программ для , так как можно вычесть 3;

   - если , прибавляем к количество программ для , так как можно взять остаток от деления на 4.

- После завершения цикла содержит количество программ, преобразующих 22 в 2.

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

# Перебираем числа от 22 до 2 в обратном порядке
for i in reversed(range(2, 23)):
    # Применяем команду "вычесть 1"
    a[i-1] += a[i]
    # Применяем команду "вычесть 3"
    a[i-3] += a[i]
    # Применяем команду "взять остаток от деления на 4", если i > 4
    if i > 4:
        a[i % 4] += a[i]

# Выводим количество программ для достижения числа 2
print(a[2])