Веду на сто
Конспект

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

Динамический подсчет программ с обязательными и запрещенными точками.

На экзамене

Задание 13. Последовательность команд рассматривается как путь в ориентированном графе чисел.

Формулы и факты

  • Число: вершина графа. Команда: ориентированное ребро. Программа: путь от A до B.
  • Для старта F(A) = 1: один пустой путь.
  • Количество путей в вершину: сумма количеств путей во всех допустимых предшественниках.
F(x)=\sum_{p \in Pred(x)}F(p)
ОграничениеКак учитывать
Запрещенная точка xF(x) = 0, значение дальше не передается
Обязательная точка CN(A → C) * N(C → B)
Несколько обязательных точекРасположить по ходу движения и перемножить соседние участки
Условие на одну из точекРазбить пути на непересекающиеся случаи и сложить

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

Алгоритм

  1. Выпиши старт, финиш, команды, обязательные и запрещенные значения.
  2. Вырази предшественников числа x обратными командами.
  3. Задай старту 1, запрещенным и недостижимым вершинам 0.
  4. Заполни значения в порядке, где все предшественники уже посчитаны.
  5. Для обязательных точек посчитай участки отдельно и перемножь.
  6. Для "ровно одной" или "хотя бы одной" точки выдели непересекающиеся случаи.
  7. Проверь небольшой фрагмент графа вручную.

Ловушки

  • Путают: стартовое значение 0 и 1. Сверь: у старта один пустой путь.
  • Путают: прямую команду и поиск предшественника. Сверь: реши, из какого числа команда приводит в x.
  • Путают: вычитание запрещенных путей и обнуление вершины. Сверь: поставь 0 до продолжения расчета.
  • Путают: сумму и произведение участков через обязательную точку. Сверь: каждый первый участок сочетается с каждым вторым.
  • Путают: x / k с целым предшественником. Сверь: учитывай деление только без остатка.