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

Рекурсия:

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

• 0, если a > b или если в процессе встречается запрещённое число 40, так как такая траектория точно не будет подходящей и ее не нужно учитывать в подсчете количества траекторий;
• 1, если a == b, так как единица означает, что мы нашли путь, который число А может превратить в число B выполнив все условия задачи;
• сумму значений для двух возможных переходов (прибавление 1, умножение на 3), если a < b, так как такая траектория еще не нарушила условия задачи и может стать подходящей.

Так как нужно, чтобы траектория содержала число 16, но не содержала число 40, то общее количество программ равно произведению f(1, 16) и f(16, 60). Первая часть считает количество способов дойти от 1 до 16, вторая — от 16 до 60, произведение этих значений дает ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

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

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа, опираясь на подсчеты для предыдущих значений. Для подсчета количества траекторий до числа 60 необходимо знать количество траекторий до чисел 59 и 20 (для команды умножения на 3).

Для реализации этого способа в программе создадим список, изначально заполненный нулями. Каждое число в списке будет обозначать количество траекторий до определенного числа. Далее пройдем по списку и заполним его значениями. Значение для каждой i-ой ячейки равно сумме значений для ячеек с индексами i-1 и i//3 (только для чисел, кратных 3).

По условию траектория не должна содержать число 40, поэтому при подсчете количества траекторий значение в ячейке с индексом 40 должно остаться 0. Также по условию траектория должна содержать число 16. Для этого разделим вычисления на два независимых этапа: из 1 в 16, из 16 в 60. Результаты этих этапов необходимо перемножить, чтобы получить итоговый ответ, так как для каждого пути из первой части можно использовать любой путь из второй части.

# Первый этап: от 1 до 16
# Создаем массив для хранения количества путей до чисел от 0 до 16
# a[i] - количество программ, которые преобразуют число 1 в число i
a = [0] * (16 + 1)
a[1] = 1  # Исходное положение - только один способ быть в числе 1

# Перебираем все числа от 2 до 16 включительно
for i in range(2, 16 + 1):

    # Для всех чисел учитываем команду +1
    ways = a[i - 1]

    # Для чисел, кратных 3, добавляем команду *3
    if i % 3 == 0:
        ways += a[i // 3]

    a[i] = ways

# Второй этап: от 16 до 60 (с обязательным исключением числа 40)
# Массив для чисел от 0 до 60
# b[i] - количество программ, которые преобразуют число 16 в число i
b = [0] * (60 + 1)
b[16] = 1  # Начинаем из числа 16, которое должно быть в траектории

# Перебираем все числа от 17 до 60 включительно
for i in range(17, 60 + 1):
    if i == 40:
        continue  # Пропускаем запрещенное число согласно условию задачи

    # Для всех чисел учитываем команду +1
    ways = b[i - 1]

    # Для чисел, кратных 3, добавляем команду *3
    if i % 3 == 0:
        ways += b[i // 3]

    b[i] = ways

# Общее количество программ равно произведению путей до 16 и от 16 до 60
print(a[16] * b[60])