Смекни!
smekni.com

Языки и технология программирования (стр. 6 из 8)

{сумма кодов всех символов строки s}

read(N);

writeln(Sum(N,2));

{сумма двух байт, из которых состоит N типа word}

end.

ПРОЦЕДУРНЫЕ ТИПЫ

В Турбо Паскале существует два процедурных типа: тип-процедура и тип-функция. Для объявления процедурного типа используется заголовок процедуры или функции без имени.

ПРИМЕР:

type Proc1 = Procedure (a,b,c : integer; x:real);

Proc2 = Procedure (var a,b);

Proc3 = Procedure;

Func1 = Function : real;

Func2 = Function (n:integer) : boolean;


Можно описывать переменные этих типов, например: var p1,p2:Proc1; f1,f2:Func2; Переменным процедурных типов можно присваивать в качестве значений имена соответствующих ВА. При этом нельзя использовать стандартные процедуры и функции. После такого присваивания имя переменной становится синонимом имени ВА. Переменные процедурного типа можно, также передавать в подпрограммы в виде параметров. Благодаря этому, имеется возможность создания более гибких вспомогательных алгоритмов.

РЕКУРСИЯ

Рекурсия - это способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения обращается сама к себе. С идейной точки зрения рекурсия аналогична методу математической индукции. Базе индукции соответствует база рекурсии. Предположению индукции соответствует предположение о том, что нужный ВА уже написан. Наконец, шагу индукции соответствует вызов создаваемого рекурсивного ВА. В любой рекурсии необходимо предусмотреть условие завершения процесса, т.е. когда вызова больше не происходит.

ПРИМЕР: Вычислить N-е число Фиббоначчи. (Смотри тему Циклы)

program Fib;

var n:byte;

function F(k:byte):word;

begin

if k<2 then F:=1 else F:=F(k-1)+F(k-2); {рекурсивный вызов}

end;

begin

write('введите номер числа Фиббоначчи ');

readln(N);

writeln(N,'-е число Фиббоначчи =',F(N));

readln

end.

Рекурсивный вызов может быть косвенным, или неявным. Например это происходит в случае, когда один ВА вызывает другой, а тот в свою очередь - первый. При использовании такой программной конструкции необходимо опережающее описание процедур и функций с директивой Forward. Сначала пишется только заголовок ВА со словом Forward, а реализация приводится ниже. При этом, в ней можно писать в заголовке либо только имя ВА, либо полностью повторять заголовок.

ПРИМЕР: Неявная рекурсия.

Procedure B(x:byte); forward;

Procedure A(y:byte);

begin

- - -

B(y);

- - -

end;

Procedure B;

begin

- - -

A(x);

- - -

end;

РЕКОМЕНДАЦИИ: Необходимо по возможности избегать применения рекурсии, так как большая глубина рекурсивных вызовов часто приводит к переполнению стека. В некоторых случаях проблему можно устранить, установив новый размер стека от 1024 до 65520 байт с помощью директивы

{$M размер стека, нижняя граница, верхняя граница памяти}

ТИПИЗИРОВАННЫЕ КОНСТАНТЫ

Кроме обычных констант в Турбо Паскале можно использовать типизированные константы, которые фактически являются переменными с начальными значениями. Они описываются в разделе Const в форме:

<имя типизированной константы> : <тип> = <значение>;

ПРИМЕР:

const x : integer = 10; y : real = 3.14;

A : array[1..5] of integer = (1,2,-3,24,0);

B : array[1..2,-1..1] of byte = ((1,2,3),(4,5,6));

R : record m : string[10]; d,y : integer; end =

(m : 'January'; d : 20; y : 1999);

S : string[4] = 'abcd';

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

ПРИМЕР: Использование типизированных констант


program typed_const;

var N:integer;

procedure Test;

const k:integer=1;

begin

if k<N then

begin

writeln(k,'-й вызов процедуры');

k:=k+1;

Test;

end

else writeln('последний вызов процедуры');

end;

begin

read(N);

if N>0 then Test;

end.

МОДУЛИ

Модуль (Unit) в паскале - это специальным образом оформленная библиотека определений типов, констант, переменных, а также процедур и функций. Модуль компилируется отдельно, в результате чего создается файл с расширением tpu (turbo pascal unit). Он не может быть запущен на выполнение самостоятельно, а может использоваться только из других программ. Для этого в программах указывается список имен используемых модулей в разделе Uses, после чего программа может использовать константы, типы и переменные, описанные в этих модулях.

В Турбо Паскале существует несколько стандартных модулей: System, Crt, Dos, Printer, Overlay, которые составляют библиотеку Турбо Паскаля: файл turbo.tpl (turbo pascal library). К числу стандартных модулей также относится модуль Graph.

Существует возможность создавать новые модули. Файл модуля имеет следующую структуру:

UNIT <имя модуля>;

INTERFACE

<раздел объявлений>

IMPLEMENTATION

<раздел реализации>

Begin

<раздел инициализации>

End.

Имя модуля должно совпадать с именем файла, в котором он хранится. Раздел объявлений или интерфейсная часть содержит объявления всех глобальных объектов модуля (типов, констант, переменных и подпрограмм), которые будут доступны программам, использующим этот модуль. Подпрограммы в этом разделе объявляются только заголовками. В интерфейсной части модулей нельзя использовать опережающее описание, т.е. директиву forward.

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

Раздел инициализации может отсутствовать. В этом случае можно даже не писать слово Begin, а сразу завершать модуль, написав End. В раздел инициализации входят операторы, которые будут выполняться при запуске программы, использующей модуль, перед выполнением основной программы. Разделы инициализаций выполняются в том порядке, в котором подключаются модули.

ПРИМЕР: Модуль для работы с одномерными массивами до 100 целых чисел.

{модуль описаний, глобальных для основной программы и всех модулей}

Unit Globals;

Interface

const Len=100;

type Vector = array[1..Len] of integer;

Implementation

End.

Unit Vectors;

Interface

uses Globals;

{находит максимальный элемент массива}

function Max_V(A:Vector; n:byte):integer;

{поэлементное сложение двух векторов}

procedure Add_V(A,B:Vector; n:byte; var C:Vector);

{скалярное произведение векторов}

function Scal_V(A,B:Vector; n:byte):integer;

Implementation

function Max_V; {заголовок без параметров}

var i,max:integer;

begin

max:=A[1];

for i:=2 to n do if A[i]>max then max:=A[i];

Max_V:=max;

end;

procedure Add_V;

var i:integer;

begin

for i:=1 to n do C[i]:=A[i]+B[i];

end;

function Scal_V(A,B:Vector; n:byte):integer;

{заголовок из interface}

var s:integer; i:byte;

begin

s:=0;

for i:=1 to n do s:=s+A[i]*B[i];

Scal_V:=s;

end;

End. {раздел инициализации модуля отсутствует}

АЛГОРИТМЫ ПОИСКА

Алгоритмы поиска применяются для нахождения, например, в массиве элемента с нужными свойствами. Обычно различают постановки задачи поиска для первого и последнего вхождения элемента. Во всех ниже изложенных алгоритмах будем считать, что производится поиск в массиве A из N целых чисел элемента, равного X.

ЛИНЕЙНЫЙ ПОИСК

Линейный поиск осуществляется циклом (while или repeat - until) с двойным условием. Первое условие контролирует индекс на принадлежность массиву, например, (i<=N). Второе условие - это условие поиска. В нашем случае в цикле while это условие продолжения поиска: (A[i]<>X), а в цикле repeat - until это условие завершения поиска: (A[i]=X). В теле цикла обычно пишется только один оператор: изменение индекса в массиве.

После выхода из цикла необходимо проверить, по какому из условий мы вышли. В операторе if обычно повторяют первое условие цикла. Можно говорить об успешном поиске с циклом while при выполнении этого условия, а с циклом repeat - until при его нарушении.

ПРИМЕР: Линейный поиск

program Poisk1;

var A:array[1..100] of integer;

N, X, i:integer;

begin

read(N); {N<=100}

for i:=1 to N do read(A[i]);

read(X);

i:=1; {i:=0;}

while (i<=N) and (A[i]<>X) do i:=i+1;

{repeat i:=i+1; until (i>N) or (A[i]=X);}

if i<=N then write('первое вхождение числа ',X,'

в массив A на ',i,' месте')

else write('не нашли');

end.

При поиске последнего вхождения после ввода должны идти операторы:

i:=N; {i:=N+1;}

while (i>=1) and (A[i]<>X) do i:=i-1;

{repeat i:=i-1; until (i<1) or (A[i]=X);}

if i>=1 then write('последнее вхождение числа ',X,' в массив A на ',i,' месте')

else write('не нашли');

ПОИСК С БАРЬЕРОМ

Идея поиска с барьером состоит в том, чтобы не проверять каждый раз в цикле условие, связанное с границами массива. Это можно обеспечить, установив в массив так называемый барьер: любой элемент, который удовлетворяет условию поиска. Тем самым будет ограничено изменение индекса.

Выход из цикла, в котором теперь остается только условие поиска, может произойти либо на найденном элементе, либо на барьере. Таким образом, после выхода из цикла проверяется, не барьер ли мы нашли? Вычислительная сложность поиска с барьером меньше, чем у линейного поиска, но также является величиной того же порядка, что и N - количество элементов массива.