3.3. Операторы управления

Операторы управления -- это средства языка, позволяющие управлять ходом выполнения программы. Фундаментальными структурами для описания алгоритмов являются последовательное, условное и циклическое выполнение.

Операторы управления служат для выражения этих структур на языке программирования.

3.3.1. Оператор последовательного выполнения

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

Пусть S1, S2,...,Sn -- операторы или последовательности операторов. Тогда правило вывода для последовательности

S1 S2.....Sn

имеет вид

(i (1(i(n ( {Pi-1} Si {Pi}

-------------------------

{P0} S1 S2 ... Sn {Pn}

На самом деле достаточно иметь правило для n=2:

{P} S1 {R}, {R} S2 {Q}

---------------------

{P} S1 S2 {Q}

Докажем это индукцией по п. При n = 2 утверждение очевидно. Пусть

i (1in-1  {Pi-1} Si {Pi})

-------------------------

{P0} S1 S2 ... Sn-1 {Pn-1}

Обозначим через SS последовательность S1 S2...Sn-1

Тогда выполняется

{P} SS {Pn-1}, {Pn-1} Sn {Pn}

--------------------------

{P0} SS {Pn}

Таким образом, из этих двух соотношений имеем

i (1in-1  {Pi-1} Si {Pi}, {Pn-1} Sn {Pn}

-----------------------------------------

{P0} SS Sn {Pn}

или

i (1in  {Pi-1} Si {Pi})

-------------------------

{P0} S1 S2 ... Sn {Pn}

что и требовалось доказать.

___________________________________

П р и м е р 3.6. С помощью указанного выше правила

из

{Х=Y*(1+q)+(r-Y)} r:=r-Y; {X=Y*(1+q)+r} ,

{Х=Y*(1+q)+r} q:=1+q; {Х=Y*(1+q)+r}

выводим

{Х=Y*(1+q)+(r-Y)} r:=r-Y; q:=q+1; {Х=Y*(1+q)+r}

3.3.2. Условные операторы

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

Пусть В -- логическое выражение (т.е. выражение, тип значения которого есть Ьоо1еаn), S1, S2 - последовательности операторов (в крайнем случае один оператор). Тогда оператор

if B then

S1

else

S2

end if;

означает следующее: вычисляется В; если его значение истинно (true), то выполняется S1, в противном случае S2. Этот оператор называется оператором if.

П р и м е р 3. 7. Оператор

if A>0 then

М:=А;

еlsе

М:=-А;

еnd if;

вычисляет абсолютное значение А и помещает его в переменную М.

Построим правило вывода для условного оператора.

Если требуется установить истинность спецификации

{Р} if B then S1 else S2 end if; {Q}

то необходимо доказать два утверждения:

1. Если В истинно, то выполняется S1 . Так как Р справедливо перед выполнением if, делаем вывод, что в этом случае Р & В справедливо перед выполнением if. Если Q справедливо после выполнения if, то должно быть справедливо и {Р & В} S1 {Q}. Итак, мы должны доказать

{Р & В} S1 {Q}

2. Если В ложно, то выполняется S2. Так как Р справедливо перед выполнением if, делаем вывод, что в этом случае Р & not В справедливо перед выполнением S2.

Если Q справедливо после выполнения if, то должно быть справедливо и {Р & not В) S2 {Q} Итак, мы должны доказать

{Р & not B} S2 {Q}

Если мы доказали истинность {Р & В} S1 {Q} и {P & not B} S2 {Q},то можно утверждать, что если Р справедливо перед выполнением if, то Q будет справедливо по окончании его выполнения независимо от тот, какой оператор (S1 или S2) был выбран для выполнения.

Итак, можно сформулировать следующее правило вывода для условного оператора:

{Р & В} S1 {Q} , {Р & not В} S2 {Q}

-------------------------------------

{Р} if В then S1 else S2 end if; {Q}

П р и м е р 3. 7 (продолжение). Для оператора из примера 3.7 В = (А>0). Пусть Р = true. Докажем, что после выполнения этот оператора И будет неотрицательно, т.е. Q = (M>=0). Так как по правилу вывода для оператора присваивания

{true & (А>0)} M:=А; {М>0}

{true & not(А>0)} М =-A; {M>=0}

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

{true} if А>0 then М:=А; else М:=-А; end if; {M>=0}

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

if В then

S

еlsе

;

end if;

Для этого случая часто используется сокращенная запись:

if В then

S

end if;

Для этом оператора правило вывода, конечно, проще. Докажем, что

({Р} ; {Q}) = (Р => Q)

Пусть выполнено {Р} ; {Q}. Надо доказать, что Р => Q. Предположим противное, т.е. существует такое состояние вычислений, что Р истинно, а Q ложно. Но правило вывода для пустого оператора имеет вид {Р} ; {Р}.

Следовательно, если Р было истинным до выполнения пустого оператора, он будет истинным и после выполнения.

При этом состояние вычислений не изменилось (так как для любой переменной Х и для любого значения с истинно утверждение {Х=с}; {Х=с}), поэтому Q ложно. Таким образом, ложно и {Р} ; {Q}. Получили противоречие.

Теперь пусть истинно Р =>Q. Воспользовавшись первым правилом консеквенции, получаем:

{P} ; {P}, P=>Q

-------------------

{P} ; {Q}

что и требовалось доказать.

Таким образом, правило вывода для сокращенной формы условного оператора:

{P & B} S {Q}, (P & not B =>Q

---------------------------------

{P} if B then S end if; {Q}

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

if В1 then

S1

еlsе

if B2 then

S2

еlsе

if В3 then

S3

еlsе

S4

еnd if;

еnd if;

еnd if;

Может показаться, что здесь оператор S2 (и тем более S3 и S4 ) находится на более глубоком уровне вложенности, чем оператор S1, но логически эти операторы могут быть одного уровня. Данное несоответствие можно разрешить, введя часть еlsif; общая форма такого условного опера-

тора имеет вид

if В1 then

S1

elsif В2 then

S2

elsif В3 then

S3

...

еlsе

Sn

еnd if;

Этот оператор выполняется следующим образом: вычи-

сляется значение выражения В1; если оно истинно, то вы-

полняется S1, в противном случае вычисляется В2, если

его значение истинно, то выполняется S2 и т.д.; если не

выполняется ни одно условие Вi, то выполняется Sn

(здесь также можно опускать часть еlsе, если Sn -- пус-

той оператор).

П р и м е р 3. 8. Использование общей формы услов-

ного оператора:

if Х < 0.5 then

Y:= Х;

еlsif Х<1.О then

Y:= 2.0*Х-О.5;

еlsе

Y:= Х+О.5;

еnd if;

В силу того, что условия В1, могут быть истинными одновременно, правило вывода для общей формы условного оператора имеет сложный вид

k (1k<n  ({P  i (1i<k  not Bi )  Bk} SK {Q})),

{ P  i (1i<k  not Bi )} Sn {Q}

{P} if Bi then Si elsif ... else Sn end if ; {Q}

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

i, j(1i<j<n  not (Bi  Bj)),

k,(1k<n  not ({ P  Bk} Sk {Q}),

{P  i (1i<n  not Bi)} Sn {Q}

{P} if Bi then S1 elsif ... else Sn end if; {Q}

Если все Вi, имеют вид Е=vi, где Е -- некоторое выражение, vi -- константы того же типа, что и значение выражения, условный оператор можно записать в более простой форме -- в виде оператора выбора

case E of

v1: S1

v2: S2

...

vn-1: Sn-1

Константы vi должны быть различными. Основное отличие условном оператора о.т оператора выбора состоит в том, что в условном операторе условия проверяются одно за другим, а в операторе выбора значение выражения непосредственно определяет одну из возможностей. Правило вывода для оператора выбора:

i (1i<n ({P(E=vi)} Si {Q})),

{P vi (1i<n(Evi))} Sn {Q}

___________________________________________

{P} if B1 then S1 elsif...else Sn end if;{Q}

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

case E of

v11,v12,...,v1k:S1

v21,v22,...,v2L:S2

...

others:Sn

end case;

Если Sn -- пустой оператор, то others можно опускать.

Наконец, последняя форма условного оператора, которая обобщает ранее рассмотренные формы. Это так называемый оператор выбора Дейкстры

if

В1: S1

В2: S2

....

Вn: Sn

еnd if

Этот оператор выполняется следующим образом: вычисляются значения всех логических выражений Вi; если все значения ложны, то выполнение программы прерывается (в этом случае действие оператора if эквивалентно действию оператора останова); в противном случае выполняется тот оператор Si, для которого Вi =true (если их несколько, то выбирается любой). Выражения Вi, называются предохранителями, операторы Si, -- охраняемыми списками, пары Вi: Si -- охраняемыми командами.

П р и м е р 3.9. Оператор определения наибольшего

из двух чисел:

if

Х>=Y : М:=Х;

Y>=Х : М:=Y;

еnd if;

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

порядок охраняемых команд внутри оператора if совершенно не важен;

выбор определяется явно сформулированными условиями, размещенными рядом с теми операторами, которые они охраняют;

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