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

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

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

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

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

print(f(43, 1)) # Найдем ответ по условию задачи

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

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

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

# Создаем массив для хранения количества путей до чисел от 42 до 0
# a[i] - количество программ, которые преобразуют число 43 в число i
a = [0] * (43 * 3 + 3)
a[43] = 1 # Начальное число
for i in range(42, 0, -1):
    # Количество путей до текущего числа. Учтем, что целочисленное деление сработает и для чисел * 3 + 1 и * 3 + 2.
    a[i] = a[i + 1] + a[i * 3] + a[i * 3 + 1] + a[i * 3 + 2]
    if i == 8: # Если встретили 8 - исключаем её (ставим 0 путей)
        a[i] = 0
print(a[1]) # Выводим ответ