Методы отладки алгоритма

Отладка алгоритма — это последовательный поиск и исправление ошибок в его логике, условиях, порядке команд и работе с данными. На экзамене полезно сочетать три приёма: выполнять трассировочную таблицу, проверять алгоритм на специально подобранных тестах и отдельно анализировать условия переходов и завершения.

Что проверяют при отладке

Алгоритм может быть записан без синтаксических ошибок, но всё равно давать неверный результат. Например, в условии перепутаны знаки \(<\) и \(\le\), переменная не изменяется внутри цикла или команда исполнителя применяется не к тому состоянию. Поэтому отладка должна отвечать на три вопроса: что должно происходить, что происходит фактически и на каком шаге появляется первое расхождение.

1. Сформулируйте, какой результат считается правильным и какие ограничения есть у входных данных.
2. Выберите короткий или специально подобранный тест.
3. Выполните команды по порядку, фиксируя состояние переменных и исполнителя.
4. Найдите первое расхождение с ожидаемым поведением.
5. Исправьте одну причину и повторите проверку на исходном и новых тестах.

Трассировка и состояние исполнителя

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

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

Здесь \(S_i\) — состояние перед шагом \(i\), \(c_i\) — очередная команда, а \(F\) — правило перехода к следующему состоянию. Если хотя бы один переход выполнен неверно, все последующие записи могут оказаться ошибочными.

1s := 0
2for i := 1 to 3 do
3    s := s + 2*i
4output(s)

Для этого фрагмента достаточно таблицы: перед циклом \(s=0\); после первой итерации \(s=2\), после второй — \(s=6\), после третьей — \(s=12\). Если вместо \(12\) получено \(6\), пропущена последняя итерация или неверно понята граница цикла.

Как подбирать тесты

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

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

Проверка условий и циклов

Каждое условие нужно рассматривать как разбиение входов на области. Запишите, при каких значениях выражение истинно, и проверьте границы. Для составного условия анализируйте отдельно операции «И», «ИЛИ» и «НЕ»: при «И» истинны должны быть обе части, при «ИЛИ» — хотя бы одна.

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

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

Разобранный пример: поиск первой ошибки

Алгоритм должен вывести сумму чисел от \(1\) до \(n\). Проверим программу при \(n=4\) и найдём ошибку в предложенной версии.

1s := 0\ni := 1
2while i < n do
3    s := s + i\ni := i + 1
4output(s)

Предположим, что отступы в записи означают: команда увеличения \(i\) находится внутри цикла. Ожидаемая сумма равна \(1+2+3+4=10\). Выполним алгоритм и проверим условие на каждом шаге.

1s := 0\ni := 1
2while i <= n do
3    s := s + i
4    i := i + 1
5output(s)

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

Частые ошибки при отладке