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

Рекурсия:

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

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

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

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

3. Иначе мы рекурсивно вызываем функцию трижды:

- — пробуем команду "прибавить 3"

- — пробуем команду "прибавить 4"

- — пробуем команду "умножить на 5"

Сумма этих трёх значений даст общее количество программ, ведущих от к .

Так как траектория должна содержать число 50, мы считаем количество способов сначала дойти от 2 до 50, а затем отдельно от 50 до 100. Общее количество программ — это произведение этих двух значений, так как для каждого пути из первой части можно использовать любой путь из второй части.

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

# Вычисляем количество программ, учитывая обязательное прохождение через 50
print(f(2, 50) * f(50, 100))

—

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

Мы можем использовать динамическое программирование, чтобы подсчитать количество программ для каждого числа до 100. Основная идея: создать массив a, где a[i] — количество программ, которые приводят к числу .

1. Инициализируем массив нулями и устанавливаем a[2] = 1, так как стартуем с числа 2.

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

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

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

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

3. Чтобы гарантировать, что траектория содержит число 50, мы обнуляем все значения массива до индекса 50 после его обработки.

4. После завершения цикла, a[100] содержит общее количество программ, которые проходят через 50 и приводят к 100.

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

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