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

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

Мы используем рекурсивный способ, в котором строим функцию f(n, m), подсчитывающую количество программ, преобразующих число n в число m.

1. Сначала мы проверяем условие окончания пути:

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

- Если n > m, путь невозможен (число превысило цель), возвращаем 0.

2. Если ни одно из условий не выполнено, мы выполняем рекурсивные вызовы для каждой команды:

- f(n + 2, m) — соответствует команде "прибавить 2".

- f(n + 5, m) — соответствует команде "прибавить 5".

- f(n * 3, m) — соответствует команде "умножить на 3".

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

- Сначала считаем все пути от 7 до 31: f(7, 31).

- Затем считаем пути от 31 до 77: f(31, 77).

- Произведение этих двух значений даёт общее количество программ, так как для каждого пути до 31 можно использовать любой путь из 31 до 77.

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

# Считаем пути до числа 31, затем от 31 до 77, перемножаем результаты
print(f(7, 31) * f(31, 77))

—

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

Мы используем динамический массив a длиной 78, где каждый элемент a[i] хранит количество программ, приводящих к числу i.

1. Инициализируем массив нулями: a = [0] * 78.

2. Устанавливаем начальное число 7: a[7] = 1, так как существует ровно один способ находиться в числе 7 без выполнения команд.

3. Проходим по всем числам от 8 до 77:

- Для каждого i прибавляем количество способов добраться из i-2, i-5.

- Если i делится на 3, добавляем количество способов из i//3.

- После достижения числа 31 обнуляем все предыдущие значения массива (a[j] = 0 для всех j < 31), чтобы обеспечить прохождение траектории через 31.

4. В конце количество программ, которые приводят к числу 77 через 31, хранится в a[77].

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