Формальное исполнение алгоритма

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

Что такое формальное исполнение

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

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

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

Порядок выполнения команд

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

Например, если \(x=3\) и затем выполняется команда \(x:=x+5\), новое значение равно \(8\). Нельзя использовать уже изменённое значение повторно внутри той же команды, если оно не было присвоено раньше.

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

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

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

Алгоритм формального исполнения

1. Прочитайте алгоритм целиком и определите его структуру: линейную, разветвляющуюся или циклическую.
2. Выпишите начальные значения всех переменных и параметров исполнителя.
3. Создайте столбцы таблицы состояний.
4. Выполняйте команды строго по порядку, каждый раз проверяя условие и границы.
5. После каждой команды записывайте изменившиеся значения.
6. В конце прочитайте значение, которое требуется найти: переменную, количество действий, положение исполнителя или итоговый вывод.

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

Разобранный пример

Выполнить формально алгоритм и определить значение переменной \(s\) после его завершения:

1s := 0
2for i := 1 to 4 do
3    if i mod 2 = 0 then
4        s := s + i
5    else
6        s := s + 1
7output s

Исполнитель на поле или числовой линии

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

Если исполнитель перемещается по координатной плоскости, удобно записывать положение парой \((x,y)\). При движении вправо увеличивается \(x\), при движении влево уменьшается \(x\), при движении вверх увеличивается \(y\), если такая система координат указана в условии.

Как проверить результат

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

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

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