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

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

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

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

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

# Первый этап: от 2 до 30 (с обязательным исключением числа 7)
# Создаем массив для хранения количества путей до чисел от 0 до 30
# a[i] - количество программ, которые преобразуют число 2 в число i
a = [0] * (30 + 1)
a[2] = 1  # Исходное положение - только один способ быть в числе 2
# Перебираем все числа от 3 до 30 включительно
for i in range(3, 30 + 1):
    if i == 7:
        continue # Пропускаем число 7 согласно условию задачи
    elif i % 2 == 0:
        # Для четных чисел: можно прийти командами +1, +2 или *2
        a[i] = a[i - 1] + a[i - 2] + a[i // 2]
    else:
        # Для нечетных чисел: можно прийти только командами +1 или +2
        a[i] = a[i - 1] + a[i - 2]

# Второй этап: от 30 до 41
# Массив для чисел от 0 до 41
# b[i] - количество программ, которые преобразуют число 30 в число i
b = [0] * (41 + 1)
b[30] = 1  # Начинаем из числа 30, которое должно быть в траектории
# Перебираем все числа от 31 до 41 включительно
for i in range(31, 41 + 1):
    if i % 2 == 0:
        # Для четных чисел учитываем все три команды
        b[i] = b[i - 1] + b[i - 2] + b[i // 2]
    else:
        # Для нечетных чисел - только команды сложения
        b[i] = b[i - 1] + b[i - 2]
# Общее количество программ равно произведению путей до 30 и от 30 до 41
print(a[30]*b[41])

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

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

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

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

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