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

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

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

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

# Функция для подсчета количества программ преобразования a -> b
def F(x, y):
    if x == y: # Если дошли до нужного числа
        return 1
    if x > y : # Если число стало больше нужного
        return 0
    else:
        return F(x + 1, y) + F(x + 2, y) + F(x * 2,y) # Количество путей до текущего числа

print(F(3, 9) * F(9, 11) * F(11, 13))  # Найдем ответ по условию задачи, умножение позволит нам включить число 9 и 11 в цепочку действий

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

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

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

# Создаем массив для хранения количества путей до чисел от 4 до 13
# a[i] - количество программ, которые преобразуют число 3 в число i
a = [0] * 100
a[3] = 1 # Начальное число
for i in range(4, 14):
    a[i] = a[i - 1] + a[i - 2] + a[i // 2] * (i % 2 == 0) # Будем делить на 2 только если число кратно 2
    # Если встретили 9 или 11 обнулим все значения до них. Таким образом мы не включим в последующие подсчёты лишние пути.
    if i == 9 or i == 11:
        for j in range(i):
            a[j] = 0

print(a[13]) # Выводим ответ