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

Каждый оператор в программе 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 было меньше или равно нулю. Как следует из свойства операции сложения, если

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать