Написание программ вычисления факториалов
Каждый оператор в программе Harmonic определял переход из одного множества состояний в другое.
Рассмотрим еще один пример.
Пример 10.1. Написать программу вычисления f(n)=n!, где n - натуральное, либо равно 0.
Program Factorial (input, output);
{ Программа Factorial вычисляет значение функции п!
Input: (nÎ N)Ù(n ³ 0)
Output: (Fctrl Î N)Ù(Fctrl ³ 1)Ù(Fctrl= 
)
}
var i, n, fctrl: integer; { n - исходное значение;
fctrl - результат;
i - параметр цикла
}
begin
{Ввод исходных данных}
write (¢Введите значение n = ¢);
readln (n);
{Проверка корректности исходных данных}
if n<0 then writeln (¢Ошибка.¢ п ¢не может быть меньше 0¢)
else
begin
if n=0 then fctrl:=1
else
begin
fctrl:=1;
for i:=2 to n do fctrl:=fctrl * i
end {if n=0};
{Вывод результата}
writeln (¢ При n = ¢, n, ¢_ n! = ¢, fctrl)
end {if n<0}
end {Program}.
Рис. 10.1.
В этой программе в строке 1 мы определяем типы переменных, которые мы будем использовать при вычислениях. В строке 2 пользователю выдается приглашение ввести исходное значение п, а в строке 3, с помощью оператора readln (n) значение, заданное пользователем, полагается текущим значением переменной п. Строка 4 - это проверка корректности исходных данных. Если текущее значение n < 0, то пользователю будет выдано сообщение об ошибке.
В соответствии с определением функции n!
в строке 5, в зависимости от текущего значения, происходит выбор способа вычисления n!. Если n=0, то переменная fctrl принимает значение 1. Если n¹0, то в строках 6 и 7 в цикле вычисляется произведение 1´2´3´…..´(п-1)´п. В строке 6 определяется начальное значение переменной fctrl. Обратите внимание, до этого момента значение этой пременной было не определено. Строка 7 - это оператор цикла. Переменная i - это параметр цикла, который последовательно принимает значения 2, 3, 4 и т.д. до п включительно. Для каждого значения параметра цикла выполняется тело цикла:
fctrl:= fctrl * i.
Ну и наконец, строка 8 - вывод полученного результата.
Последовательность итераций цикла в строке 7 для п = 6 показана на рисунке 10.2. Под итерацией цикла мы будем понимать выполнение тела цикла для конкретного значения параметра цикла.
| Итерации | Cостояние | ||||
| 1-я итерация i£n ® | 
| i | fctrl | n | |
| 2-я итерация i£n ® | 
| ||||
| 3-я итерация i£n ® |
| ||||
| 4-я итерация i£n ® |
| ||||
| 5-я итерация i£n ® | 
| ||||
Рис. 10.2.
Введение Pre и Post условий.
В зависимости от исходного значения п, мы будем иметь разное число итераций цикла и разные состояния. Итак, на основе сделанного, мы можем сделать вывод: всякий оператор в программе определяет переход из одного множества состояний в другое.
Мы уже умеем определять множество с помощью предикатов. Пусть Q и R - предикаты, определяющие множество состояний до выполнения оператора S и после выполнения оператора S соответственно.
Это записывается так:
{Q} S {R}.
Это преобразование множества Q во множество R и определяет семантику оператора S.
Определение 10.1. Предикат Q называется предусловием оператора S, а предикат R - постусловием оператора S, если
{Q} S {R}.
Например, оператор fctrl: =1; из строки 7 рис. 10.1, любое состояние вычислительного процесса перерабатывает в состояние, где fctrl=1, т.е.
Q º T, а R º fctrl =1.
Семантика оператора присваивания.
Наша задача определить семантику оператора присваивания в терминах множеств состояний. Это означает, что нам надо определить взаимосвязь пред и постусловий для оператора присваивания. Эту задачу мы рассмотрим применительно к простым переменным.
Определение 10.2. Обозначим wp(S,R) - предикат, определяющий множество всех состояний, для которых выполнение оператора S, обязательно заканчивается за конечное время и обязательно в состоянии, удовлетворяющем предикату R.
Пример 10.1.
Пусть S - это оператор присваивания
i: = i+1,
а R º i £ 1, тогда
wp(i: = i+1, i £ 1)=(i £ 0).
Действительно, выполнение i: = i+1 может завершиться в состоянии
i £ 1 только, если i было меньше или равно нулю. Как следует из свойства операции сложения, если i > 0, то i+1 >1.
Пример 10.2.
Множество состояний, определяемых предикатом wp(S,T) для некоторого оператора S, есть множество всех состояний, таких, что выполнение оператора S, начавшееся в одном из этих состояний, обязательно заканчивается.
Определение 10.3. Обозначим 
предикат, который получается из предиката R, если в нем заменить все свободные вхождения переменной x на выражение е.
Например, если R(x,y)=(x+y), то
Пусть
E=x<y Ù("i: 0 £ i < n: bi < y).
Тогда
, т.к. i не свободно в Е.
Определение 10.4. wp(x: = e, R) = если domain(e), то ;
где domain(e) - предикат, описывающий множество состояний, для которых значение выражения е определено.
Примеры 10.3.:
wp(x: =5, х=5) = (5=5) = Т,
т.е. любое состояние оператор x: =5 перерабатывает в состояние, на котором предикат х=5 выполняется.
wp(x: =5, х¹5) = (5¹5) = F,
т.е. нет такого состояния, которое бы оператор x: =5, перевел в состояние х¹5.
wp(x: =x+1, х<0) = (x+1<0) =(x<-1).
wp(x: =x´x, х4=10) = ((x´x)4=10) = (x8=10).
Пусть с - константа, тогда
wp(x: =е, х=с) = (е=с),
т.е. оператор x: =е обязательно завершится и даст в результате состояние, где x имеет значение с, если, и только если, значение выражения е при выполнении этого оператора будет равно с.
Пусть с - константа, а х и y - имена двух разных переменных, тогда
wp(x: =е, у=с) = (у=с),
т.е. выполнение оператора x: = е не может изменить значение переменной у.
В последнем примере предполагается, что x: =е может изменить только значение переменной х. Вычисление выражения е не может изменить значения никакой переменной, т.е. нет, так называемого, побочного эффекта. Побочный эффект мы рассмотрим позднее в лекции 15.
Запрещение побочных эффектов исключительно важно, т.к. это позволяет рассматривать выражения в программе, так же, как в математике. Это означает, что выражение в программе обладает многими свойствами выражений в математике.
Идея описания семантики оператора в терминах пред- и постусловий применима не только к отдельному оператору, но и к группе операторов. Покажем, что последовательность операторов
t: =х; x: =y; y: = t;
обеспечивает обмен значениями у переменных х и y.
Пусть начальное значение {x=Y, y=X}.
{x=Y Ù y=X}
t: =х;
{x=Y Ù y=X Ù t=Y}
x: =y;
{x=X Ù y=X Ù t=Y}
y: = t;
{x=X Ù y=Y Ù t=Y}
или
{x=Y Ù y=X} t: =х; x: =y; y: = t; {x=Х Ù y=Y}.
Что и требовалось доказать.
Условный оператор.
Условный оператор в большинстве языков программирования реализует операцию композиции “выбор”. Этот оператор позволяет выбрать ту или иную последовательность операторов в зависимости от текущего состояния вычислительного процесса.
Пример 10.4.
if x=>0 then z: =x else z: =-x.
В результате выполнения этого условного оператора, переменная z получит значение, равное абсолютной величине х.
Согласно синтаксису языка Pascal, между ключевыми словами if и then должно стоять логическое выражение. Если значение этого логического выражения Т, то выполняется оператор, стоящий после then, если - F, то оператор, стоящий после else.
Определение 10.3.
wp(if B then S1 else S2 , R) =
= domain (B)Ù(B Ú ØB)Ù((B Þ wp(S1 , R))Ù(ØBÞwp(S2 , R))),
где domain (B) - предикат, определяющий область определения для логического выражения В.
Обычно, B - всюду определенный предикат, поэтому член domain (B) опускают, и остается
wp(if В then S1 else S2 , R)= B Þ wp(S1 , R) Ù ØBÞwp(S2 , R)
Покажем, что при любых начальных условиях, выполнение оператора из примера 10.4. дает в результат в z абсолютную величину х.
wp(if x=>0 then z: =x else z: = -x, z =abs(x))=
= x ³ 0 Þ wp(z: =x, z =abs(x)) Ù x < 0 Þ wp(z: = -x, z = abs(x))=
= x ³ 0 Þ x = abs(x) Ù x < 0 Þ -x = abs(x) = TÙT = T,
т.е., при любом предусловии этот оператор даст в качестве значения
z =abs(x).
Пример 10.5. Покажем, что при любом начальном состоянии оператор
if x=>y then z: =x else z: = y
дает z =max(x,y).
wp(if x ³ y then z: =x else z: = y, z =max(x,y))=
=((x ³ y) Þ(z: =x, z =max(x,y))) Ù ((x<y) Þ (z: =y, z =max(x,y)))=
=(x ³ y) Þ (x=max(x,y)) Ù ((x<y) Þ (y= max(x,y))= TÙT = T.
Пример 10.6. Покажем, что
wp(if x=>y then z: =x else z: = y, z =y)= (x £ y).
wp(if x=>y then z: =x else z: = y, z =y)=
(x ³ y) Þ (z: =x, z =y) Ù (x<y) Þ (z: =y, z =y)=
(x ³ y) Þ (x=y) Ù (x<y) Þ (y=y)=(x £ y).
У читателя может сложиться мнение, что для доказательства того, что было сделано в этих примерах, потрачено слишком много усилий. В конце концов, это можно было получить, руководствуясь интуитивными соображениями. Однако, важно уже сейчас научиться проделывать подобные формальные преобразования. Это приведет к лучшему пониманию условного оператора. При построении и анализе некоторых программ, эта техника будет совершенно необходима. Даже выполнение небольшого числа упражнений будет способствовать изменению привычных для нас способов обдумывания программ и того, что называется интуицией программиста.