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

9387
знаков
1
таблица
0
изображений

Каждый оператор в программе 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.

Определение 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).

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


Информация о работе «Написание программ вычисления факториалов»
Раздел: Информатика, программирование
Количество знаков с пробелами: 9387
Количество таблиц: 1
Количество изображений: 0

Похожие работы

Скачать
723413
0
0

... данных будет нести больше смысла, если его отсортировать каким‑либо образом. Часто требуется сортировать данные несколькими различными способами. Во‑вторых, многие алгоритмы сортировки являются интересными примерами программирования. Они демонстрируют важные методы, такие как частичное упорядочение, рекурсия, слияние списков и хранение двоичных деревьев в массиве. Наконец, сортировка ...

Скачать
62370
0
0

... компьютер эмоционально безразличен к ошибкам учащихся. Это освобождает уче­ника от страха и смущения, снижает до минимума психологическую несовместимость, которая иногда имеет место между учеником и учителем. До появления компьютеров в школе резко разделя­лись два важнейших вида деятельности детей: обуче­ние и игра. Игра, как правило, запрещалась, а к обу­чению ребят принуждали. Теперь компьютер ...

Скачать
20976
1
9

... функциях это уравнение не решается. Его решение называется гамма-функцией. Гамма-функцию можно записать в виде ряда или в виде интеграла. Для изучения глобальных свойств гамма-функции обычно пользуются интегральным представлением. 2.2       Интегральное представление   Перейдем к решению этого уравнения. Будем искать решение в виде интеграла Лапласа: В этом случае правая часть уравнения ...

Скачать
80531
5
5

... вы можете обрабатывать наряду с символами и числами. Он начинается с имени, называемого функтором (в данном случае date), за которым следуют три аргумента. Функтор в Visual Prolog — не то же самое, что функция в других языках программирования; это просто имя, которое определяет вид составного объекта данных и объединяет вместе его аргументы. Функтор не обозначает, что будут выполнены какие-либо ...

0 комментариев


Наверх