Иванова Г.С. - Основы программирования

5. Модульное программирование

Implementation Function sum;

Var s:integer;i:integer; begin s:=0;

for i:=0 to High(b) do s:-=s+b[i]; sum:=s;

end;

End.

Тестирующая программа для работы с индексами также может исполь­ зовать функции Low и High, которые вернут соответственно -5 и -3.

Program ex; Uses SummaS;

Const a:array['5..'3,3,. 7] ofinteger=((], J, /, 7,1), (2X2X2). (3X3,3,3));

Var i:integer; Begin

for i:=Low(a) to Higlt(a) do WriteLn(sum(a[i])); end.

Примечание. Обратите внимание, что допустимо лередавать в подпрограмму строку ма­ трицы как одномерный массив, указав ее номер - a[i].

В том случае, если необходимо разработать универсальную подпрограм­ му с параметрами - многомерными массивами, следует применять нетипизированные параметры (см. параграф 5.5).

Проблема разработки универсальных подпрограмм существует и для строк.

По правилам Borland Pascal, если строка передается в подпрограмму как параметр-значение, то длина ее не контролируется. Контроль длины осуще­ ствляется только для строк, передаваемых в подпрограмму как параметр-пе­ ременная. Поэтому при написании универсальных подпрограмм, работаю­ щих со строками произвольного размера, необходимо включать режим от­ крытых строк {$Р+} или объявлять параметры-строки как openstring.

Пример 5.7. Разработать программу, которая формирует строку, содер­ жащую буквы латинского алфавита.

Для решения задачи будем использовать процедуру, которая добавляет к строке символ, номер которого на единицу превышает номер последнего символа:

Unit Stroka;

Interface

Procedure Add(var s: openstring);

161

Часть L Основы алгоритмизации и процедурное программирование

Implementation

Procedure Add;

begin

s:=^s+chr(succ(Ord(s[length(s)J)));

end;

End

Параметр s должен передаваться как открытая строка, так как в против­ ном случае при попытке использовать процедуру в программе мы получим сообщение о том, что типы формального и фактического параметров не сов­ падают (Error 26: Туре mismatch).

Program ex; Uses Stroka;

Var S:string[26]; i:integer; Begin

s:^'A\-

for i: =2 to 26 do Add(s); WriteLn(s);

End

Увеличить область применения подпрограмм позволяет также использо­ вание нетипизированных параметров и параметров процедурного типа.

Задания для самопроверки

Задание 1. Разработайте универсальную подпрограмму, удаляющую из масси­ ва элемент, номер которого передается в списке параметров. Поместите подпрофамму в модуль. Разработайте тестирующую программу.

Задание 2. Разработайте универсальную подпрофамму, которая сортирует сло­ ва строки по алфавиту. Слова в строке разделены одним пробелом. Поместите под­ программу в модуль. Разработайте тестирующую программу.

5.5.Нетипизированные параметры

ВBorland Pascal допускается использовать параметры, тип которых не указан. Такие параметры могут передаваться в подпрограмму только по ссылке (как параметры-переменные), так как в этом случае в подпрограмму реально передается адрес параметра.

Безусловно, для того чтобы подпрограмма могла выполнять какие-либо действия с этим параметром, она должна как-то назначить ему тип.

Для приведения нетипизированного параметра к определенному типу можно использовать:

162

5.Модульное программирование

•автоопределенное преобразование типов;

•наложенное описание переменной определенного типа.

При автоопределенном преобразовании типов тип выражения указыва­ ют явно (см. параграф 2.5), например:

Procedure Proc(Var:a);...

...b:=Integer(a)-^IO;,..

Для наложения переменной определенного типа используют описание с absolute (см. параграф 2.3), например:

Procedure Proc(Var:a);...

Var r:real absolute a;...

При этом переменная г оказывается в памяти размещенной в том же ме­ сте, что и нетипизированный параметр а, и, соответственно, любое измене­ ние г приведет к изменению а.

Пример 5.8. Разработать подпрограмму, которая может суммировать как элементы массива целых чисел, так и элементы массива вещественных чи­ сел.

Тип массива подпрограмма будет определять по значению третьего па­ раметра, для которого объявим специальный перечисляемый тип. В разделе описаний подпрограммы определим шаблоны для каждого случая. Шаблон представляет собой описание массива соответствующего типа максимально возможного размера 64 Кб/<размер элемента>. Оба шаблону наложены по адресу нетипизированного параметра. Если значение третьего параметра подпрограммы treal, то используется шаблон mr, а если tinteger - шаблон mi.

Unit Summa4; Interface

Type ttype=(treal, tinteger); {описание типа третьего параметра}

Function sumfvar x;n:integer;t:ttype).real; Implementation

