Реферат: Написание программ вычисления факториалов
Каждый оператор в программе 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
2
fctrl
1
n
6
2
2
6
2-я итерация
i£n ®
3
2
6
3
6
6
3-я итерация
i£n ®
4
6
6
4
24
6
4-я итерация
i£n ®
5
24
6
5
120
6
5-я итерация
i£n ®
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) = (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.
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).
У читателя может сложиться мнение, что для доказательства того, что было
сделано в этих примерах, потрачено слишком много усилий. В конце концов, это
можно было получить, руководствуясь интуитивными соображениями. Однако, важно
уже сейчас научиться проделывать подобные формальные преобразования. Это
приведет к лучшему пониманию условного оператора. При построении и анализе
некоторых программ, эта техника будет совершенно необходима. Даже выполнение
небольшого числа упражнений будет способствовать изменению привычных для нас
способов обдумывания программ и того, что называется интуицией программиста.
)
предикат, который
получается из предиката R , если в нем заменить все свободные вхождения переменной x на выражение е .
, т.к. i не свободно в Е.
;