1 Глава 4 Модульное программирование 4.1 Процедуры и функции Процедуры и функции – самостоятельные фрагменты программы, соответствующим образом оформленные и снабженные именем (программные блоки). Программный блок: Процедура: Функция:

2 Передача данных в подпрограмму Подпрограмма может получать данные двумя способами: а) неявно – с использованием глобальных переменных; б) явно – через параметры. Неявная передача: 1) приводит к большому количеству ошибок; 2) жестко связывает подпрограмму и данные. Обращение к глобальной переменной Обращение к глобальной переменной Обращение к переменной вызывающей подпрограммы

3 Передача данных через параметры Список параметров описывается в заголовке: Параметры, описанные в заголовке – формальные. При вызове подпрограммы необходимо определить фактические значения этих параметров – аргументы (константы и переменные). Формальные и фактические параметры должны соответствовать по количеству, типу и порядку: function proc(a:integer; b:single):byte; … n:= proc(5,2.1);

4 Стек Способы передачи параметров Основная программа Подпро- грамма Передача по значению Копии параметров Работа с копиями параметров Стек Основная программа Подпро- грамма Передача по ссылке Работа с параметрами через адреса Адреса параметров Параметры - значения – в подпрограмму передаются ко- пии фактических параметров, и никакие изменения этих копий не возвращаются в вызывающую программу. Параметры - переменные – в под- программу передаются адреса фактических параметров, соответственно все изменения этих параметров в подпрограмме происходят с переменными основной программы.

5 Способы передачи параметров (2) Параметры-значения при описании подпрограммы не помечаются, например: function Alpha(x:single; n:byte);. Параметры-переменные при описании подпрограммы помечаются служебным словом var, например: function Alpha(x:single; Var n:byte);. Ограничение: в качестве фактических значений параметров- переменных нельзя использовать литералы: Alpha(2.5,5); // ошибка! правильно: n:=5; Alpha(2.5,n); Параметры-константы – в подпрограмму, так же как и в случае параметров-переменных, передаются адреса фактических параметров, но при попытке изменить значение параметра компилятор выдает сообщение об ошибке; такие параметры при описании подпрограммы помечаются служебным словом const, например: function Alpha(const x:single; n:byte);.

6 Определение площади четырехугольника Площадь четырехугольника определяем как сумму площадей треугольников. Площадь треугольника определяем по формуле Герона. В качестве подпрограммы реализуем вычисление площади треугольника, поскольку эта операция выполняется два раза с разными параметрами. a b c d e

7 Схемы алгоритмов подпрограмм Формальные параметры Фактические параметры Фактическое значение параметра- переменной Формальный параметр-переменная в заголовке на схеме не выделяется Подпрограмма-функция Начало алгоритма подпрограммы Подпрограмма-процедура Завершение подпрограммы Вызов процедуры

8 Функция Program Ex4_1; {$APPTYPE CONSOLE} Uses SysUtils; Var A,B,C,D,E:single; Function Stf(const X,Y,Z: single): single; Var p:single; begin p:=(X+Y+Z)/2; Result:=sqrt(p*(p-X)*(p-Y)*(p-Z)); // или Stf:=.. end; Begin WriteLn('Input a,b,c,d,e:'); ReadLn(A,B,C,D,E); WriteLn('S=',Stf(A,B,E)+Stf(C,D,E):7:3); ReadLn; End. Локальная переменная Глобальные переменные Тип возвращаемого значения Вызов функции из выражения Вычисление возвращаемого значения

9 Процедура Program Ex4_2; {$APPTYPE CONSOLE} uses SysUtils; Var A,B,C,D,E:real; S1,S2:single; Procedure Stp(const X,Y,Z:single;var S:single); Var p:single; begin p:=(X+Y+Z)/2; S:=sqrt(p*(p-X)*(p-Y)*(p-Z)); end; Begin WriteLn('Input a,b,c,d,e'); ReadLn(A,B,C,D,E); Stp(A,B,E,S1); Stp(C,D,E,S2); WriteLn('S= ',S1+S2:7:3); ReadLn; End. Возвращаемое значение Локальная переменная Вызов процедуры Глобальные переменные

10 Параметры структурных типов Структурные типы параметров должны быть предварительно объявлены. Пример. Функция вычисления суммы элементов массива.