Function sum;

Var mr:array[L.maxint*2 div sizeof(real)] of real absolute x; mi:array[L.maxint^l div sizeof(integer)] of integer absolute x; s:real;i:integer;

begin s:=0;

if t=treal then

for i:-I to n do s:=s+mr[ij elsefor i:=I to n do s:-s+mifij; sum:=s;

end; End

163

Часть I. Основы алгоритмизации и процедурное программирование

Тестирующая программа вызывает одну и ту же функцию для суммиро­ вания массивов с разным типом элементов.

Program ex; Uses Summa4;

Var a:array[L.10] of integer; b:array[L.15] of real; i,n; integer;

Begin

for i;=l to 10 do Read(a[iJ); ReadLn; WriteLnCCyMMa= \stim(a,10,tintegerJ:8:J); for i:=l to J5 do Read(b[i]); ReadLn; WriteLn('CyMMa= \sum(b, 15jreal):8:l);

end.

Примечание. Вместо описания массива максимально возможного размера в подпрограм­ ме можно описать массив длиной 1 элемент, но при работе с таким шаблоном необходимо от­ ключать контроль индексов {$R-}.

Нетипизированные параметры можно применить для написания универ­ сальных подпрограмм, использующих в качестве параметров многомерные массивы. Поскольку невозможно в подпрограмме определить универсаль­ ный шаблон многомерного массива, приходится обрабатывать многомерный массив как одномерный, учитывая то, что элементы многомерных массивов в памяти располагаются так, что чем правее индекс, тем быстрее он воз­ растает. Так, элементы трехмерного массива В(2,3,2) будут расположены в памяти в следующем порядке:

bl,l,l' ^^1,1,2' bi,2,i, b| 2,2^ b] 3,1, b] 3 2, b 2 | j , ^2,\,b ^2,2,1' ^2,2,2^ Ь2Д1, Ь2зд.

Пример 5.9. Разработать универсальную подпрограмму транспонирова­ ния матрицы.

На рис. 5.9 показано, как в матрице А(Р,Р) расположены элементы реаль­ ной матрицы размером пхп, где п<Р, и, соответственно, как те же элементы расположены в памяти.

Таким образом, в одномерном массиве элемент с индексами i и j имеет индекс (i-l)*P+j, т.е. индекс этого элемента зависит от размера строки заре­ зервированной матрицы. В подпрограмму это значение передается через па­ раметр Р.

Чтобы транспонировать матрицу, меняем местами элементы, располо­ женные ниже и выше главной диагонали.

Примечание. При разработке алгоритма процедуры учтено, что при транспонировании матрицы по аналогии с переворотом строки количество перестановок равно п*п div 2. Если выполнить п*п перестановок, то матрица примет исходный вид, так как будет транспонирова­ на дважды.

164

5. Модульное программирование

1-ястрока	и т.д.
п

	Неопределенные	Неопределенные
		элементы
	элементы

Рис. 5.9. Матрица А(Р,Р) {а) и ее внутреннее представление {б)

Unit Matrica;

Interface

Procedure tran(Var x;n,P:integer); Implementation

Procedure tran;

Var a:array[1..2*maxint div sizeof(real)] of real absolute x; ij: integer;

t.real; begin

for i:=2 to n do forj:=l to i-I do

begin t: =a[(i-l) ''P+jJ;

af(i-l) *P+jJ: =afO'l) *P+i]; a[0'l)''P+i]:=t;

end;

end;

End.

Тестирующая программа выглядит следующим образом:

Program ex; Uses Matrica;

Var a:array[L .10J,. 10] of real; ij.'integer;

Begin

WriteLnCВведите матрицу a(5 *5);'); for i:=l to 5 do

begin

for j:=l to 5 do Read(a[i,j]); ReadLn; end;

165

Часть I. Основы алгоритмизации и процедурное программирование

