Основы программирования

Общая схема


Обозначим через X множество всевозможных наборов значений всех переменных, меняющихся в ходе выполнения цикла. Множество X иногда называют фазовым, или конфигурационным, пространством задачи. Инвариант - это некоторое условие I(x), зависящее от точки x из множества X и принимающее значение "истина" или "ложь". (Математики называют такие условия предикатами.) В процессе инициализации точке x присваивается такое значение x0, что условие I(x0) истинно.

Обозначим условие завершения цикла через Q(x). Условия I(x) и Q(x) должны быть подобраны таким образом, чтобы одновременная истинность I(x) и Q(x) обеспечивала решение требуемой задачи: нахождение точки x с требуемыми свойствами.

Тело цикла можно трактовать как отображение точки x в новую точку T(x) из того же множества X:

T:X

X

Условие I(x) является инвариантом для отображения T: если I(x), то I(T(x)) также истинно.

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

x := x0; // x0 выбирается так, чтобы условие // I(x0) было истинным утверждение: I(x);

цикл пока не Q(x) | инвариант: I(x); | x := T(x); // точка x преобразуется в T(x) конец цикла

утверждение: Q(x) и I(x); ответ := x;

Конечно, эта схема не имеет никакой ценности без умения применять ее на практике. Рассмотрим несколько важных примеров ее использования.



Содержание раздела