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

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

Идея рекурсивного решения заключается в построении функции f(x, y), которая возвращает количество программ, преобразующих число в число . Для реализации задаются следующие проверки и действия:

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

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

3. В остальных случаях функция вызывает саму себя для трёх вариантов действий: прибавить 2 (x+2), прибавить 3 (x+3), умножить на 2 (x*2). Количество программ для текущего равно сумме результатов этих вызовов.

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

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

# Считаем количество программ через число 8:
# сначала от 3 до 8, затем от 8 до 18, умножаем результаты
print(f(3, 8) * f(8, 18))

—

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

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

1. Создаём массив a длиной 19 (от 0 до 18) и инициализируем его нулями.

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

3. Проходим циклом по всем числам от 4 до 18. Для каждого числа i:

- добавляем количество программ из числа i-2, так как команда "прибавить 2"ведёт к i;

- добавляем количество программ из числа i-3, так как команда "прибавить 3"ведёт к i;

- если i чётное, добавляем количество программ из i//2, так как команда "умножить на 2"ведёт к i;

4. Если i = 8, значит мы достигли числа, через которое должна проходить траектория. Тогда обнуляем все значения для индексов меньше 8, чтобы учесть только пути, которые прошли через 8.

После завершения цикла значение a[18] даёт количество программ от 3 до 18, проходящих через число 8.

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

# Количество программ от 3 до 18 через число 8
print(a[18])