tran(a,5,10); WriteLn('Результат: *); for i:-l to 5 do

begin

forj:=l to 5 do Write(a[iJ]:6:2); WriteLn;

end;

End

Задания для самопроверки

Задание 1. Разработайте универсальную подпрограмму, определяющую сред­ нее арифметическое элементов матрицы размером nxm элементов. Поместите подпрофамму в модуль. Разработайте тестирующую программу

Задание 2. Разработайте универсальную подпрограмму, удаляющую из матри­ цы размером nxm заданную строку и столбец. Поместите подпрограмму в модуль. Разработайте тестирующую программу.

5.6. Параметры процедурного типа

Параметры процедурного типа используют тогда, когда нужно передать в подпрограмму имена процедур и функций.

Для объявления процедурного типа используют заголовок подпрограм­ мы, в котором отсутствует имя, например:

Туре proc=procedure (a,b,c:real;Var d:real): func=function(x: real):real;

Значениями переменных процедурных типов являются идентификаторы процедур и функций с соответствующими заголовками:

Var f:func;

/:фп1;...

Процедуры или функции, идентификаторы которых будут передаваться в качестве параметров процедурного типа, по правилам языка необходимо компилировать в режиме дальнего вызова (с указанием директивы компиля­ тора {$Р+}или служебного слова far). В этом режиме при вызове подпро­ грамм используются длинные 4-байтовые адреса (см. параграф 7.1) в отли­ чие от коротких 2-байтовых адресов, которые применяются для адресации подпрограмм, объявленных в основной программе или ее подпрограммах.

166

5. Модульное программирование

Примечания: 1. Если процедуры или функции описываются в интерфейсной части моду­ ля (см. параграф 5.2), то по умолчанию они вызываются в режиме дальнего вызова, поэтому специально это оговаривать не надо.

2. Стандартные процедуры и функции, описанные в модуле System, по умолчанию явля­ ются функциями ближнего вызова. Если имена этих подпрограмм необходимо передавать че­ рез параметры, то надо описать собственную подпрограмму с указанием режима дальнего вы­ зова, в теле которой будет находиться вызов стандартной подпрограммы, и использовать ее вместо стандартной подпрограммы.

Пример 5.10. Разработать подпрограмму, которая возвращает массив значений произвольной функции при заданных интервале изменения аргу­ мента [а,Ь] и количестве точек п.

Имя функции будем передавать в подпрограмму через параметр проце­ дурного типа. Массив значений будем описывать как открытый:

UnitSFun;

Interface

Type func-functwn(x:real):real;

Procedure TabFun(f:func;a,b:real;n:integer;

Var Masf:array of real);

Implementation

Procedure TabFun;

Var h.real; i:integer;

Begin

h;=(b-a)/(n'l);

for i:=0 to n-l do Masf[i]—f(a+h*i);

End;

End

Основная программа должна описать конкретную функцию как функ­ цию дальнего вызова. Для функции sin создается специальная функция даль­ него вызова.

Program ex; Uses SFun;

Var masFl: array[L, 10] of real; masF2:array[L. 20] of real; i:integer;

function Fl(x:real):real; far; Begin Fl:-sin(x); end; function F2(x:real):real; far;

Begin F2:-exp(x)+cos(x); end; Begin

WriteLnC Таблица значений функции sin x:); TabFun(FIA2J0,masFI);

167

Часть 1. Основы алгоритмизации и процедурное программирование

for i:=l to JO do Write(masFl[i]:7:l); Writeln;

WriteLnC Таблица значений функции exp x+cos x:); TabFun(F2A2,20,masF2);

for i:=l to 20 do Write(masF2[i]:7:l); Writeln;

End

Задания для самопроверки

Задание 1. Разработайте процедуру вычисления производных функции у(х) по формулам Лагранжа в трех соседних точках, отстоящих на величину шага h:

Уо' = (-ЗУо + 4У1 -У2У2Ь; УГ = (-Уо + У2У2Ь; Уг'= (Уо^У1+Зу2)/2Ь. Поместите процедуру в модуль. Разработайте тестирующую программу.

Задание 2. Разработайте процедуру определения корня функции на заданном отрезке. Поместите процедуру в модуль. Разработайте тестирующую программу.

5.7.Рекурсия

Вматематике строгое определение некоторых понятий может опираться на то же понятие. Такие определения называют рекурсивными или индук­ тивными. Например, рекурсивно определяется факториал:

