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

3. Метод Шелла

Этот метод был предложен автором Donald Lewis Shеll в 1959 г. Основная идея этого алгоритма заключается в том, чтобы в начале ycтpанить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы. Как видно, интервал между сравниваемыми элементами (gap) постепенно уменьшается до единицы. Это означает, что на поздних стадиях сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки являются необходимыми).

4. Метод Хoopа

Этот метод, называемый также быстрой сортировкой (QuickSort), был разработан в 1962 г. (его разработал Charles Antony Richard Hoare). Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею можно реализовать многими способами.

5.2. Многомерные массивы

До сих пор мы рассматривали массивы, каждый элемент которых содержал один индекс. Такие массивы называют одномерными.

Из многомерных массивов в математике наиболее часто используют двумерные массивы – матрицы.

Описание матрицы 3 х 4:

1. Type T = Array [1..3,1..4] of Integer;

Var A:T;

1. Type T = Array [1..3] of Array [1..4] of Integer;

Var A:T;

Пример:

Type T1 = Array [1..4] of Integer;

T = Array [1..3] of T1;

Var A:T;

B: T1;

Здесь сначала описывается тип одной строки Т1, а затем, через тип строки Т1, описывается тип всей матрицы Т. В разделе переменных указывается, что А является двумерным массивом (т.е. матрицей), а В – одномерным массивом.

Пример: Найти сумму положительных элементов массива D(n,m)

n10, m20.

Program Summa;

Const n=10;

m=20;

Var i, j:Integer;

Sum: Real;

D: Array [1..n,1..m] of Real;

Begin

Sum: = 0;

For i: = 1 to n do

For j: = 1 to m do

Begin

Read (D[i,j]);

If D[i,j] > 0 then Sum: = Sum + D[i,j];

End;

Writeln (‘Sum=’,Sum);

End.

Пример: Даны две матрицы: A[N*M], B[N*M].

Найти их сумму C[N*M]= A + B.

C_ij = a_ij + b_ij

Program Summa;

Const N=3; (*количество строк*)

M=5; (*количество столбцов*)

Type Mat = Array [1..N,1..M] of Real;

Var A, B, C: Mat;

I: Integer; (*индекс строки*)

J: Integer; (*индекс столбца*)

Begin

Writeln (‘Ввести А, В’);

For I: = 1 to N do

Begin

For J: = 1 to M do

Begin

Read (A[I,J],B[I,J]);

C[I,J]:= A[I,J] + B[I,J];

End;

Readln;

End;

Writeln (‘Матрица С’);

For I: = 1 to N do

Begin

For J: = 1 to M do

Write (C[I,J]:3:1, ‘ ‘:2);

Writeln;

End;

End.

5.3. Упакованные массивы

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

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

Например, массивы А и АР описаны как

Var AP: Packed Array [1..3] of Boolean;

A: Array [1..3] of Boolean;

Обычнвй м упакованный массивы идентичны в смысле объема и характера хранимой информации, но различаются способами представления в памяти ЭВМ.

Упакованный массив можно описывать в разделе переменных или с использованием раздела типов.

Описание в разделе типов:

Type имя типа = Packed Array [имя индекса] of тип элемента;

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

Здесь служебное слово Packed указывает на то, что массив данных является упакованным.

К упакованным символьным массивам в языке программирования Паскаль относится строки символов, которые задаются либо в разделе операторов, либо в разделе констант (строки символов, а не символьные строки String, о которых речь пойдет дальше). Как известно, тип константы однозначно определяется ее записью. Поэтому если, например, в разделе констант определена константа S=’end’, то она принадлежит к типу: Packed Array [1..3] of Char.

Считается, что символьные константы имеют тип упакованных массивов:

Packed Array [1..n] of Char;

где n - длина строки.

Символьные массивы и константы могут участвовать в операциях присваивания и сравнения.

Пусть, например, описание символов массива имеет вид:

Type Mas= Packed Array [1..7] of Char;

Var A:Mas;

Тогда, можно записать такой оператор:

A:=’ZADACHA’;

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

Пример: ‘String’ < ’Strong’, т.к. в алфавите символ ‘i’ стоит раньше, чем ’o’ и его код меньше, т.е. ’i’<’o’.

Пусть, например, имеется строка: “ABCDEFG”. Эту строку можно считать массивом символов, состоящим из 8 символов, включая пробел. Если этот массив символов обозначить именем Sim, то описание примет вид:

Type T = Packed Array [1..8] of Char;

Var Sim:T;

Один элемент массива принимает значение одного символа, например:

Sim[1]=’A’;

Sim[6]=’ ’.

Элементы массива могут принимать свои значения с помощью оператора ввода Read, который располагается внутри цикла.

Пример: ввода.

1. I: = 1;

While I<=10 do Begin Read (A[I]); I:= I+1; End;

1. For I:= 1 to 46 do Read (A[I]);

Вывод массива символьных данных также организуется с использованием цикла.

Пример: Дана строка символов, обозначенная именем S1.

‘To be or not to be’

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

Program Hamlet;

Type Stroka = Packed Array [1..20] of Char;

Var S1, S2: Stroka;

I: Integer; (*счетчик символов*)

K: Integer; (*параметр цикла*)

Begin

Write (‘Ввести S1=’);

I; = 0;

While I <= 18 do

Begin

I:= I+1;

Raed (S1[I]); Readln;

End;

S2:= S1;

