В Турбо Паскале предусмотрен механизм создания новых типов, которые принято называть пользовательскими или конструируемыми. Их можно создавать на основе стандартных и ранее созданных типов. Описание новых типов происходит в разделе TYPE. После этого можно в разделе Var создавать переменные этих типов. Также, можно сразу описывать новый тип при создании переменной в разделе Var. В этой главе мы рассмотрим следующие пользовательские типы:

перечисляемый тип,

тип-диапазон,

массивы,

записи.

ПЕРЕЧИСЛЯЕМЫЙ ТИП

Перечисляемый тип задается перечислением тех значений, которые он может получать. Каждое значение должно являться идентификатором (смотри главу Алфавит языка) и располагаться в круглых скобках через запятую. Количество элементов в перечислении не более 65536. Вводить и выводить переменные перечисляемого типа запрещено. Перечислимый тип является порядковым (смотри главу Типы данных), поэтому к переменным такого типа можно применять функции Ord, Pred, Succ. Функция Ord возвращает порядковый номер значения начиная с нуля.

ПРИМЕР: Объявление перечисляемых типов.

Type Colors = (Red,Green,Blue);

Numbers = (Zero,One,Two,Three,Four,Five);

var c:Colors; n:Numbers;

begin

c:=Red; write(Ord(c)); {0}

n:=Four; write(Ord(n)); {4}

c:=Succ(c); {c=Green}

for n:=One to Five do write(Ord(n)); {12345}

end.

Следует отметить, что стандартные типы byte, word, char и boolean также можно считать вариантами перечислимого типа.

ТИП-ДИАПАЗОН

Тип-диапазон также называют ограниченным или интервальным типом. Он является подмножеством своего базового типа, в качестве которого может выступать любой порядковый тип кроме типа-диапазона. Тип-диапазон наследует все свойства своего базового типа. Имеются две стандартные функции, работающие с этим типом: High(x)- возвращает максимальное значение типа-диапазона, к которому принадлежит переменная x; Low(x) - возвращает минимальное значение.

ПРИМЕР: Объявление типа-диапазон.

type Numbers = (Zero,One,Two,Three,Four,Five);

Num = Two .. Four; {диапазон на базе типа Numbers}

Abc = 'A' .. 'z'; {все английские буквы : диапазон на базе типа Char}

Digits = 0 .. 9; {цифры}

var n:Num; c,d:Abc; x:integer;

begin

n:=Four; writeln(Ord(n)); {4 как в базовом типе}

n:=Succ(n); { ОШИБКА (следующее значение вне диапазона)}

read(c,d);

if c=d then write('одинаковые буквы');

writeln(Low(c),' .. ',High(c)); { A .. z }

writeln(Low(x),' .. ',High(x)); { -32768 .. 32767 }

end.

В тексте программы на Турбо Паскале могут встречаться директивы компилятору, которые также называют опциями. Опции {$R+} и {$R-} позволяют включать и отключать проверку соблюдения границ при работе с диапазонами. Когда проверка включена, при нарушении границ диапазонов происходит аварийное завершение работы программы. В другом случае ответственность за возможные ошибки лежит на программисте.

МАССИВЫ

Массив - это упорядоченная структура однотипных данных, хранящая их последовательно. Доступ к элементу массива осуществляется через его индекс. Массивы описываются следующим образом:

Имя типа = ARRAY [ диапазоны индексов ] OF тип элемента массива;

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

ПРИМЕР: Три способа описания одного и того же типа массива:

type {1} M1 = array [0..5] of integer;

M2 = array [char] of M1;

M3 = array [-2..2] of M2;

{2} M3 = array [-2..2] of array [char] of array [0..5] of integer;

{3} M3 = array [-2..2,char,0..5] of integer;

var A:M3;

{Обращаться к элементам массива можно следующим образом:}

begin

read(A[-1,'a',3]);

read(A[1]['x'][0]);

A[1]['c',1]:=100;

end.

Глубина вложенности, т.е. количество индексов, при определении массивов не ограничена. Играет роль только суммарный объем данных в программе. В стандартном режиме работы Турбо Паскаля этот объем ограничен размерами сегмента, т.е. 64 килобайта. Целиком над массивами допускается применение только операции присваивания массивов (подмассивов) одинаковых типов. Остальные операции должны выполняться поэлементно.

