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

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

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

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

a = [0] * 20
a[1] = 1 # Начальное число
for i in range(2, 20):
    a[i] = a[i - 1] + a[i // 2] * (i % 2 == 0) # Будем делить на 2 только если число кратно 2
    if i == 14: # Если встретили нужное число - обнулим всё до него, таким образом будут учтены пути лишь с учётом 14
        a[i] = 0
print(a[19]) # Выводим ответ

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

# Повторим шаги с первого решения динамикой, но теперь будем заполнять значения наперёд
# Создаем массив для хранения количества путей до чисел до 40
# a[i] - количество программ, которые преобразуют число 1 в число i
a = [0] * 40
a[1] = 1
for i in range(1, 19):
    if i == 14: # Если встретили нужное число - обнулим всё до него, таким образом будут учтены пути лишь с учётом 14
        a[i] = 0
    a[i + 1] += a[i]
    a[i * 2] += a[i]
print(a[19]) # Выводим ответ

Решение 3 Пусть — количество программ, которые число 1 преобразуют в число . Тогда верно следующее утверждение:

Заполним таблицу по данной формуле до 13:

Так как по условию сказано, что траектория не должна проходить через число 14, значит мы никак не можем его получить, что означает .

Заполним таблицу до конца:

Отсюда получаем ответ — 20.