Написание программ вычисления факториалов
Написание программ вычисления факториалов
Каждый
оператор в программе 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
|
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}
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).
У
читателя может сложиться мнение, что для доказательства того, что было сделано
в этих примерах, потрачено слишком много усилий. В конце концов, это можно было
получить, руководствуясь интуитивными соображениями. Однако, важно уже сейчас
научиться проделывать подобные формальные преобразования. Это приведет к
лучшему пониманию условного оператора. При построении и анализе некоторых
программ, эта техника будет совершенно необходима. Даже выполнение небольшого
числа упражнений будет способствовать изменению привычных для нас способов
обдумывания программ и того, что называется интуицией программиста.
Список литературы
Для
подготовки данной работы были использованы материалы с сайта http://www.ergeal.ru/