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

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

Мы используем рекурсивный подход для подсчёта количества программ. Сначала определяем функцию f(a, b), которая считает, сколько существует программ, преобразующих число в число с учётом всех условий. Внутри функции проверяем следующие условия:

1. Если текущее число больше целевого числа или равно запрещённому числу 12, то путь невозможен и возвращаем 0.

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

3. В противном случае считаем все возможные переходы: прибавляем 1, прибавляем 2 или умножаем на 3, вызывая функцию рекурсивно для каждого из вариантов и суммируя результаты.

Таким образом, каждая рекурсивная ветка проверяет корректность траектории и суммирует количество программ для всех допустимых вариантов. Вызов f(3,40) даст итоговое количество программ, которые из числа 3 приводят к числу 40, обходя число 12.

# Импортируем кэш для ускорения рекурсии
from functools import lru_cache

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

# Вызываем функцию от 3 до 40 и выводим результат
print(f(3,40))

—

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

Мы используем динамический способ, создавая массив a длиной 41, где индекс соответствует числу на экране, а значение по индексу показывает количество программ, ведущих к этому числу. Изначально заполняем массив нулями, а в ячейку с индексом 3 записываем 1, так как начинаем с числа 3.

Далее для каждого числа от 4 до 40 включительно выполняем следующие действия:

- Считаем количество программ, которые приходят к из командой "прибавить 1".

- Считаем количество программ, которые приходят к из командой "прибавить 2".

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

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

После прохода по всем индексам в массиве, итоговое количество программ хранится в a[40].

# Создаем массив из 41 элемента, все значения равны 0
a = [0] * 41
# В ячейку с индексом 3 записываем 1, так как стартуем с числа 3
a[3] = 1
# Перебираем все числа от 4 до 40
for i in range(4, 41):
    # Считаем количество программ из i-1, i-2 и i//3
    a[i] = a[i - 1] + a[i - 2] + a[i // 3] * (i % 3 == 0)
    # Если число равно 12, обнуляем количество программ
    a[12] = 0

# Выводим количество программ, которые ведут от 3 к 40 без числа 12
print(a[40])