Написание программ вычисления факториалов

Написание программ вычисления факториалов

Каждый оператор в программе 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. Если n0 , то в строках 6 и 7 в цикле вычисляется произведение    123…..(п-1)п . В строке 6 определяется начальное значение переменной fctrl . Обратите внимание, до этого момента значение этой пременной было не определено. Строка 7 - это оператор цикла. Переменная i - это параметр цикла, который последовательно принимает значения 2, 3, 4 и т.д. до п включительно. Для каждого значения параметра цикла выполняется тело цикла:

fctrl:= fctrl  i .



Ну и наконец, строка 8 - вывод полученного результата.

	Последовательность итераций цикла в строке 7 для п = 6 показана на рисунке 10.2. Под итерацией цикла мы будем понимать выполнение тела цикла для конкретного значения параметра цикла.



Итерации

Cостояние



1-я итерация



in 



i



2

fctrl



1

n



6





2

2

6



2-я итерация



in 





3



2



6





3

6

6



3-я итерация



in 





4



6



6





4

24

6



4-я итерация



in 





5



24



6





5

120

6



5-я итерация



in 





6



120



6





6

720

6



Рис. 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) = (55) = F ,

т.е. нет такого состояния, которое бы оператор x : =5 , перевел в состояние х5 .

wp(x : =x+1 , х<0) = (x+1<0) =(x<-1) .

wp(x : =xx , х4=10) = ((xx)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))(Bwp(S2 , R))) ,

где  domain (B) - предикат, определяющий область определения для логического выражения В.

Обычно, B - всюду определенный предикат, поэтому член domain (B) опускают, и остается 

wp(if В then S1 else S2 , R)= B  wp(S1 , R)  Bwp(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) = TT = 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))= TT = 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).



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