S2[I+1]:= ‘?’;

For K:= 1 to I+1 do Write (S2[K]);

End.

Р азрешается ввод и вывод символьных массивов целой строкой, без организации цикла.

Пример: Даны два символьных массива: А₁= ‘Suvorov’ и А₂= ‘Suhanov’. Требуется поменять их местами.

Program Zamena;

Const N =12;

Type Mas = Array [1..N] of Char;

Var A1,A2,X: Mas;

Begin

Writeln (‘A1-Who?’);

Readln (A1); {Суворов}

Writeln (‘A2-Who?’);

Readln (A1); {Суханов}

Writeln (‘происходит замена’);

X:=A1;

A1:=A2;

A2:=X;

Writeln (‘A1=’,A1);

Writeln (‘A2=’,A2);

End.

Обратите внимание, что для ввода и вывода символьных массивов здесь не применяется цикл!

5.4. Строки

Тип String (строка) в Паскале широко используется для обработки текстов и во многом похож на одномерный массив символов Array [0..N] of Char. Однако в отличие от массива количество символов в строке – переменной может меняться от 0 до N, где N – максимальное количество символов в строке. Значение N определяется в разделе объявления типа String [N] и может быть любой константой порядкового типа, но не больше 255: N 255. Можно не указывать N, в этом случае длина строки принимается максимально возможной: N = 255.

Строка трактуется как цепочка символов. К любому символу в строке можно обратится точно так же, как к элементу одномерного массива Array [0..N] of Char.

Пример:

Var st: String;

- - - - - - - - - - - - - -

if st[5]= ‘A’ then …….

Самый первый байт в строке имеет индекс 0 и содержит текущую длину строки. Первый значащий символ строки занимает второй и имеет индекс 1. Над длиной строки можно совершать необходимые действия и таким способом менять длину строки.

Пример:

Var st:String[10];

I:Integer;

- - - - - - - - - - - - - -

st[0]:=5;

Значение Ord (st[0]), то есть текущую длину строки можно получить с помощью функции length (st).

К строке можно применить операцию + (сцепление строк), например:

St:=’a’+’b’;{ ab}

St:=st+’c’; { abc}

Если длина сцепленной строки превысит максимально допустимую длину N, то «лишние» символы отбрасываются.

Пример:

Var st :String [1];

Begin st:=’123’;

Writeln(st); { 1}

End;

Кроме сцепления строк, все остальные действия над строками (и символами) реализуются с помощью встроенных функций.

1) Concat (S1<, S2, S3,…SN>)– функция типа String, сцепление строк;

2) Copy (имя строки,№ нач. символа, кол-во символов)– функция копирования;

1. Delete (имя строки,№ нач. символа, кол-во символов)– функция удаления;

2. Insert (имя подстроки, имя строки, № нач. символа в строке)– вставка;

3. Length (имя строки)– функция типа Integer, вычисляет длину строки;

4. Pos (имя подстроки, имя строки)- функция типа Integer, отыскивает в строке первое вхождение подстроки и дает № позиции, с которой она начинается; если подстрока не найдена, значение функции будет = 0;

5. Str (число Real или Integer <: общая ширина поля<: кол-во симв. в дроб. части>>, имя строки) – процедура, преобразующая число типа Real или Integer в строку символов так, как это делает процедура Writeln перед вызовом; параметры, если они присутствуют, задают формат преобразования;

6. Val (имя строки, число Real или Integer, параметр) – процедура, преобразующая строку символов во внутреннее представление целое или вещественное числа; параметр = 0, если преобразование проведено успешно, в противном случае он содержит № позиции в строке, где обнаружен ошибочный символ;

7. Upcase (символ) – функция типа Char, возвращает символ в верхнем регистре, если он определен для него, либо сам символ, если для него нет верхнего регистра.

Пример: Upcase(‘a’) даст A,

Upcase(‘2’) даст 2.

Пример:

Var

x: Real;

y: Integer;

st, st1: String;

• - - - - - - - - - - - - - - - -

st:= concat (‘12’,’345’); (*получится st  12345*)

st1:= copy (st, 3, lenght(st)-2); (*получится st1  345*)

insert(‘-’,st1,2); (*получится st1  3-45*)

delete(st, pos(‘2’,st),3); (*получится st  15*)

str(pi:6:2,st); (*получится st  3.14*)

st1:=’3.1415’; (*получится st1  3.1415*)

val(st1,x,y); (*получится y=2, x – какой был*)

Операции отношения

= <> > < >= <=

выполняются над двумя строками посимвольно, слева направо, с учетом внутренней кодировки символов. Если одна строка меньше другой по длине, недостающие символы короткой строки заменяются значением chr(0).

Пример: Операции дают значение true:

‘turbo’<’turbo-pascal’;

‘A’<>’IFF’;

‘ПАскаль’<’Паскаль’;

6. МНОЖЕСТВЕННЫЕ ТИПЫ

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

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

Множества могут состоять из любого числа объектов (элементов), но могут и не содержать элементов.

В математике под множеством понимается некоторый набор элементов. Например, множество плоских геометрических фигур:

[круг, ромб, квадрат, треугольник, прямоугольник].

Все элементы одного множества различны и неупорядочены. Элементы множества не могут повторяться.

Пример. [круг, ромб, круг] – неверная запись множества.

[круг, ромб, квадрат]=[ромб, круг, квадрат] – одинаковы и равны между собой.