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

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

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

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

# Создаем массив для хранения количества путей до чисел от 257 до 273
# a[i] - количество программ, которые преобразуют число 256 в число i
a = [0] * 274
a[256] = 1  # Начальное число
for i in range(257, 274):
    a[i] = a[i - 3] + a[i - 4] + a[i // 2] * (i % 2 == 0) # Будем делить на 2 только если число кратно 2
    if i == 262 or i == 270: # Если встретили запрещённые числа - ставим 0, чтобы их не учитывать
        a[i] = 0
print(a[273]) # Выводим ответ

Решение руками

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

Заметим, что — это больше числа, которое нам нужно найти, значит 3-я команда нам не понадобится. Составим уравнение:

Составим таблицу по данному уравнению:

Так как траектория не должна содержать число 262, то . Продолжим заполнение таблицы:

Аналогично .

Отсюда ответ — 2.