ПРИМЕР: Вычисление значения многочлена степени N, коэффициенты которого находятся в массиве A в точке X по схеме Горнера.

Pn(x) = A[0]*X^n + A[1]*X^(n-1) + ... + A[n-1]*X + A[n] =

= (...((A[0]*X + A[1])*X + A[2])*X + ... + A[n-1])*X + A[n].

program Scheme_Gorner;

type Mas = array[0..100] of integer;

var A:Mas; i,j,n:integer; x,p:real;

begin

write('степень многочлена = '); read(n);

writeln('введите целые коэффициенты : ');

for i:=0 to n do read(A[i]);

write('значение X = '); read(x);

p:=0;

for i:=0 to n do p:=p*x+A[i];

writeln('Pn(X) = ',p);

end.

ЗАПИСИ

Запись - это стpуктуpа данных, которая может содержать информацию разных типов, объединенную под одним названием. Компоненты записи называются полями. Их фиксиpованное число. Описание записей имеет следующую стpуктуpу:

Имя типа = RECORD

список полей 1 : тип 1;

- - -

список полей N : тип N;

CASE поле выбора : тип OF

значение 1 : (полей 1 : тип 1 )

END;

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

Список полей может состоять из двух разделов: постоянной и вариантной части. В постоянной части идет перечисление полей записи (идентификаторов) с указанием их типов. Синтаксис такой же, как в разделе var.

ПРИМЕР: Пример объявления типа запись.

type Men = Record

FIO,Adress : string;

Year : byte;

End;

var A,B : Men;

Для обращения к полям записи указывается имя переменной типа запись, точка, имя поля, напpимеp:

begin

A.FIO:='Иванов И.И.';

A.Adress:='пp. Ленина, д. 40, кв. 10';

A.Year:=1981;

end.

После описания постоянных полей может следовать вариантная часть, которая может быть только одна и имеет вид

CASE поле выбора : тип OF

значение 1 : (список полей 1);

- - -

значение N : (список полей N);

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

Все варианты располагаются в одном и том же месте памяти, которой выделяется столько, сколько требуется для максимального по pазмеpу варианта. Это приводит к тому, что изменение одного вариантного поля оказывает влияние на все остальные. Это увеличивает возможности пpеобpазования типов, ПРИМЕР: Запись с вариантами.

var R = Record

rem : string;

Case byte of

3 : (n:integer);

5 : (x,y,z:char);

'a' : (i,j:byte);

end;

begin

R.rem:='запись с вариантами';

R.n:=25000;

write(R.i,R.x,R.j,R.y); {168и97a}

{ord('и')=168, ord('a')=97, 168+97*256=25000}

end.

Значения выбора могут повторяться. Имена полей записи не являются переменными и, следовательно, могут повторяться, но только на разных уровнях, напpимеp:

var Rec:Record

x : real;

Sr : Record a : real; x,y : integer; end;

I : byte;

end;

Для удобства обращения к полям записей может использоваться опеpатоp присоединения

WITH переменная DO опеpатоp;

Здесь переменная - это запись, за которой может следовать список вложенных полей, напpимеp следующие три опеpатоpа эквивалентны:

With Rec,Sr Do a := x / y;

With Rec.Sr Do a := x / y;

Rec.Sr.a := Rec.Sr.x / Rec.Sr.y;

РАБОТА СО СТРОКАМИ

Тип String (строка) в Турбо Паскале широко используется для обработки текстов. Этот тип является стандартным и во многом похож на одномерный массив символов Array [0..N] of Char. Значение N соответствует количеству символов в строке и может меняться от 0 до 255. Символы, входящие в строку, занимают позиции с 1 до N. Начальный байт строки с индексом 0 содержит информацию о ее длине, т.е. это символ с кодом, равным длине строки.

Можно, также описывать переменные типа String[K], где K - целое число не больше 255. Так определяются строки с длиной не больше K. Этот тип уже не является стандартным. С символами строки можно работать как с элементами массива из символов, но в отличие от массивов, строки можно вводить целиком, сравнивать друг с другом и сцеплять операцией "+".