N1= I	1,	еслиЫ=0;
I	Nx(N-l)!,	еслиК>0.

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

В программировании/76?/cy/?cwe;/(9w называется подпрограмма, которая в процессе выполнения вызывает сама себя.

Различают два вида рекурсии подпрограмм:

•прямая или явная рекурсия - характеризуется существованием в теле подпрограммы оператора обращения к самой себе;

•косвенная или неявная рекурсия - образуется при наличии цепочки вызовов других подпрограмм, которые в конечном итоге приведут к вызову исходной.

168

5. Модульное программирование

Каждое обращение к рекурсивной подпрограмме вызывает независи­ мую активацию 3tofi подпрограммы. Совокупность данных, необходимых для одной активации рекурсивной подпрограммы, называется фреймом акmueaifuu.

Фрейм активации включает:

•копии всех локальных переменных подпрограммы;

•копии параметров-значений;

•четырехбайтовые адреса параметров-переменных и параметров-кон­

стант;

•копию строки результата (для функций типа string);

•служебную информацию - около 12 байт, точный размер этой облас­ ти зависит от способа вызова (ближний или дальний) и внутренней органи­ зации подпрограмм.

Пример 5.11. Разработать программу определения наибольшего общего делителя двух чисел, используя алгоритм Евклида.

Нерекурсивный вариант этого алгоритма уже был рассмотрен в приме­ ре 1.2. Рекурсивный вариант будем строить исходя из двух утверждений.

Базисное утверэюдение: если два числа равны, то их наибольший общий делитель равен этим числам.

Рекурсивное утверждение: наибольший общий делитель двух чисел ра­ вен наибольшему общему делителю их разности и меньшего из чисел.

Рекурсивная подпрограмма может быть реализована и как процедура, и как функция. При реализации в виде процедуры список параметров кроме чисел А и В включает параметр-переменную R. Через этот параметр проце­

дура возвращает результат (рис. 5.10, а). Текст					программы, реализующий ва­
риант с рекурсивной процедурой, представлен ниже.
ПЧос1(А,ВД))					Гыос1(А,В) J
да	А=В	нет		да	А-В	нет
R=A	да	А>В	нет		да	А>В	нет
				Nod = A
	Nod		Nod		Nod =		Nod =
	(А.В,ВД)		(A,B-A,R)		Nod(A-B,B)		Nod(A,B-A)
			I				I
(	Return	j			( Return	j
	a				6

Рис. 5.10. Схема алгоритма Евклида:

а - с использованием рекурсивной процедуры; о - с использованием рекурсивной функции

169

Часть 1. Основы алгоритмизации и процедурное программирование

Фрейм		1	Служебная информация
			Адрес возврата
активации		[_
	<		Адрес	Параметр-переменная
третьего		Г	результата
вызова		1	Ь = 4	Параметры-значения
	N		а~4
		1
Фрейм			Служебная информация
			Адрес возврата
активации		1
	<		Адрес	] Параметр-переменная
второго		Г	результата
вызова		1	Ь - 8	Параметры-значения
	>		а = 4
Фрейм			Служебная информация
			Адрес возврата
активации		|_
	<		Адрес	Параметр-переменная
первого		Г	результата
вызова		1	Ь « 8	Параметры-значения
	ч1		а=12
				J
		V	,

2 байта

Рис. 5.11. Заполнение стека при выполнении рекурсивной подпрограммы

Program ex;

Var a,b,r:integer;

Procedure nod(a,b:inieger; var rnnteger);

Begin ifa-b then r:-a {базис}

else ifa>b then nod(a'b,b,r) else nod(a,lhayr)

End;

Begin ReadLn(a,b); nod(a,b,r);

WriteLn(r);

End,

При выполнении программы фреймы активации будут размещаться в стеке - специальным образом организованной памяти. Например, для а=12 и Ь=8 в момент завершения нерекурсивной третьей активации стек будет вы­ глядеть, как показано на рис. 5,11 (запись в стек идет словами, т. е. по 2 бай­ та, как и изображено на рисунке).

Если реализовать вариант с ре1^рсивной функцией (рис. 5.10, б), то фрейм активации уменьшится, так как сократится список параметров. Соот­ ветствующая программа будет выглядеть следующим образом:

Program ex;

Var а,b,r:integer;

Function nod(a,b:integer).integer; begin ifa=b then nod:'=a {базис}

170