{сумма кодов всех символов строки 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 - количество элементов массива.