Файл: Вспомогательные алгоритмы.doc

for i:=2 to k do

if mx<z[i] then mx:=z[i];

end;

Begin {исполняемая часть программы}

writeln(‘ввод массива х из 10 элементов’);

Vvod(x,n);

writeln(‘ввод массива y из 20 элементов’);

Vvod(y,m);

writeln(‘ввод массива z из 30 элементов’);

Vvod(z,r);

max(x, n, s1);

max(y, m, s2);

max(z, r, s3);

s:=(s1+s2+s3)/3;

writeln(‘среднее=’, s:10:3);

readln;

end.

Пример 2. Дан двумерный массив (матрица) размера m*n. Упорядочить элементы каждой строки этого массива в порядке возрастания, применить для этого алгоритм сортировки выбором в виде процедуры.

Program Poriadok;

const m=5; n=10; {5 строк , 10 столбцов }

type matrica=array[1..m,1..n] of integer;

mas=array[1..n] of integer;

var a:matrica;

b:mas; { b – строка матрицы – массив длины n }

i, j: integer;

procedure Vvod(var x:matrica); {описание процедуры матричного ввода}

var i, j: integer;

begin

for i:=1 to m do

begin for j:=1 to n do

read(x[i,j]);

readln;

end;

end;

procedure Select(var y:mas); {описание процедуры сортировки}

var i, j, c, k: integer; {y – формальный параметр, строка}

begin

for j:=1 to n-1 do

begin c:=y[j];

k:=j;

for i:=j+1 to n do

if c>y[i] then k:=i;

c:=y[i];

y[j]:=y[k];

y[k]:=c;

end;

end;

Begin {раздел операторов}

writeln(‘ввод матрицы’);

Vvod(a);

for i:=1 to m do {блок обработки матрицы}

begin

for j:=1 to n do

b[j]:=a[i,j]; {берем строку b из матрицы}

Select(b);

for j:=1 to n do

a[i,j]:=b[j]; {возвращаем отсортированную строку в матрицу а}

end;

writeln(‘получена матрица’); {матричный вывод матрицы а}

for i:=1 to m do

begin

for j:=1 to n do write(a[i,j],’_’ );

writeln;

end;

readln;

End.

---

Локальные и глобальные параметры (переменные).

Имена, описанные в теле процедуры (это i, j –в процедуре Vvod; i, j, c, k –в процедуре Select)-называются локальными параметрами, областью их действия является только тело процедуры, в которой они описаны. Если одно и то же имя (например, i, j) описано и в основной программе, и в теле процедуры, то эти имена воспринимаются компилятором, как совершенно различные, т.к. имя, описанное в основной программе отменяется для процедуры, где оно повторно описано. Хотя в основной программе (блоке обработки) вызов процедуры происходит в теле цикла по i и j, а процедура Select сама содержит циклы по i и j, однако никакой ошибки не возникает, т.к. эти переменные хранятся в различных местах памяти.

Если имя описано в основной программе, а в процедуре используется без описания, то такой параметр называется глобальным (такими являются n, m в процедуре Vvod и параметр n в процедуре Select). Областью действия таких параметров является как программа, так и тело процедуры.

Таким образом, обмен информацией между основной программой и подпрограммами может осуществляться не только с помощью формальных и фактических параметров, но и с помощью глобальных параметров. За счет использования глобальных параметров можно писать процедуры и функции совсем без параметров в заголовке.

Рекурсивные подпрограммы.

Рекурсией называется ситуация, когда подпрограмма вызывает саму себя. В математике давно используется рекурсивное определение. Рекурсия в математике – это описание объекта, содержащее ссылку на сам описываемый объект. Рекурсия позволяет сокращать описание объекта.

Определение факториала:

1)без рекурсии:

n!=

1, n=0

1*2*..*n, если n>0

2)c рекурсией:

n!=

1, n=0

(n-1)!*n, n>0

C видом определения величины связан алгоритм ее вычисления, поэтому основываясь на рекурсивном определении n! можно записать соответствующий рекурсивный алгоритм.

Язык Pascal является одним из алгоритмических языков, в котором допустимо рекурсивное описание подпрограмм. Рекурсия в подпрограмме – это обращение к самой себе в теле подпрограммы. Например, для подпрограммы-функции можно сказать, что функция вызывает себя рекурсивно, если имя функции внутри ее описания используется в правой части оператора присваивания.

---

Покажем это на примере подпрограммы функции вычисления n! в одном случае с рекурсией, в другом-без нее.

№1 без рекурсии

Запишем подпрограмму-функцию Fact1 с использованием локальной переменной fact.

Function Fact1(n:integer):longint;

var fact:longint;

i:integer;

begin

fact:=n;

for i:=n-1 downto 2 do

fact:=fact*i;

Fact1:= fact;