11 Программа Program Ex4_3; {$APPTYPE CONSOLE} Uses SysUtils; Type mas=array[1..10] of integer; Var a:mas; i,n:integer; Function sum(b:mas; n:integer):integer; Var s:integer; i:integer; Begin s:=0; for i:=1 to n do s:=s+b[i]; Result:=s; End; Begin Write('Input n:'); ReadLn(n); for i:=1 to n do Read(a[i]); ReadLn; WriteLn('Sum =',sum(a,n)); ReadLn; End. Предварительное объявление типа параметра Объявление параметра структурного типа Фактический параметр структурного типа

Модули Модуль – это автономно компилируемая коллекция программных ресурсов, предназначенных для использования другими модулями и программами. Ресурсы – переменные, константы, описания типов и подпрограммы. Все ресурсы, определенные в модуле делят на: 1) внешние – предназначенные для использования другими программами и модулями. 2) внутренние – предназначенные для использования внутри модуля. Структура модуля: Unit ; Interface Implementation [ Initialization [ Finalization ]] End. Имя модуля должно совпадать с именем файла, в котором он описан.

13 Подключение модуля к программе Подключение модуля осуществляется по имени: Uses,,...; Объявление модулей в файле проекта Если: к проекту подключается модуль, который находится в каталоге, не совпадающем с каталогом проекта и не указанном в путях компилятора; в путях компилятора имеется несколько модулей с одинаковыми именами, то необходимо указать местонахождение модуля: Uses Strings in 'C:\Classes\Strings.pas'; Uses Strings in '..\Strings.pas'; {относительно тек. кат.} Модули, объявленные в файле проекта с указанием in …, считаются частью проекта, т. е. доступны через средства работы с проектом среды. Использование указания in … в файлах с расширением pas не допустимо.

14 Режимы компиляции программы с модулями 1. Compile – компилируется только основная программа, все модули должны быть предварительно откомпилированы в файлы.tpu и размещены либо в текущем каталоге, либо в одном из каталогов, указанных как источники файлов.tpu в настройках среды. 2. Make – модули, для которых не обнаружены файлы.tpu, компилируются из соответствующих файлов.pas, которые должны находиться в текущем каталоге или в каталогах, указанных в настройках среды в качестве источников исходных файлов модулей. 3. Build – все ранее откомпилированные модули.tpu игнорируются и все модули компилируются из своих исходных файлов заново. В процессе отладки модулей целесообразно использовать режим Build, а при отладке программы – режим Compile.

15 Модуль с функцией вычисления суммы Unit Summa; { должен находиться в файле Summa.pas} Interface type mas=array[1..10] of integer; function sum(b:mas;n:integer):integer; Implementation Function sum; Var s:integer;i:integer; begin s:=0; for i:=1 to n do s:=s+b[i]; Result:=s; end; End.

16 Программа вычисления суммы Program Ex4_4; {$APPTYPE CONSOLE} Uses SysUtils, Summa in 'Summa.pas'; Var a:mas; i,n:integer; Begin Write('Input n:'); Readln(n); for i:=1 to n do Read(a[i]); ReadLn; WriteLn('Sum =',sum(a,n)); ReadLn; End.

17 Правило видимости имен ресурсов модуля Ресурсы модуля перекрываются ресурсами программы и ранее указанных модулей. Для доступа к перекрытым ресурсам модуля используют точечную нотацию:. Пример: Unit A; Interface Var X:real; … End. Unit A; Unit В; Program G; Uses A,B; Program ex; Uses A; Var X:integer; Begin X:=10; A.X:=0.45; …

Создание универсальных подпрограмм Открытые массивы и строки Открытый массив – конструкция описания типа массива без указания типа индексов. Используется только при объявлении формальных параметров. Примеры: array of single; array of integer; Индексы открытого массива всегда начинаются с 0. Размер можно: передать через дополнительный параметр; получить, используя функцию High( ).

19 Функция с открытым массивом Unit Summa2; Interface Function sum(b:array of integer; n:integer):integer; Implementation Function sum; var s:integer; i:integer; begin s:=0; for i:=0 to n-1 do s:=s+b[i]; Result:=s; end; End. Размер массива