ПРИМЕР: Работа со строками.

var s,x,y,z:string;

begin

x:='turbo';

y:='pascal';

z:=x+' '+y; { z='turbo pascal' }

s:=''; { пустая строка }

for c:='a' to 'z' do s:=s+c; { s='abcd..xyz' }

writeln(s);

end.

Сравнение строк выполняется посимвольно в соответствии с их кодами до первого несовпадения. Если одна из строк закончилась до первого несовпадения, то она считается меньшей. Пустая строка меньше любой строки.

ПРИМЕР: Сравнение строк.

'abcd' > 'abcD' { 'd'>'D' }

'abcd' > 'abc' { 'd'>'' }

'abc' < 'axxc' { 'b'<'x' }

'abcd' = 'abcd'

Существует ряд стандартных функций и процедур для работы со строками.

Функция Length(s) выдает длину строки s.

Функция Concat(s1,s2,..,sn) возвращает строку s1+s2+..+sn.

Функция Copy(s,p,k) возвращает фрагмент строки s, который начинается в позиции p и имеет длину k.

Функция Pos(s1,s) ищет первое вхождение подстроки s1 в строку s и возвращает номер первого символа s1 в строке s или 0 если не нашли.

Процедура Delete(s,p,k) удаляет из строки s фрагмент, который начинается в позиции p и имеет длину k.

Процедура Insert(s,s1,p) вставляет в строку s подстроку s1, начиная с заданной позиции p.

Турбо паскаль позволяет производить преобразования числовых значений в строковые и наоборот. Для этого используются процедуры Str(X:n:d,S) и Val(S,X,e). Первая получает их числа X строку S с изображением этого числа, в которой не менее n символов и из них d знаков после запятой. Параметры n и d необязательные. Вторая процедура получает из строки S число X. При успешном результате e=0.

ПРОЦЕДУРЫ И ФУНКЦИИ

Турбо Паскаль позволяет выделять фрагменты программы во вспомогательные алгоритмы (ВА). Это позволяет писать хорошо структурированные программы. Языки программирования, в которых предусмотрены ВА, называются процедурно-ориентированными. Структурированные программы обычно проще в понимании и отладке.

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

Другим подходом в разработке программ является метод восходящего программирования или проектированием “снизу - вверх”. В этом случае все начинается с создания небольших ВА, из которых затем создаются более сложные ВА и, наконец, основная программа.

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

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

label

const Описание локальных меток,

type констант, типов и переменных

var

procedure Описание внутренних процедур

function и функций

begin

Операторы

end;

Описание функции имеет следующую структуру.

Function Имя (Список формальных параметров) : Тип результата;

label

const Описание локальных меток,

type констант, типов и переменных

var

procedure Описание внутренних процедур

function и функций

begin

Операторы, среди которых хотя бы один, который

присваивает имени функции значение результата

end.

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

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

Исходные данные для работы ВА можно передавать через глобальные переменные, а также через параметры. Параметры при вызове ВА называются фактическими, а параметры в заголовке ВА называются формальными.

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

По способу передачи параметры в Турбо Паскале делятся на три типа:

параметры-значения,

параметры-переменные,

параметры-константы.

Параметры-значения

При вызове процедур и функций формальным параметрам-значениям выделяется новое место в памяти и присваиваются значения фактических параметров. При этом на месте фактических параметров могут стоять выражения. Совместимость типов определяется возможностями присваивания. После выполнения подпрограммы место формальных параметров освобождается. Изменение формальных параметров не сказывается на значении фактических. Заголовок процедуры с параметрами-значениями имеет вид:

Procedure MyProc1(par1,par2 : type1; par3,par4 : type2);

Параметры-переменные

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

Такой механизм передачи данных требует, чтобы фактические параметры были переменными, причем в точности того же типа, что и формальные параметры. При описании ВА перед параметрами-переменными должно присутствовать слово var. Заголовок процедуры с параметрами-переменными имеет вид:

Procedure MyProc2(var par1,par2 : type1; var par3,par4 : type2);

Параметры-константы

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

