23.03 Количество программ из A в B где траектория вычислений содержит число(-а)

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

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

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

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

3. Если ни одно из условий не выполнено, мы вызываем функцию трижды: первый раз с (команда "прибавить 1"), второй раз с (команда "умножить на 2"), третий раз с (команда "прибавить 3"). Сумма этих вызовов даёт общее количество программ.

Чтобы учесть требование, что траектория должна содержать число 14, мы разбиваем задачу на два этапа: подсчёт программ от 2 до 14 и от 14 до 24. Результаты этих этапов перемножаются, так как любая программа из первой части может быть объединена с любой программой второй части.

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

# Вычисляем количество программ с учётом прохождения числа 14
print(f(2, 14) * f(14, 24))

—

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

Динамический способ решения заключается в том, что мы создаём массив, где индекс соответствует числу , а значение хранит количество программ, которые преобразуют начальное число в .

1. Создаём массив длиной 25, заполняем нулями, так как числа от 0 до 24.

2. В ячейку записываем 1, так как стартуем с числа 2.

3. Перебираем все числа от 3 до 24:

- Добавляем количество программ, ведущих в (команда "прибавить 1").

- Добавляем количество программ, ведущих в (команда "прибавить 3").

- Если делится на 2, добавляем количество программ, ведущих в (команда "умножить на 2").

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

После завершения цикла в будет храниться количество программ, которые из числа 2 ведут к 24 и проходят через число 14.

# Создаем массив для подсчета программ
a = [0] * 25
# Начальное число 2, один способ быть в нём
a[2] = 1
# Перебираем числа от 3 до 24
for i in range(3, 25):
    # Считаем количество программ, ведущих в i
    a[i] = a[i - 1] + a[i - 3] + a[i // 2] * (i % 2 == 0)
    # Если достигли числа 14, обнуляем предыдущие элементы массива
    if i == 14:
        for j in range(i):
            a[j] = 0

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