end;

№2 с рекурсией

Function Fact2(n:integer):longint;

begin

if n=0 then Fact2:=1

else Fact2:=Fact2(n-1)*n;

end;

Если в основной программе обратиться к функции Fact2, например:

Begin

……………..

a:=Fact2(4);

……………..

Еnd.

то будут выполнены действия:

a:=Fact2(3)*4;

a:=Fact2(2)*3*4;

a:=Fact2(1)*2*3*4;

a:=Fact2(0)*1*2*3*4;

a:=1*1*2*3*4=24

Рекурсивный процесс закончен.

Здесь при каждом новом обращении к подпрограмме функции Fact2 фактические параметры, которые она использует, записываются в стек (Stack).

Структура типаLIFO

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

1. с помощью цикла (пример Function Fact1).

2. с помощью рекурсии, т.е. вложения одной операции в другую (пример Function Fact2)

Примеры 1 и 2 демонстрируют, прежде всего, различие между циклом и рекурсией. Fact1 использует вспомогательную локальную переменную fact. Рекурсивная функция Fact2 обходится без вспомогательных переменных. Однако выполнение рекурсивных подпрограмм приводит к многократным обращениям к ним самим. Это увеличивает время выполнения. Кроме того, есть опасность переполнения стека, в котором записываются адреса возвратов из подпрограммы, а также размещаются значения фактических параметров. Поэтому использование рекурсивных подпрограмм с одной стороны сокращает запись программы, делая ее более понятной, а с другой стороны увеличивает затраты памяти и машинного времени.

---

Косвенная рекурсия.

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

1) 2)

Пример: Две процедуры вызывают друг друга взаимно.

Program primer;

………………….

procedure А1(k:integer);

begin

………………….

A2(k);

………………….

end;

procedure А2(i:integer);

begin

…………………...

A1(i);

end;

begin

………. {раздел операторов}

end.

В Pascal должно выполняться правило, чтобы имя до его использования было описано, поэтому обращение к процедуре А2 в теле процедуры А1 будет ошибочным. Чтобы этого избежать используется опережающее описание подпрограммы, в котором записывается только заголовок подпрограммы с директивой Forward. Затем ниже эта подпрограмма должна быть описана полностью, причем в заголовке достаточно записать только имя подпрограммы без формальных параметров

Program n;

………………….

procedure A2(i:integer);

Forward;

procedure A1(k:integer);

begin

…………………

А2(k);

…………………

end;

procedure A2; {без формальных параметров}

begin

…………………

A1(i);

…………………

end;

begin

…………………

end.

Процедурные типы.

В списке формальных параметров процедуры или функции могут быть параметры, означающие вызов той или иной подпрограммы, т.е. одна и та же процедура (или функция) может обращаться к различным процедурам или функциям при каждом новом обращении к ней. В ТP и ОP для реализации этой возможности предусмотрен специальный процедурный тип. Он позволяет указать, какой вид подпрограмм можно использовать в качестве параметра и с какими формальными параметрами должны быть эти подпрограммы. Процедурный тип описывается в разделе Type следующим образом:

Type

<имя типа>= Procedure(<список формальных параметров>);

---

<имя типа>= Function(<список формальных параметров>):<тип функции>;

Затем в списке формальных параметров основной процедуры <имя типа> используется при описании параметра:

<имя переменной>:<имя типа>;

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

Здесь будет применен параметр – функция, как параметр процедурного типа. Этот параметр будет являться параметром-значением процедуры. В качестве фактического параметра для него будет использована та или другая функция с параметрами требуемого типа.

Program Tablica;

type func=function(x, y:integer):integer; {описание процедурного типа}

function Add(x, y:integer):integer; far; {описание функции сложения}

begin

Add:=x+y;

end;

function Multiply(x, y:integer):integer; far; {описание функции умножения}

begin

Multiply:=x*y;

end;

procedure PrintTable(a, b:integer;operation:func); {процедура печати}

var i, j:integer;

begin

for i:=1 to a do

begin

for j:=1 to b do write(operation(i,j):5); {5-формат печати}

readln;

end;

writeln;

end;

begin {исполняемая часть программы}

PrintTable(10,10,Add);

PrintTable(10,10, Multiply);

end.

Чтобы правильно описать заголовок процедуры PrintTable необходимо предварительно описать имя процедурного типа, который затем используется для описания формального параметра operation. При обращении к процедуре PrintTable формальный параметр operation процедурного типа func заменяется фактическими параметрами – функциями Add и Multiply.

Отметим, что если подпрограмма используется для переменных процедурного типа, то в Turbo Pascal она независимо от своего положения должна компилироваться нестандартным образом. В этом случае в ней можно использовать директиву far или же ключ компилятора {$F+}.

В ОР это не обязательно.

20

---