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

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

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

По формуле , но по условию дано, что траектория должна проходить через число 9. Значит если мы будем проходить через 8, то условие будет не выполнено. Следовательно .

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

Отсюда получаем искомое количество программ — 272.

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

Динамический способ решения заключается в том, чтобы подсчитать количество программ, которые ведут от начального числа 1 до конечного числа 14, с условием, что траектория обязательно проходит через число 9. Для этого создаем массив, где каждый индекс соответствует конкретному числу на экране, а значение в ячейке — количество программ, которые приводят к этому числу с учетом предыдущих шагов.

1. Создаем массив длиной 25 элементов, все элементы изначально равны 0. Каждый элемент массива a[i] будет обозначать количество программ, которые приводят к числу .

2. Устанавливаем a[4] = 1, так как это стартовое условие (сдвиг индексов в коде).

3. Проходим по всем числам от 5 до 24 (включительно) и считаем количество программ, которые могут привести к :

- прибавление 1 из ,

- прибавление 5 из ,

- деление на 2 из , только если делится на 2.

4. Если текущее число соответствует запрещенным значениям, через которые траектория не должна проходить (в данном коде это числа 11 и 17), обнуляем все предыдущие значения массива, чтобы исключить все пути, которые достигли этих чисел.

5. После прохождения всех чисел результат для конечного числа 14 хранится в ячейке a[24].

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

# Создаем массив длиной 25, все значения изначально равны 0
a = [0] * 25
# Устанавливаем исходное количество программ для числа 4
a[4] = 1
# Перебираем все числа от 5 до 24 включительно
for i in range(5, 25):
    # Считаем количество программ, которые приводят к числу i:
    # из i-1 командой "прибавить 1"
    # из i-5 командой "прибавить 5"
    # из i//2 командой "деление на 2", только если i четное
    a[i] = a[i - 1] + a[i - 5] + a[i // 2] * (i % 2 == 0)
    # Если текущее число равно запрещенному значению (11 или 17),
    # обнуляем все предыдущие значения массива, чтобы исключить эти траектории
    if i == 11 or i == 17:
        for j in range(i):
            a[j] = 0
# Выводим количество программ, которые приводят от 1 к 14 с условием прохождения через число 9
print(a[24])