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

  • 01 окт. 2011 г.
  • 8445 Слова
Написание программ вычисления факториалов
Каждый оператор в программе Harmonic определял переход из одного множества состояний в другое.
Рассмотрим еще один пример.
Пример 10.1. Написать программу вычисления f(n)=n! , где n - натуральное, либо равно 0.
Program Factorial (input, output);
{ Программа Factorial вычисляет значение функции п!
Input: (nI N)U(n ? 0)
Output: (Fctrl I N)U(Fctrl ?1)U(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 {ifn=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 ® | | i2 | fctrl1 | n6 |
| | 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 - это оператор...
tracking img