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

Решение 1

a = [0] * 20
a[1] = 1
for i in range(2, 20):
    a[i] = a[i - 1] + a[i // 2] * (i % 2 == 0)
    if i == 14:
        a[i] = 0
print(a[19])

Решение 2

a = [0] * 40
a[1] = 1
for i in range(1, 19):
    if i == 14:
        a[i] = 0
    a[i + 1] += a[i]
    a[i * 2] += a[i]
print(a[19])

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

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

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

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

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