Разработка программ
.pdf14write (rez)
15end.
Трассировка программы.
Входные данные 3
Строка |
Ход выполнения |
n |
i |
rez |
4 |
вход в work3 |
? |
? |
? |
5 |
|
3 |
|
|
6 |
|
|
|
1 |
7 |
|
|
1 |
|
8 |
(i<=n)=True |
|
|
|
10 |
|
|
|
1 |
11 |
|
|
2 |
|
8 |
(i<=n)=True |
|
|
|
10 |
|
|
|
2 |
11 |
|
|
3 |
|
8 |
(i<=n)=True |
|
|
|
10 |
|
|
|
6 |
11 |
|
|
4 |
|
8 |
(i<=n)=False |
|
|
|
13 |
|
|
|
0.167 |
14 |
Вывод 0.167 |
|
|
|
15 |
Выход из work3 |
|
|
|
Результат: 0.167 При выполнении вычислений часто требуется выполнять
повторяющиеся действия. Это можно достичь многократным написанием операторов, но более эффективным способом является использование оператора цикла. Чтобы пояснить, как использовать оператор цикла, рассмотрим, как факториал обычно вычисляется вручную. Математическое выражение факториала есть 1*2*3*..*n. При его вычислении вначале 1 умножается на 2, затем результат умножается на 3, на 4 и так далее до n. То есть, на каждом шаге делается одно и тоже: новое значение есть результат умножения предыдущего значения на требующийся множитель. Если очередное значение обозначить как rezi, где i –
номер шага, то rezi=rezi-1 * i для i = 1,..n и rez0=1.
21
Чтобы организовать процесс на компьютере, необходимо предусмотреть счетчик, который будет считать, сколько раз было произведено умножений. В данном случае для счетчика использовано имя i.
С учетом сказанного процесс вычисления факториала записан в третьем разделе таблицы разработки. Здесь надо учесть следующее. На очередном шаге требуется выполнить вычисление rezi = rezi-1 * i. Поскольку для вычисления очередного значения требуется только знание предыдущего, в Паскале это реализуется записью rez := rez * i, где в правой части используется предыдущее значение, а в левой получается новое.
Вложенные циклы
Так как оператор S в цикле while U do S может быть любым оператором, в том числе и оператором цикла, то в этом случае возникает структура, которая называется вложенные циклы. Например:
while U1 do
while U2 do S2. (этот оператор цикла вложен во внешний и представляет собой оператор S1). Или:
while U1 do begin
while U2 do S2; while U3 do while U4 do S4; end;
и т.д.
Выполнение таких вложенных циклов происходит по тем же правилам, что и для простых - просто выполнение внешнего цикла как бы приостанавливается на время выполнения внутреннего цикла.
Пример трассировки программы с вложенными циклами
1.Program prim3;
2.var n,i,j:integer;
3.x,y,rez,rez1:real;
4.begin
22
5.read (n,x,y);
6.i:=1;
7.rez1:=0;
8.while i<=n do
9.begin
10.j:=0;
11.rez:=0;
12.while j<n do
13.begin
14.rez:=rez+i*x*y;
15.j:=j+1;
16.end;
17.rez1:=rez1+rez/n;
18.i:=i+1;
19.end;
20.write (rez1)
21.End.
Входные данные 2 2 8
Строка |
Ход выполнения |
n |
x |
y |
i |
j |
rez |
rez1 |
4 |
вход в Prim3 |
? |
? |
|
? |
|
? |
|
5 |
|
2 |
2 |
8 |
|
|
|
|
6 |
|
|
|
|
1 |
|
|
|
7 |
|
|
|
|
|
|
|
0 |
8 |
(i<=n)=True |
|
|
|
|
|
|
|
10 |
|
|
|
|
|
0 |
|
|
11 |
|
|
|
|
|
|
0 |
|
12 |
(j<n)=True |
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
16 |
|
15 |
|
|
|
|
|
1 |
|
|
12 |
(j<n)=True |
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
32 |
|
15 |
|
|
|
|
|
2 |
|
|
12 |
(j<n)=False |
|
|
|
|
|
|
|
17 |
|
|
|
|
|
|
|
16 |
18 |
|
|
|
|
2 |
|
|
|
23 |
|
|
|
|
|
|
|
|
Строка |
Ход выполнения |
n |
x |
y |
i |
j |
rez |
rez1 |
8 |
(i<=n)=True |
|
|
|
|
|
|
|
10 |
|
|
|
|
|
0 |
|
|
11 |
|
|
|
|
|
|
0 |
|
12 |
(j<n)=True |
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
32 |
|
15 |
|
|
|
|
|
1 |
|
|
12 |
(j<n)=True |
|
|
|
|
|
|
|
14 |
|
|
|
|
|
|
64 |
|
15 |
|
|
|
|
|
2 |
|
|
12 |
(j<n)=False |
|
|
|
|
|
|
|
17 |
|
|
|
|
|
|
|
48 |
18 |
|
|
|
|
3 |
|
|
|
8 |
(i<=n)=False |
|
|
|
|
|
|
|
20 |
Вывод: 48 |
|
|
|
|
|
|
|
21 |
Выход из prim3 |
|
|
|
|
|
|
|
Результат: 48 Рассмотрим вывод математического выражения для резуль-
тата. Во внешнем цикле выражение rezl:=rezl+rez/n соответствует
n
rezli=rezli-1+rezi/n, i=1,..,n, то есть rezi /n, в свою очередь внут-
i 1
реннему циклу соответствует rezj=rezj-1+i*x*y, j= 0,..,n-1, то есть
n 1
i*x*y. В итоге математическое выражение результата запи-
j 0
шется так
n |
1 |
n 1 |
n |
|
|
i*x*y |
|||
|
||||
i 1 |
n j 0 |
i 1 |
i*x*y |
n 1 |
n |
ixy |
n |
n 1 |
|
|
1 |
n xy i xy |
n. |
|||||
n |
n |
2 |
|||||
j 0 |
i 1 |
i 1 |
|
Разработка программы с вложенными циклами.
n
Задача: Вычислить значение выражения i!
i 1
Спецификация.
1. Составить программу для вычисления значения выражения
24
n
i! , где i ! = 1*...*i.
i1
2.Входные данные: целое число, значение n, например 3
3.Выходные данные: целое число, значение выражения, например, 9 (для входных данных 3).
Таблица разработки |
|
Шаги разработки |
Примечания |
work4 |
|
|
|
begin |
|
ввод входных данных |
|
вычисление значения выражения |
|
вывод результата |
|
end |
|
ввод входных данных |
переменная n (integer) |
|
|
read (n) |
|
вычисление значения выражения |
|
|
|
begin |
переменная rez (real) |
установить начальное значение суммы |
|
установить начальное значение счетчика |
переменная i (integer) |
слагаемых |
|
пока не просуммированы все слагаемые |
|
выполнять |
переменная fact (inte- |
begin |
|
установить начальное значение |
ger) |
произведения |
переменная j (integer) |
установить начальное значение |
|
счетчика произведений |
|
пока не перемножены все сомножители |
|
выполнять |
|
begin |
|
учесть в произведении очередной |
|
25 |
|
сомножитель увеличить счетчик произведений end
учесть в сумме очередное слагаемое увеличить счетчик слагаемых
end end
установить начальное значение суммы
rez:=0;
установить начальное значение счетчика слагаемых
i:=1;
пока не просуммированы все слагаемые выполнять
while i<=n do
установить начальное значение произведения
fact:=1;
установить начальное значение счетчика произведений
j:=1;
пока не перемножены все сомножители выполнять
while j<=i do
учесть в произведении очередной сомножитель
Fact:=fact*j;
увеличить счетчик произведений
26
j:=j+1;
учесть в сумме очередное слагаемое
rez:=rez+fact;
увеличить счетчик слагаемых
i:=i+1;
вывод результата
write (rez)
Текст программы
1.Program work4;
2.var i,j,n,fact,rez: integer;
3.begin
4.read( n);
5.rez:=0; i:=1;
6.while i<=n do
7.begin
8.fact:=1; j:=1;
9.while j<=i do
10.begin
11.fact:=fact*j;
12.j:=j+1;
13.end;
14.rez:=rez+fact;
15.i:=i+1;
16.end;
17.write (rez)
18.end.
n
Вычисление i! требует применения вложенных циклов.
i 1
Это становится ясно, если его переписать в виде
27
n |
n |
n |
i |
n |
i! (i!) ( j) |
или, более обобщенно, (i-ое слагае- |
|||
i 1 |
i 1 |
i 1 |
j 1 |
i 1 |
мое), где i-ое слагаемое это i!.
Когда проводится суммирование нескольких слагаемых, то процесс обычно выполняется следующим образом. Вначале (к нулю) прибавляется первое слагаемое, затем к тому, что получилось второе, потом третье и так далее. Таким образом, процесс суммирования схематично можно представить так (здесь также требуется счетчик для учета количества просуммированных слагаемых)
Установить сумму в ноль.
Установить счетчик слагаемых в единицу Пока не просуммированы все слагаемые, выполнить begin
Вычислить очередное слагаемое Учесть в сумме очередное слагаемое Модифицировать счетчик слагаемых
End
В свою очередь, как видно из занятия 7, вычисление факториала (очередного слагаемого) требует использования другого цикла (внутреннего), являющегося вложенным по отношению к циклу суммирования. Здесь также требуется свой счетчик для колличества выполненных умножений в факториале. С учетом сказанного в разделе 3 таблицы разработки представлен общий процесс вычисления требуемого выражения.
Подпрограммы - процедуры и функции
1.Описание процедуры. Описание функции.
2.Вызов процедуры. Вызов функции.
3.Параметры, передаваемые по ссылке и по значению.
4.Локальные и глобальные переменные.
5.Примеры трассировки процедур и функций.
I. Нередко при написании программы требуется повторить один и тот же фрагмент в разных местах. В таких случаях удобнее оформить этот фрагмент отдельно в виде подпрограммы,
28
дать ей имя и вызывать по имени каждый раз, когда необходимо выполнить этот фрагмент.
Подпрограммой называется часть программы, имеющая свое имя и предназначенная для решения определенной, самостоятельной и вполне законченной задачи. В Паскале есть два вида подпрограмм: процедура и функция.
Процедуры и функции бывают встроенные и определяемые программистом. Встроенные процедуры и функции не нужно описывать, они являются неотъемлемой частью компилятора Паскаля, например: sqr(x), sqrt(x), round(x) - встроенные функции, write(x), read(x) - встроенные процедуры.
Определяемые программистом процедуры и функции необходимо описывать после раздела описания переменных и перед разделом описания операторов.
Как программа описывает весь процесс в целом, так описание подпрограммы описывает отдельный подпроцесс и дает ему имя.
Описание процедуры/функции
Заголовок процедуры |
procedure имя (<список формальных |
|
параметров>); |
Заголовок функции |
function имя (<список формальных |
|
параметров>): тип результата; |
Раздел описания меток |
label ... |
Раздел описания констант |
const ... |
Раздел описания типов |
type ... |
Раздел описания пере- |
var ... |
менных |
|
Раздел описания операто- |
begin |
ров (тело подпрограммы) |
S1; |
|
S2; |
|
... |
|
SN; |
end;
Функция – это та же процедура, только с именем функции связывается некоторое значение, используемое при вычислении
29
выражения. Описание функции оформляется аналогично описанию процедуры, только: а) указывается тип результата функции; б) в теле функции обязательно должно выполняться присвоение (с типом результата) имени функции; такое присвоение возвращает результат функции.
Иногда требуется выполнить один и тот же фрагмент программы, но с разными данными. В этом случае данные передаются подпрограмме в виде параметров. Таким образом, параметр позволяет одной части программы иметь доступ к информации, относящейся к другой ее части, т.е. с помощью параметров происходит обмен информацией между программой и подпрограммами.
Параметры, которые перечисляются в заголовке подпрограммы, называются формальными, а в вызове подпрограммы - фактическими. Между формальными и фактическими параметрами существует взаимно однозначное соответствие, которое определяется позицией параметра в списке. Таким образом, начальное значение формального параметра в подпрограмме равно значению соответствующего фактического параметра.
II. Употребление имени подпрограммы - процедуры или функции (с необязательным списком фактических параметров после имени) в программе называется обращением, или вызовом подпрограммы.
Вызов процедуры представляет собой отдельный оператор, называемый оператор процедуры; вызов функции, в отличие от вызова процедуры, не может быть отдельным оператором и происходит только когда имя функции употребляется в качестве компоненты какого-либо выражения, операнда какой-либо операции.
Вызов процедуры – общий вид : имя_процедуры (<список фактических параметров>);.
Выполнение:
1.выполнение основного процесса приостанавливается
2.вычисляются значения фактических параметров
3.вычисленные значения фактических параметров передаются в
30