Состояние алгоритма
Состояние алгоритма — это полное описание того, что известно об исполнении алгоритма в данный момент: какие значения имеют переменные и где находится исполнитель.
При запуске алгоритма задаётся начальное состояние: известны входные данные, начальные значения переменных и позиция исполнителя перед первой командой. После выполнения каждой команды состояние может измениться. Например, оператор присваивания меняет значение переменной, а команда движения меняет положение исполнителя.
Здесь \(S\) — состояние алгоритма, \(x_1, x_2, \ldots, x_n\) — значения переменных, а \(p\) — положение исполнителя в алгоритме: номер текущей команды или указатель на следующую команду. Если изменилось хотя бы одно значение или положение, состояние стало другим.
Пусть выполняется алгоритм: \(a := 2\); \(b := a + 3\); вывести \(b\). После первой команды состояние можно записать так: \(a=2\), \(b\) ещё не задано, исполнитель находится перед второй командой. После второй команды: \(a=2\), \(b=5\), исполнитель находится перед командой вывода. Последовательность таких состояний удобно записывать в трассировочной таблице.
Состояние алгоритма — это не только значения переменных. Если значения переменных не изменились, но исполнитель перешёл к другой команде, состояние всё равно изменилось. Также состояние не следует путать с отдельным шагом алгоритма: шаг — это действие или переход, а состояние — результат, который получился к определённому моменту.
В алгоритме переменные \(x=4\) и \(y=7\) не изменились, но исполнитель перешёл от команды 3 к команде 4. Изменилось ли состояние алгоритма?
Главное
- Состояние алгоритма описывает значения переменных и положение исполнителя.
- После выполнения команды состояние может измениться из-за нового значения или перехода к другой команде.
- Последовательность состояний алгоритма можно исследовать с помощью трассировочной таблицы.