20 Программа, использующая функцию с открытым массивом Program Ex4_5; {$APPTYPE CONSOLE} Uses SysUtils, Summa2 in 'Summa2.pas'; Var a:array[1..10] of integer; i,n:integer; Begin Write('Input n:'); ReadLn(n); for i:=1 to n do Read(a[i]); ReadLn; WriteLn('Sum=',sum(a,n)); ReadLn; End.

21 Открытые строки Для строк, передаваемых в подпрограмму как параметр- переменная, Паскаль осуществляет контроль длины строки. Чтобы избежать его необходимо использовать «открытые» строки. Пример. Программа, формирующая строку из букв латинского алфавита. Unit Stroka; Interface Procedure Add(var s:openstring); Implementation Procedure Add; Var Ch:char; begin Ch:=s[length(s)]; s:=s+chr(succ(Ord(Ch))); end; End.

22 Программа program Ex4_6; {$APPTYPE CONSOLE} uses SysUtils, Stroka in 'Stroka.pas'; Var S:string[26];i:integer; Begin s:='A'; for i:=2 to 26 do Add(s); WriteLn(s); ReadLn; end.

Нетипизированные параметры Нетипизированные параметры – параметры-переменные, тип которых при объявлении не указан. Для приведения нетипизированного параметра к определенному типу можно использовать: 1) авто определенное преобразование типов: Procedure Proc(Var:a);......b:= Integer(а)+10;... 2) наложенное описание переменной определенного типа: Procedure Proc(Var:a);... Var r:real absolute a;...

24 Суммирование чисел различных типов Unit Summa4; Interface type ttype=(treal,tinteger); function sum(var x;n:integer;t:ttype):real; Implementation function sum; Var mr:array[ ] of real absolute x; mi:array[ ] of integer absolute x; s:real;i:integer; begin s:=0; if t=treal then for i:=1 to n do s:=s+mr[i] else for i:=1 to n do s:=s+mi[i]; sum:=s; end; End. Параметр перечисляемого типа, определяющий тип элементов массива Описанный массив накладывается по адресу параметра

25 Программа program Ex4_7; {$APPTYPE CONSOLE} uses SysUtils, Summa4 in 'Summa4.pas'; Var a:array[1..10] of integer; b:array[1..15] of real; i,n:integer; Begin for i:=1 to 10 do Read(a[i]); ReadLn; WriteLn('Sum=',sum(a,10,tinteger):8:1); for i:=1 to 15 do Read(b[i]); ReadLn; WriteLn('Sum=',sum(b,15,treal):8:1); ReadLn; end.

26 Универсальные подпрограммы с многомерными массивами B[i,j] A[(i-1)*q+j] m n p q q m q m B A

27 Транспонирование матрицы В транспонированной матрице B: b[i,j] = a[j,i] Если i=1, то первый номер столбца j=2 i=2 j=3 i=3 j=4 i=4 j=

28 Универсальная подпрограмма Unit Matrica; Interface procedure Tran(Var x;n,q:integer); Implementation procedure Tran; Var a:array[ ] of real absolute x; i,j:integer; t:single; begin for i:=1 to n-1 do for j:= i+1 to n do begin t:=a[(i-1)*q+j]; a[(i-1)*q+j]:=a[(j-1)*q+i]; a[(j-1)*q+i]:=t; end; End.

29 Программа Program Ex4_8; {$APPTYPE CONSOLE} Uses SysUtils, Matrica in 'Matrica.pas'; Var a:array[1..10,1..10] of single; i,j:integer; Begin WriteLn('Input a(5*5):'); for i:=1 to 5 do begin for j:=1 to 5 do Read(a[i,j]); ReadLn; end; tran(a,5,10); WriteLn('Result:'); for i:=1 to 5 do begin for j:=1 to 5 do Write(a[i,j]:6:2); WriteLn; end; ReadLn; End.

Параметры процедурного типа Параметры процедурного типа используются для передачи в подпрограмму имен процедур и функций. Для объявления процедурного типа используется заголовок подпрограммы, в котором отсутствует имя: Type proc=procedure (a,b,c:real;Var d:real); func=function(x:real):real; Значениями переменных процедурных типов являются идентификаторы процедур и функций с соответствующими заголовками: Var f:func;... f:=fun1;...

31 Табулирование функций Табулирование – построение таблицы значений: x y Рассчитыва- ется лишний N+1 элемент Исключение расчета лишнего элемента за счет дополнительной проверки Расчет значения аргумента требует больше времени

