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

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

Динамический способ решения заключается в подсчёте количества программ, которые преобразуют каждое число по порядку от исходного до целевого, с учётом того, что траектория должна содержать определённое число (в данном случае 11).

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

2. В ячейку с индексом 3 записываем 1, так как начинаем с числа 3, и только один способ быть в этом состоянии.

3. Перебираем числа от 4 до 27 включительно (for i in range(4, 28)), и для каждого числа выполняем следующие действия:

- a[i] = a[i - 1] + a[i - 4] + a[i // 4] * (i % 4 == 0) — суммируем количество программ для переходов из чисел , и (для кратных 4), что соответствует применению команд +1, +4 и *4;

4. Когда достигнуто число 11, необходимо обнулить все предыдущие значения (for j in range(i): a[j] = 0), чтобы гарантировать, что траектория обязательно проходит через число 11.

5. После завершения цикла элемент a[27] будет содержать количество программ, преобразующих число 3 в число 27, проходя через число 11.

# Создаем массив для хранения количества программ до числа 27
a = [0] * 28

# Начальное число 3, только один способ быть в этом состоянии
a[3] = 1

# Заполняем массив для чисел от 4 до 27
for i in range(4, 28):
    # Количество программ, приводящих к числу i, равно сумме программ,
    # которые приводят к i-1, i-4 и i//4 (если i кратно 4)
    a[i] = a[i - 1] + a[i - 4] + a[i // 4] * (i % 4 == 0)

    # Если достигнуто число 11, обнуляем все предыдущие значения,
    # чтобы траектория проходила через 11
    if i == 11:
        for j in range(i):
            a[j] = 0

# Выводим количество программ, приводящих к числу 27 через 11
print(a[27])