Использовать параметры-константы рекомендуется при передаче данных большого объема с гарантией сохранения их значений. Заголовок процедуры с параметрами-константами имеет вид:

Procedure MyProc3(const par1,par2 : type1; const par3,par4 : type2);

ОТКРЫТЫЕ ПАРАМЕТРЫ-МАССИВЫ

Открытые параметры-массивы могут быть параметрами-значениями, параметрами-переменными и параметрами-константами. Они используются для передачи массивов произвольной размерности. Заголовок процедуры с открытыми параметрами-массивами имеет вид:

Procedure OpenArray(Vector : array of MyType);

Формальный параметр при этом является массивом элементов некоторого типа MyType с нулевой базой, т.е. Array [0..N-1] of MyType; где N - количество элементов массива, которое можно определить с помощью стандартной функции High.

ПРИМЕР: Увеличение вдвое всех элементов массива.

program DoubleProgram;

const n=10; m=20;

type T1 = array[1..n] of integer;

T2 = array[-m..m] of integer;

var A : T1; B : T2; k : integer;

Procedure Double(var X : array of integer);

var i : byte;

begin

for i:=0 to High(X)-1 do X[i]:=X[i]*2;

end;

begin

for k:=1 to n do read(A[k]);

for k:=-m to m do read(B[k]);

Double(A); {увеличение в 2 раза элементов массива A}

Double(B); {увеличение в 2 раза элементов массива B}

Double(k); {то же самое, что и присваивание k:=k*2}

writeln('k=',k); {напечатается: k=40 }

for k:=1 to n do write(A[k],' ');

writeln;

for k:=-m to m do write(B[k],' ');

end.

БЕСТИПОВЫЕ ПАРАМЕТРЫ

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

Procedure MyProc(var par1,par2; const par3,par4);

Перед использованием формальных параметров необходимо выполнить их приведение к какому-либо типу. Использование бестиповых параметров дает большую гибкость программе, но ответственность за их корректное применение возлагается на программиста.

ПРИМЕР: Сложение первых N байт, начиная с того же места, что и X.

program without_type;

var N:word; s:string;

{$R-} (* отключение контроля за границами диапазонов *)

function Sum(var X; N:byte):word;

type A=array[1..1] of byte;

var i:byte; s:word;

begin

s:=0;

for i:=1 to n do S:=S+A(X)[i];

Sum:=s;

end;

begin

readln(s);

writeln(Sum(s,1)); {длина строки s}

writeln(Sum(s[1],1)); {код первого символа строки s}

writeln(Sum(s[1],length(s)));

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

Существует два способа установки барьера: дополнительным элементом или вместо крайнего элемента массива.

ПРИМЕР: Поиск с барьером

program Poisk2a;

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

N,X,i:integer;

begin

read(N); {N<=100}

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

read(X);

A[N+1]:=X; {установка барьера дополнительным элементом}

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

while A[i]<>X do i:=i+1;

{repeat i:=i+1; until A[i]=X;}

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

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

end.

program Poisk2b;

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

N,X,i,y:integer;

begin

read(N); {N<=100}

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

read(X);

y:=A[N]; {сохранение последнего элемента}

A[N]:=X; {установка барьера на последнее место массива}

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

while A[i]<>X do i:=i+1;

{repeat i:=i+1; until A[i]=X;}

if (i<N) or (y=X) then

write('первое вхождение числа ',X,' в массив A на ',i,' месте')

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

A[N]:=y; {восстановление последнего элемента массива}

end.

ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК

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

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

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

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

ПРИМЕР: Поиск в упорядоченном по возрастанию массиве первого вхождения числа X.

program Poisk3a;

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

N,X,left,right:integer;

begin

read(N); {N<=100}

write('введите упорядоченный по возрастанию массив');

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

read(X);

left:=1; right:=N;

{левая и правая граница фрагмента для поиска}

while left<right do

begin

c:=(left + right) div 2;

{середина с округлением в меньшую сторону}

if X>A[c] then

{если массив упорядочен по убыванию, то if X<A[c]}

left:=c+1

{выбираем правую половину без середины, меняя left}

else right:=c;

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

end;

if X=A[left] then {здесь left = right, но не всегда = c}

