Задание 23: число программ исполнителя

Считаем количество программ исполнителя, переводящих одно число в другое, в том числе с обязательными или запрещёнными промежуточными числами.

Число способов добраться из A в B — это сумма чисел способов добраться туда из всех клеток, откуда есть прямой переход в B.

Что проверяет задание 23

Задание 23 — высокий уровень, 1 балл. Дан исполнитель с командами, меняющими число (например, «прибавь 1» и «умножь на 2»). Нужно посчитать, сколько различных программ переводят начальное число A в конечное B. Усложнения: программа должна (или не должна) проходить через определённые числа. Это комбинаторика траекторий, которая идеально ложится на динамику или рекурсию.

Теория: рекуррента на числе способов

Пусть cnt(x) — число программ, переводящих x в конечное B. Из x команды «+1» и «×2» ведут в x+1 и 2x. Тогда:

cnt(B) = 1                       // мы уже на месте — одна «пустая» программа
cnt(x) = cnt(x+1) + cnt(2*x)     // суммируем способы по каждой команде
cnt(x) = 0, если x > B           // перескочили цель — тупик

Запреты учитываются легко: cnt(forbidden) = 0 — через запретное число пройти нельзя. Обязательная точка C решается «склейкой»: число программ A→B через C равно cnt(A→C) · cnt(C→B).

Метод решения

1. Определите команды (какие переходы из x возможны).
2. Напишите рекурсию cnt(x) с базой в B и обнулением за пределами B.
3. Запретные числа дают cnt = 0.
4. Для «обязательно через C» перемножьте число программ A→C и C→B.

Разбор примера

Исполнитель: «прибавь 1» и «умножь на 2». Сколько программ переводят число 3 в число 20? А сколько — если программа не должна содержать число 13?

Решение на Python

from functools import lru_cache

START, END = 3, 20

# Без ограничений
@lru_cache(maxsize=None)
def cnt(x):
    if x > END:
        return 0
    if x == END:
        return 1
    return cnt(x + 1) + cnt(2 * x)

print("Программ 3 -> 20:", cnt(START))

# С запретом проходить через 13
FORBIDDEN = 13

@lru_cache(maxsize=None)
def cnt_no13(x):
    if x == FORBIDDEN:
        return 0          # через запретное число нельзя
    if x > END:
        return 0
    if x == END:
        return 1
    return cnt_no13(x + 1) + cnt_no13(2 * x)

print("Программ 3 -> 20 без числа 13:", cnt_no13(START))

Вывод:

Программ 3 -> 20: 18
Программ 3 -> 20 без числа 13: 12

Без ограничений — 18 программ; запрет числа 13 убирает 6 из них, остаётся 12. Запрет реализован одной строкой: как только x попадает в 13, ветка даёт 0.

Обязательное промежуточное число

«Программа должна содержать число 10» — считаем A→10 и 10→B и перемножаем.

from functools import lru_cache

def count(a, b):
    @lru_cache(maxsize=None)
    def cnt(x):
        if x > b:
            return 0
        if x == b:
            return 1
        return cnt(x + 1) + cnt(2 * x)
    return cnt(a)

# Через обязательную точку 10: 3 -> 10 -> 20
through = count(3, 10) * count(10, 20)
print("Программ 3 -> 20 через 10:", through)

Вывод:

Программ 3 -> 20 через 10: 8

Связь с задачей про Кузнечика / прибавления

Тот же приём работает для любых команд исполнителя: меняется только список переходов из x. Если команды «−1», «+3», «×3» — просто впишите соответствующие слагаемые в рекурренту. Динамика по числам (от B вниз к A) — альтернатива рекурсии, но рекурсия с lru_cache короче и нагляднее.

Типичные ошибки

• Неверная база. cnt(B) = 1 (одна программа — «ничего не делать»), а не 0.
• Не обрезают перелёт. Если x > B и команды только увеличивают число — это тупик, cnt = 0.
• Складывают вместо умножения для обязательной точки. Через C: число программ A→C умножают на C→B.
• Забывают про мемоизацию. Без неё рекурсия пересчитывает одно и то же и тормозит.

Итог

• cnt(x) = сумма cnt(следующих чисел), база cnt(B) = 1, перелёт за B — это 0.
• Запрет числа — cnt(forbidden) = 0; обязательная точка C — умножение A→C на C→B.
• Меняя список переходов, тот же код решает любые команды исполнителя.