23.01 Количество программ из A в B

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

Рекурсивный способ решения заключается в определении функции, которая считает количество программ, преобразующих число в число . Логика работы функции следующая: если текущее число превысило , то возвращаем , так как большее число уже нельзя уменьшить до нужного, следовательно, пути не существует. Если совпало с , то возвращаем , так как найден один корректный путь. В остальных случаях функция вызывает саму себя трижды: с аргументом (команда «прибавить 2»), с аргументом (команда «прибавить 3») и с аргументом (команда «умножить на 4»). Полученные значения суммируются, так как каждая из ветвей даёт количество различных программ. По условию траектория должна содержать число , поэтому итоговое количество программ вычисляется как произведение значений и : первая часть считает количество способов дойти от 2 до 16, вторая — от 16 до 26, а произведение этих чисел даёт ответ, потому что для каждого пути из первой части можно выбрать любой путь из второй.

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

# Условие требует прохождения через число 16,
# поэтому результат равен произведению двух этапов:
# от 2 до 16 и от 16 до 26
print(f(2,16)*f(16,26))

—

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

Динамический способ решения основывается на том, что мы последовательно заполняем массив, где индекс соответствует числу, а значение по индексу обозначает количество программ, ведущих в это число. Сначала создаём массив из нулей, в ячейку с индексом 2 записываем 1, так как изначально исполнитель находится в числе 2 и существует ровно один способ быть в этой позиции. Далее последовательно рассматриваем все числа от 3 до 26 и для каждого вычисляем количество способов попасть в него. Для этого проверяем:

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

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

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

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