write('первое вхождение числа ',X,' в массив A на ',left,' месте')

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

end.

ПРИМЕР: Поиск в массиве, упорядоченном по возрастанию сумм цифр элементов массива, последнего числа с суммой цифр равной X.

program Poisk3b;

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

N,X,left,right:integer;

{функция считает сумму цифр числа a, здесь a - локальная переменная}

function Sum(a:integer):integer;

var s:integer;

begin

s:=0; a:=abs(a);

while a>0 do

begin

s:=s + a mod 10;

a:=a div 10;

end;

Sum:=s;

end;

begin

read(N); {N<=100}

write('введите массив, упорядоченный по возрастанию сумм цифр');

{например, для N=4 : 122, -432, 88, 593}

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

read(X);

left:=1; right:=N;

{левая и правая граница фрагмента для поиска}

while left<right do

begin

c:=(left+right+1) div 2;

{середина с округлением в большую сторону}

if X>=Sum(A[c]) then left:=c

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

else right:=c-1;

{выбираем левую половину без середины, меняя right}

end;

if X=Sum(A[left]) then {здесь left = right, но не всегда = c}

write('последнее число с суммой цифр=',X,' равно',A[left], ' находится в массиве A на ',left,' месте')

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

end.

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

Простейшая задача сортировки заключается в упорядочении элементов массива по возрастанию или убыванию. Другой задачей является упорядочение элементов массива в соответствии с некоторым критерием. Обычно в качестве такого критерия выступают значения определенной функции, аргументами которой выступают элементы массива. Эту функцию принято называть упорядочивающей функцией.

Существуют различные методы сортировки. Будем рассматривать каждый из методов на примере задачи сортировки по возрастанию массива из N целых чисел.

СОРТИРОВКА ВЫБОРОМ

Идея метода заключается в том, что находится максимальный элемент массива и меняется местами с последним элементом (с номером N). Затем, максимум ищется среди элементов с первого до предпоследнего и ставится на N-1 место, и так далее. Необходимо найти N-1 максимум. Можно искать не максимум, а минимум и ставить его на первое, второе и так далее место. Также применяют модификацию этого метода с одновременным поиском максимума и минимума. В этом случае количество шагов внешнего цикла N div 2.

Вычислительная сложность сортировки выбором - величина порядка N*N, что обычно записывают как O(N*N). Это объясняется тем, что количество сравнений при поиске первого максимума равно N-1. Затем N-2, N-3, и так далее до 1, итого: N*(N-1)/2.

ПРИМЕР: Сортировка выбором по возрастанию массива A из N целых чисел.

program Sort_Vybor1;

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

N,i,m,k,x : integer;

begin

write('количество элементов массива ');

read(N);

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

for k:=n downto 2 do { k - количество элементов для поиска max }

begin

m:=1; { m - место max }

for i:=2 to k do if A[i]>A[m] then m:=i;

{меняем местами элементы с номером m и номером k}

x:=A[m]; A[m]:=A[k]; A[k]:=x;

end;

for i:=1 to n do write(A[i],' '); {упорядоченный массив}

end.

ПРИМЕР: Та же задача с одновременным выбором max и min.

program Sort_Vybor2;

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

N,i,m,k,x,p : integer;

begin

write('количество элементов массива ');

read(N);

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

for k:=1 to n div 2 do { k - номер пары max и min }

begin

m:=k; { m - место max }

p:=k; { p - место min }

{max и min ищутся среди элементов с k до n-k+1}

for i:=k+1 to n-k+1 do

if A[i]>A[m] then m:=i

else if A[i]<A[p] then p:=i;

{меняем местами элементы с номером p и номером k}

x:=A[p]; A[p]:=A[k]; A[k]:=x;

if m=k then m:=p;

{если max стоял на месте k, то сейчас он на месте p}

{меняем местами элементы с номером m и номером n-k+1}

x:=A[m]; A[m]:=A[n-k+1]; A[n-k+1]:=x;

end;

for i:=1 to n do write(A[i],' '); {упорядоченный массив}

end.

СОРТИРОВКА ОБМЕНОМ (методом "пузырька")

