Учебная статья

Анализ алгоритмов исполнителя и подсчёт программ

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

Зачем на экзамене

В задании 13 исполнитель преобразует начальное число в конечное с помощью нескольких команд. Нужно посчитать не значения, а количество различных последовательностей команд. Задача сводится к подсчету путей в ориентированном графе.

Что нужно уметь

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

База

Граф программ

Каждое достижимое число является вершиной графа. Команда исполнителя задает направленное ребро из текущего числа в новое. Одна программа соответствует одному пути от начальной вершины A до конечной вершины B.

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

Динамическое программирование

Обозначим через F(x) количество программ, которые переводят A в x. Для начального числа задаем F(A) = 1: существует один пустой путь, от которого строятся все программы.

Если в вершину x можно прийти из предшественников p1, p2, ..., pk, то действует формула:

F(x)=\sum_{p \in Pred(x)}F(p)

Суммируются количества программ для всех допустимых предшественников. Например, для команд "+1" и "+2" при движении вверх обычно получается F(x) = F(x - 1) + F(x - 2).

Элемент задачи	Представление в графе	Действие в таблице
начальное число	стартовая вершина	`F(A) = 1`
команда	ориентированное ребро	добавить значение предшественника
запрещенное число	удаленная вершина	`F(x) = 0`
обязательное число	точка разбиения пути	перемножить количества участков

Порядок заполнения

Значение F(x) можно вычислять только после всех его предшественников. Если каждая команда увеличивает число, таблицу заполняют слева направо. Если каждая команда уменьшает число, удобно двигаться от старта вниз или считать обратные переходы от финиша.

При смешанных командах сначала проверь, остается ли граф ациклическим на нужном диапазоне. Для произвольного ациклического графа вершины обрабатывают в топологическом порядке. Если команды создают цикл и число шагов не ограничено, программ может быть бесконечно много: стандартная схема задания обычно исключает такую ситуацию.

Обязательные и запрещенные точки

Запрещенная вершина не может входить ни в один путь, поэтому число способов для нее равно нулю. Ее значение не передается дальше.

Если программа обязана пройти через точку C, путь разбивается на независимые участки A -> C и C -> B. При подходящем направлении команд количество программ равно:

N(A \to B\ \text{через}\ C)=N(A \to C)\cdot N(C \to B)

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

Условия на траекторию

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

Как решать

Запиши начальное и конечное числа, команды, обязательные и запрещенные значения.
Проверь направление каждой команды и отбрось переходы, после которых финиш уже недостижим.
Вырази предшественников произвольной вершины обратными командами.
Задай для старта 1, для запрещенных и недостижимых вершин 0.
Заполни таблицу в порядке, при котором все предшественники уже посчитаны.
Если есть обязательные точки, посчитай участки отдельно и перемножь результаты.
Если есть условие "ровно одна точка" или "хотя бы одна точка", раздели траектории на непересекающиеся случаи.
Проверь малый фрагмент графа вручную и убедись, что каждая команда учтена один раз.

Частые ошибки

Ошибка: ставить в начальной вершине 0. Как избежать: помни, что старт имеет один пустой путь.
Ошибка: применять команду вперед при поиске предшественников. Как избежать: реши уравнение "из какого числа команда приводит в x".
Ошибка: считать запрещенную вершину, а затем только вычитать ее из ответа. Как избежать: сразу присвой ей 0, чтобы пути через нее не продолжались.
Ошибка: складывать участки пути через обязательную точку. Как избежать: каждый путь первой части сочетается с каждым путем второй части, поэтому результаты перемножаются.
Ошибка: использовать дробный предшественник для команды умножения. Как избежать: учитывай обратный переход только при целочисленной делимости.
Ошибка: дважды считать траектории в пересекающихся случаях. Как избежать: делай случаи взаимоисключающими или используй включение и исключение.

Проверь себя

Чему равно количество программ в начальной вершине?
Как учитывается запрещенное промежуточное число?
Как соединяются количества программ до и после обязательной точки?
Можно ли для команды "умножь на 2" считать x / 2 предшественником нечетного x?

Ответы: 1) 1; 2) для него ставят 0; 3) перемножаются; 4) нет.

Связь с заданиями

В задании 13 меняются команды и ограничения на траекторию, но основа остается одной: количество путей в графе считается суммой значений в предшественниках. Обязательные точки разбивают путь на участки, а запрещенные точки обнуляют соответствующие вершины.