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

Рекурсия:

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

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

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

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

 

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

Динамический способ решения заключается в подсчете количества траекторий для каждого числа опираясь на подсчеты для предыдущих значений. Так, например, для подсчета количества траекторий до числа 100 необходимо знать количество траекторий до чисел 95, 90 и 50.

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

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

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

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

    # Можно прийти командами Прибавить 5 и Прибавить 10
    ways = a[i-5] + a[i-10]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += a[i // 2]

    a[i] = ways

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

# Перебираем все числа от 51 до 100 включительно
for i in range(51, 100 + 1):
    # Можно прийти командами Прибавить 5 и Прибавить 10
    ways = b[i-5] + b[i-10]

    # Можно прийти командой Умножить на 2 (только для четных чисел)
    if i % 2 == 0:
        ways += b[i // 2]

    b[i] = ways

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