Идея метода заключается в том, что последовательно сравниваются пары соседних элементов массива. Если они располагаются не в том порядке, то совершаем перестановку, меняя местами пару соседних элементов. После одного такого прохода на последнем месте номер N окажется максимальный элемент ("всплыл" первый "пузырек"). Следующий проход должен рассматривать элементы до предпоследнего и так далее. Всего требуется N-1 проход. Вычислительная сложность сортировки обменом O(N*N).

ПРИМЕР: Сортировка обменом по возрастанию массива A из N целых чисел. (Базовый вариант)

program Sort_Obmen1;

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

N,i,k,x : integer;

begin

write('количество элементов массива ');

read(N);

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

for k:=n-1 downto 1 do { k - количество сравниваемых пар }

for i:=1 to k do

if A[i]>A[i+1] then

{меняем местами соседние элементы}

begin x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x; end;

for i:=1 to n do write(A[i],' '); {упорядоченный массив}

end.

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

ПРИМЕР: Сортировка обменом с проверкой факта перестановки.

program Sort_Obmen2;

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

N,i,k,x : integer; p:boolean;

begin

write('количество элементов массива ');

read(N);

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

k:=n-1; {количество пар при первом проходе}

p:=true; {логическая переменная p истинна, если были

перестановки, т.е. нужно продолжать сортировку}

while p do

begin

p:=false;

{Начало нового прохода. Пока перестановок не было.}

for i:=1 to k do

if A[i]>A[i+1] then

begin

x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x;

{меняем элементы местами}

p:=true; {и запоминаем факт перестановки}

end;

k:=k-1;

{уменьшаем количество пар для следующего прохода}

end;

for i:=1 to n do write(A[i],' '); {упорядоченный массив}

end.

Следующая модификация алгоритма сортировки обменом получается при запоминании места последней перестановки. Если при очередном проходе последней парой элементов, которые поменялись местами, были A[i] и A[i+1], то элементы массива с i+1 до последнего уже стоят на своих местах. Использование этой информации позволяет нам сделать количество пар для следующего прохода равным i-1.

ПРИМЕР: Сортировка обменом с запоминанием места последней перестановки.

program Sort_Obmen3;

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

N,i,k,x,m : integer;

begin

write('количество элементов массива ');

read(N);

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

k:=n-1; {количество пар при первом проходе}

while k>0 do

begin

m:=0;

{пока перестановок на этом проходе нет, место равно 0}

for i:=1 to k do

if A[i]>A[i+1] then

begin

x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x; {меняем элементы местами}

m:=i; {и запоминаем место перестановки}

end;

k:=m-1; {количество пар зависит от места последней перестановки}

end;

for i:=1 to n do write(A[i],' '); {упорядоченный массив}

end.

ШЕЙКЕРНАЯ СОРТИРОВКА

Этот алгоритм, по сути, является модификацией сортировки обменом. Отличие состоит только в том, что если в сортировке обменом проходы осуществлялись только в одном направлении, то здесь направление каждый раз меняется. В шейкерной сортировке также можно проверять факт перестановки или запоминать место последней перестановки. В базовом алгоритме количество двойных проходов равно N div 2. Вычислительная сложность шейкерной сортировки O(N*N).

ПРИМЕР: Шейкерная сортировка по возрастанию массива A из N целых чисел.

program Shaker;

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

N,i,k,x,j,d : integer;

begin

write('количество элементов массива ');

read(N);

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

d:=1; i:=0;

for k:=n-1 downto 1 do { k - количество сравниваемых пар }

begin

i:=i+d;

for j:=1 to k do

begin

if (A[i]-A[i+d])*d>0 then

{меняем местами соседние элементы}

begin x:=A[i]; A[i]:=A[i+d]; A[i+d]:=x; end;

i:=i+d;

end;

d:=-d;

{меняем направление движения на противоположное}

end;

for i:=1 to n do write(A[i],' '); {упорядоченный массив}

end.

СОРТИРОВКА ВКЛЮЧЕНИЕМ

Идея данного метода состоит в том, что каждый раз, имея уже упорядоченный массив из K элементов, мы добавляем еще один элемент, включая его в массив таким образом, чтобы упорядоченность не нарушилась. Сортировка может производиться одновременно со вводом массива.

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