32 Подпрограмма табулирования функции Unit SFun; Interface Type func=function(x:Single):Single; Procedure TabFun(f:func;a,b:Single;n:integer; var Masf,MasX:array of Single); Implementation Procedure TabFun; Var h,x:Single; i:integer; Begin h:=(b-a)/(n-1); for i:=0 to n-1 do begin MasX[i]:= a+h*i; Masf[i]:=f(MasX[i]); end; End; End.

33 Программа Program Ex4_9; {$APPTYPE CONSOLE} Uses SysUtils, SFun in 'SFun.pas'; Var masF1,masX1:array[1..10] of Single; masF2,masX2:array[1..20] of Single; i:integer; function F1(x:Single):Single; Begin F1:=sin(x); end; function F2(x: Single):Single; Begin F2:=exp(x)+cos(x); end;

34 Программа(2) Begin TabFun(F1,0,2,10,masF1,masX1); WriteLn(Table 1); for i:=1 to 10 do WriteLn(masX1:4:1,masF1[i]:7:1); WriteLn(Table 2); TabFun(F2,0,2,20,masF2,masX2); for i:=1 to 20 do WriteLn(masX2:4:1,masF2[i]:7:1); ReadLn; End.

Рекурсия Основные понятия Рекурсия – организация вычислений, при которой процедура или функция обращаются к самим себе. Различают явную и косвенную рекурсии. При явной – в теле подпрограммы существует вызов самой себя, при косвенной – вызов осуществляется в подпрограммах, вызываемых из рассматриваемой. Косвенная рекурсия требует предопределения: procedure B(j:byte); forward; procedure A(j:byte); begin...B(i);... end; procedure B; begin... A(j);... end;

36 Вычисление наибольшего общего делителя Базисное утверждение: если два числа равны, то их наибольший общий делитель равен этим числам. Рекурсивное утверждение: наибольший общий делитель двух чисел равен наибольшему общему делителю их разности и меньшего из чисел a b r Фрейм активации

37 Вычисление наибольшего общего делителя (2) Program Ex4_10a; {$APPTYPE CONSOLE} Uses SysUtils; Var a,b,r:integer; Procedure nod(a,b:integer; var r:integer); Begin if a=b then r:=a else if a>b then nod(a-b,b,r) else nod(a,b-a,r) End; Begin WriteLn('Input A,B'); ReadLn(a,b); nod(a,b,r); WriteLn(r); ReadLn; End.

38 Вычисление наибольшего общего делителя (3) a b r Фрейм активации

39 Вычисление наибольшего общего делителя (4) Program Ex4_10b; {$APPTYPE CONSOLE} Uses SysUtils; Var a,b,r:integer; Function nod(a,b:integer):integer; begin if a=b then Result:=a else if a>b then Result:=nod(a-b,b) else Result:=nod(a,b-a) end; Begin WriteLn('Input A,B'); ReadLn(a,b); r:=nod(a,b); WriteLn(r); ReadLn; End.

Фрейм активации. Структура рекурсивной подпрограммы Каждое обращение к рекурсивной подпрограмме вызывает независимую активацию этой подпрограммы. Совокупность данных, необходимых для одной активации рекурсивной подпрограммы, называется фреймом активации. Фрейм активации включает локальные переменные подпрограммы; копии параметров-значений; адреса параметров-переменных и параметров-констант (4 байта); копию строки результата (для функций типа string); служебную информацию ( 12 байт, точный размер этой области зависит от способа передачи параметров).

41 Переворот строки 1) последовательное отсечение начального элемента и добавление его в конец результирующей строки: Function reverse1(const st:string):string; Begin if length(st)=0 then Result:= else Result:= reverse1(copy(st,2,length(st)-1))+ st[1]; End; Фрейм активации: V= S=ABC S=BC S=С S= Result:=… +S[1] Result:=

42 Переворот строки 2) последовательная перестановка элементов, например ABCDE EBCDA EDCBA Procedure reverse2(var ss:string; n:integer); Var temp:char; Begin if n<=length(ss) div 2 then begin temp:=ss[n]; ss[n]:=ss[length(ss)-n+1]; ss[length(ss)-n+1]:=temp; reverse2(ss,n+1); end; End; Фрейм активации: V=