При использовании линейного поиска вычислительная сложность сортировки включением составляет O(N*N), а при использовании двоичного поиска - O(N*LogN) (имеется в виду логарифм по основанию 2).

ПРИМЕР: Сортировка по возрастанию массива A из N целых чисел включением с линейным поиском.

program Sort_Include1;

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

N,i,k,x : integer;

begin

write('количество элементов массива ');

read(N);

read(A[1]); {for i:=1 to n do read(A[i]);}

{k - количество элементов в упорядоченной части массива}

for k:=1 to n-1 do

begin

read(x); {x:=A[k+1];}

i:=k;

while (i>0)and(A[i]>x) do

begin

A[i+1]:=A[i];

i:=i-1;

end;

A[i+1]:=x;

end;

for i:=1 to n do write(A[i],' '); {упорядоченный массив}

end.

ПРИМЕР: Сортировка по возрастанию массива A из N целых чисел включением с двоичным поиском.

program Sort_Include2;

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

N,i,k,x,c,left,right : integer;

begin

write('количество элементов массива '); read(N);

read(A[1]); {for i:=1 to n do read(A[i]);}

{k - количество элементов в упорядоченной части массива}

for k:=1 to n-1 do

begin

read(x); {x:=A[k+1];}

left:=1; right:=k;

{левая и правая граница фрагмента для поиска}

while left<right do

{двоичный поиск последнего вхождения}

begin

c:=(left+right+1) div 2;

{середина с округлением в большую сторону}

if x>=A[c] then left:=c

{берем правую половину с серединой}

else right:=c-1; {берем левую половину без середины}

end;

if x>=A[left] then left:=left+1;

{сдвигаем на 1 вправо часть массива, освобождая место

для включения x}

for i:=k downto left do A[i+1]:=A[i];

A[left]:=x;

end;

for i:=1 to n do write(A[i],' '); {упорядоченный массив}

end.

СОРТИРОВКА ХОАРА

Эту сортировку также называют быстрой сортировкой. Метод был разработан в 1962 году профессором Оксфордского университета К. Хоаром. Это прекрасный пример использования рекурсии. Рассмотрим принцип работы алгоритма при упорядочении массива A из N элементов по возрастанию.

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

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

Вычислительная сложность одного вызова данного рекурсивного алгоритма пропорциональна количеству элементов сортируемого фрагмента массива. В лучшем случае деление на части производится пополам, поэтому вычислительная сложность всего алгоритма быстрой сортировки составляет величину порядка N*LogN (логарифм по основанию 2). Вычислительная сложность в среднем того же порядка.

ПРИМЕР: Быстрая сортировка по возрастанию массива A из N целых чисел.

program Quick_Sort;

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

N,i : integer;

{В процедуру передаются левая и правая границы сортируемого фрагмента}

procedure QSort(L,R:integer);

var X,y,i,j:integer;

begin

X:=A[(L+R) div 2];

i:=L; j:=R;

while i<=j do

begin

while A[i]<X do i:=i+1;

while A[j]>X do j:=j-1;

if i<=j then

begin

y:=A[i]; A[i]:=A[j]; A[j]:=y;

i:=i+1; j:=j-1;

end;

if L<j then QSort(L,j);

if i<R then QSort(i,R);

end;

begin

write('количество элементов массива ');

read(N);

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

QSort(1,n); {упорядочить элементы с первого до n-го}

for i:=1 to n do write(A[i],' '); {упорядоченный массив}

end.

СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ВЕКТОРА ИНДЕКСОВ

В отличии от всех ранее изложенных методов сортировки, этот не является самостоятельным алгоритмом, а представляет собой идею, которую можно применять к любому из них. Идея заключается в том, что вводится дополнительный массив B, который принято называть вектором индексов. Числа в нем говорят о том, в каком порядке нужно смотреть на элементы из A, например: Массив A : 4 7 Массив B : 3 1 4 2 { A[3] A[1] A[4] A[2] }

В начале программы в вектор индексов B записываются последовательно натуральные числа от 1 до N. При работе любой сортировки вместо элемента A[i] обращаются к элементу A[B[i]]. Это сделано для того, чтобы менять местами не элементы массива A, а их индексы, т.е. элементы массива B.