43 Определение корней уравнения на заданном отрезке Базисное утверждение: Если абсолютная величина функции в середине отрезка не превышает заданного значения погрешности, то координата середины отрезка и есть корень. Рекурсивное утверждение: Корень расположен между серединой отрезка и тем концом, значение функции в котором по знаку не совпадает со значением функции в середине отрезка.

44 Определение корней уравнения на заданном отрезке (2) Program Ex4_11; {$APPTYPE CONSOLE} Uses SysUtils; Var a,b,eps,x:real; Procedure root(a,b,eps:real;var r:real); Var f,x:real; Begin x:=(a+b)/2; f:=x*x-1; if abs(f)>=eps then if (a*a-1)*f>0 then root(x,b,eps,r) else root(a,x,eps,r) else r:=x; End; Begin WriteLn('Input a,b,eps'); ReadLn(a,b,eps); root(a,b,eps,x); WriteLn('Root x=',x:9:7); ReadLn; End. Если корней на заданном отрезке нет, то произойдет зацикливание!

45 Структура рекурсивной подпрограммы «Операторы после вызова», выполняются после возврата управления из рекурсивно вызванной подпрограммы. Пример. Распечатать положительные элементы массива в порядке следования, а отрицательные элементы – в обратном порядке. Признак конца массива – 0.

46 Просмотр массива i=1 i=2 i=3 Дан массив, завершающийся нулем и не содержащий нулей в середине, например: Необходимо напечатать положительные элементы в том порядке, как они встречаются в массиве и отрицательные элементы в обратном порядке:

47 Просмотр массива Program Ex4_12; {$APPTYPE CONSOLE} Uses SysUtils; Type mas=array[1..10] of real; Var x:mas; i:integer; Procedure print(const x:mas;i:integer); Begin if x[i]=0 then WriteLn('***') else begin if x[i]>0 then WriteLn(i,x[i]); print(x,i+1); if x[i]<0 then WriteLn(i,' ', x[i]); end End;

48 Просмотр массива (2) Begin i:=0; repeat i:=i+1; Read(x[i]) until x[i]=0; print(x,1); ReadLn; End.

Древовидная рекурсия. Перестановки А,B,C ABC, ACB, BAC, BCA, CAB, CBA. Схема формирования перестановок:

50 Перестановки (2) Program Ex4_13; {$APPTYPE CONSOLE} Uses SysUtils; Type mas=array[1..3] of char; Var a:mas='ABC'; Var pole:mas; procedure Perest(n,m:integer; Const r:mas; Var pole:mas); Var r1:mas; k,j,i:integer; Begin if n>m then begin for i:=1 to m do Write(pole[i]); WriteLn; end else

51 Перестановки (3) for i:=1 to m-n+1 do begin pole[n]:=r[i]; k:=1; for j:=1 to m-n+1 do if j<>i then begin r1[k]:=r[j]; k:=k+1; end; Perest(n+1,m,r1,pole); end; End; Begin Perest(1,3,a,pole); ReadLn; End.

Полный и ограниченный перебор Пример. Расставить N ферзей на доске N*N так, чтобы они не били друг друга. Условие того, что ферзь «бьет другого»: Pole[ j ]=Pole[ i ] – одна горизонталь; |Pole[ j ]-Pole[ i ] | = | j - i | – одна диагональ. Pole

53 Дерево формирования вариантов

54 Схема алгоритма расстановки ферзей

55 Программа расстановки ферзей Program Ex4_14; {$APPTYPE CONSOLE} Uses SysUtils; Type p=array[1..100] of integer; Var pole:p; m:integer; {функция проверки перспективности комбинации} Function new_r(n:integer;pole:p):boolean; Var j:integer; Begin new_r:=true; for j:=1 to n-1 do if (pole[j]= pole[n]) or (abs(pole[j]-pole[n])=n-j) then new_r:=false; End;

56 Программа расстановки ферзей (2) Procedure ferz(n,m:integer; var pole:p); Var i:integer; Begin if n=m+1 then begin for i:=1 to m do Write(pole[i]:2); WriteLn; end else for i:=1 to m do begin pole[n]:=i; if new_r(n,pole) then ferz(n+1,m,pole); end; End;

57 Программа расстановки ферзей (3) Begin WriteLn('Input N:'); ReadLn(m); ferz(1,m,pole); ReadLn; End. Размер доски Всего вариантов Количество вызовов проц. Количество решений