МОДУЛЬ CRT (основные возможности)

Модуль Crt относится к стандартным модулям Турбо Паскаля и находится в файле turbo.tpl (Turbo Pascal Library). Для подключения модуля достаточно написать uses Crt. Модуль Crt содержит средства управления экраном в текстовом режиме и клавиатурой.

На экране используются два активных цвета: цвет текста и цвет фона. Их можно установить с помощью процедур TextColor и TextBackground, которые имеют по одному параметру: целому числу, задающему номер цвета. Для цвета текста используются числа от 0 до 15, а для цвета фона - от 0 до 7. Обе эти процедуры оказывают влияние только на последующий вывод.

Координаты на экране задаются следующим образом. Левый верхний угол имеет координаты (1,1), а правый нижний (80,25). Можно вводить относительные координаты, объявляя окно с помощью процедуры Window(x1,y1,x2,y2), где x1,y1 - абсолютные координаты левого верхнего, а x2,y2 - правого нижнего угла окна. После этого все процедуры и функции кроме Window используют относительные координаты. Вернуться к работе со всем экраном можно, написав Window(1,1,80,25). С помощью процедуры GotoXY(x,y) можно установить курсор в заданную позицию окна, а с помощью пары функций WhereX и WhereY без параметров можно узнать текущие координаты курсора. Процедура ClrScr не имеет параметров и закрашивает текущее окно цветом фона.

Модуль Crt позволяет осуществлять контроль клавиатуры. Известно, что информация о нажатых клавишах поступает сначала в буфер клавиатуры и только затем считывается компьютером. Также известно, что клавиши и комбинации клавиш делятся на обычные, и управляющие. В результате нажатия обычной клавиши в буфер клавиатуры поступает ее код, который может быть от 1 до 255, а при нажатии управляющей клавиши в буфер клавиатуры поступает два кода, первый из которых 0. Функция KeyPressed не имеет параметров и возвращает истинный результат если буфер не пуст. При этом содержимое буфера не изменяется. Функция ReadKey также не имеет параметров и забирает из буфера клавиатуры очередное число, возвращая в программу символ (тип char), код которого соответствует этому числу. В случае, когда буфер пуст, функция ReadKey ожидает нажатия на клавиатуре.

ЛИТЕРАТУРА

1. Абрамов А.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. М., Наука, 1988.

2. Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию. М., Наука, 1988.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., Мир, 1979.

4. Вирт Н. Алгоритмы и структуры данных. М., Мир, 1989.

5. Епанешников А., Епанешников В. Программирование в среде Turbo Pascal 7.0. М., Диалог-Мифи, 1993.

6. Зуев Е.А. Система программирования Turbo Pascal. М., Радио и связь, 1992.

7. Зуев Е.А. Программирование на языке Турбо-Паскаль 6.0,7.0. М. Радио и связь. Веста. 1993.

8. Йодан Э. Структурное программирование и конструирование программ. М.: Мир, 1979.

9. Кенин А.М., Печенкина Н.С. Работа на IBM PC. М., АО "Книга и бизнес", 1992.

10. Кнут Д. Искусство программирования на ЭВМ. М.: МИР, т.1, 1976; т.2, 1977; т.3, 1978.

11. Липский В. Комбинаторика для программистов. М., Мир, 1988.

12. Майерс Г. Искусство тестирование программ. М.: Финансы и статистика, 1982. Гласс Р., Нуазо Р. Сопровождение программного обеспечения, М.: Мир, 1983.

13. Пильщиков В.Н. Сборник упражнений по языку Паскаль. М., Наука, 1989.

14. Поляков Д.Б., Круглов И.Ю. Программирование в среде Турбо Паскаль (версия 5.5). Изд-во МАИ, 1992.

15. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. М., Мир, 1980.

16. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. М., Нолидж, 1997.

17. Фаронов В.В. Турбо Паскаль 7.0. Практика программирования. М., Нолидж, 1997.

18. Шень А. Программирование: Теоремы и задачи. М., МЦНМО, 1995.

Страницы: 1, 2