Сортировка обменом (пузырьковая Сортировка)

Принцип метода:

Слева направо поочередно сравнивается два соседних элемента, и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.

После одного такого прохода на последней n -ой позиции массива будет стоять максимальный элемент («всплыл» первый «пузырек»). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1 -го элемента. И так далее. Всего требуется n-1 проход.

Программа, реализующая метод обмена («пузырька»), будет иметь следующий вид:

Program BubbleSort;

uses Ctr;

const

n= 20; { длина массива }

type

TVector = array [1…n] of Real;

var

Vector: TVector;

B: Real;

i, k: Integer;

begin

ClrScr;

Writeln('Введите элементы массива:');

for i:=1 to n do

Read (Vector[i]);

Readln;

{_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ }

for k:= n downto 2 do

{«Всплывание» очередного максимального элемента на k-ю позицию}

for i:= 1 to k-1 do

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

begin

B: =Vector[i];

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

Vector[i+1]:= B

end;

{_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _}

Writeln('Отсортированный массив:');

for i:=1 to n do

Write (Vector [i]: 8: 2);

Writeln;

End.

Задачи

1. Заполнить одномерный массив из n – элементов целых чисел. Упорядочить его:

а) по возрастанию;

б) по убыванию.

2. Заполнить одномерный массив из n – элементов целых чисел. Упорядочить первую половину элементов по возрастанию, вторую по убыванию.

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

4. Заполнить строку из символов русского алфавита. Упорядочить символы по алфавиту, сначала заглавные, затем строчные символы. Символы, не являющиеся буквами исключить.

5. Заполнить строку из символов русского алфавита. Упорядочить слова, образующие строку, по алфавиту. Лишние пробелы и знаки препинания исключить.

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

МНОГОМЕРНЫЕ МАССИВЫ

Массивы могут иметь и более одного измерения. В таких случаях говорят о многомерных массивах. Многомерные массивы широко используются в математике, статистике и некоторых других прикладных науках (например, для матричных вычислений). Объявление двумерного массива выглядит следующим образом:

Var

TwoDimensionalArray: Array [1..80, 1..25] of Char;

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

Поскольку элементы массивов расположены упорядоченно в соответствии с их номерами-индексами, необходимо внимательно относиться к изменению индексов. Обработка таких одномерных массивов ведется, как правило, с использованием вложенных циклов For…to…do.

Пример:

Применение некоторого двумерного массива.

Переменные Line и Column определяют номера строк и столбцов на экране.

Program DemoUsesTwoDimensionalArray;

Uses Crt;

Var

TwoDimensionalArray: Array[18..0, 1..25] of char;

Column, Line: integer;

Begin

ClrScr;

for Line:= 1 to 25 do

for Column: = 1 to 80 do

TwoDimensionalArray[Column, Line]:= Chr(32+Column);

{Вывод элементов массива. Номер столбца изменяется чаще}

{номера строки}

ClrScr;

for Line:= 1 to 25 do

begin

for Column: = 1 to 80 do

Write(TwoDimensionalArray[Column, Line]);

Writeln;

end;

End.

Пример:

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

Program VertMirrow;

Const

m = 10; {число строк}

n = 15; {число столбцов}

type

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

Var

Matr: TMatr;

B: Integer;

i, j: integer;

Begin

Clrscr;

for i: =1 to m do {Ввод исходных значений матрицы}

for j: =1 to n do

readln(Matr[i, j]);

writeln ('Исходная матрица');

for i: =1 to m do

begin

for j: =1 to n do write (Matr [i, j]: 5);

writeln;

end;

writeln;

{Зеркальное отображение матрицы относительно вертикальной}

{оси симметрии}

for j: =1 to n div 2 do (Берем столбцы от первого до среднего)

for i: =1 to m do (Меняем местами симметричные столбцы)

begin

B:= Matr[i, j];

Matr[i,j]:= Matr [i, n-j+1];

Matr[i, n-j+1]:= B;

end;

Writeln('Преобразованная матрица:');

for i: =1 to m do

begin

for j: =1 to n do write (Matr [i, j]: 5);

writeln;

end;

writeln;

End.

Пример:

Программа, осуществляющей вывод элементов квадратной матицы порядка n и вывод, выполняя обход матрицы по «спирали», как показано на рисунке.

	i   p p+1 n–p n–p+1		j p n–p+1	p p+1   n–p+1
1 2 3 4 5 6
p n–p n–p+1

P –номер текущего витка «Спирали»

Программа, соответствующая данной схеме, имеет вид:

Program SpiralWrite;

Uses Crt;

const

n =10; {порядок квадратной матрицы}

type

TMatr = array[1…n, 1…n]of integer;

Var

Matr: TMatr; {исходная матрица}

i, j, p: integer;

Begin

ClrScr;

for i: =1 to n do

begin

for j: = 1 to n do read(Matr [i,j]);

end

writeln ('Исходная матрица:');

for i: = 1 to n do

begin

for j: = 1 to n do

write(Matr [i,j]:5);

writeln;

end;

writeln;

{Выписывание элементов матрицы по «спирали»}

for p: = 1 to (n+1) div 2 do

begin

{Выписывание элементов верхней строки p–го витка}

for j: =p to n-p+1 do

write(Matr[p, j]:4);

{Выписывание элементов правого столбца p–го витка}

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

write(Matr[i,n-p+1]:4);

{Выписывание элементов нижней строки p–го витка}

for j: =n-p downto p do

write(Matr[n-p+1,j]:4);

{Выписывание элементов левого столбца p–го витка}

for i: =n-p downto p+1 do

write(Matr[i,p]:4);

end;

End.

В Турбо Паскаль можно одним оператором присвоения передать все элементы одного массива другому массиву того же типа, например:

Var

a,b: array [1…5]of integer;

begin

....

a: =b

....

end.

После этого присваивания все пять элементов массива a получат те же значения, что и в массиве b. Однако над массивами не определены операции отношения. Нельзя, например, записать:

if a =b then…

Сравнить два массива можно поэлементно, например:

Var

a,b: array [1…5] of singl;

eq: Boolean;

i: byte;

Begin

....

eq: = true;

for i: = 1 to 5 do

if a[1]< > b[j] then

eq: =fals;

if eq= false then

....

End.

Задачи

1. Заполнить два массива размера n´n, все элементы которого целые числа. Вычислить сумму двух массивов.

2. Заполнить массив размера n´n, все элементы которого целые числа, затем ввести число. Вычислить произведение матрицы на число.

3. Заполнить массив размера n´n, все элементы которого целые числа. Преобразовать массив, заменив строки столбцами.

4. Заполнить массив размера n´n, все элементы которого целые числа. Преобразовать его:

а) расставив строки в порядке возрастания первого элемента каждой строки;

б) расставив строки в порядке убывания первого элемента каждой строки;

в) расставить столбцы в порядке возрастания первого элемента каждого столбца;

г) расставить столбцы в порядке убывания последнего элемента каждого столбца.

5. Усложнить предыдущую задачу условием: в случае равенства первых элементов провести расстановку по вторым элементам, затем в случае равенства вторых – по третьим и т.д.

6. Заполнить массив размера n´n, все элементы которого целые числа. Вывести на экран:

а) строки, первые элементы которых – четные числа;

б) строки, первые элементы которых – положительные числа;

в) строки, сумма элементов которых – четное число;

г) столбцы, первые элементы которых – положительные числа;

д) столбцы, первые элементы которых – четные числа;

е) те строки, где элемент главной диагонали массива – четное число.

7. Заполнить массив размера n´n, все элементы которого натуральные числа. Подсчитать число комбинаций символов 'н', 'о'. Комбинации 'но', 'он', , входят в это число.

8. Заполнить случайным образом массив n´n, все элементы которого целые числа. Вывести на экран максимальные элементы строк.

9. Заполнить случайным образом массив размера n´n, все элементы которого целые числа. Получить новый массив, переставляя его блоки в соответствии с рисунком:

а) б)

10. Заполнить случайным образом массив размера n´n. Определить максимальный элемент в заштрихованной области.

ЗАПИСИ

Рассмотрим еще один структурированный тип данных, так называемые записи (Record), позволяющие хранить вместе переменные, имеющие различные типы данных:

Структура объявления типа записи такова:

<имя типа> = RECORD <список полей> End;

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

type

Birthday = record

day, month: byte;

year: integer;

end;

var

a,b: Birthday;

…

В этом примере тип Birthday (день рождения) есть запись с полями day, month и year (день, месяц и год); переменные А и В содержат записи типа Birthday.

Как и в массиве, значения переменных типа записи можно присваивать переменным того же типа, например:

a: =b;

К каждому из компонентов записи можно получить доступ, если использовать составное имя, т.е. указать имя переменной, затем точку и имя поля:

a.day: =27

b.year: =1939;

Для вложенных полей приходится продолжать уточнения:

type

Birthday = record

day, month: byte;

year: integer;

end;

var

c: record

name: string;

bd: Birthday;

end;

begin

....

if c.bd.year =1939 then…

end.

Чтобы упростить доступ к полям записи, используется оператор присоединения with:

With <переменная> do <оператор>

Здесь With, do – ключевые слова (с, делать);

<переменная> – имя переменной типа запись, за которым, возможно, следует список вложенных полей;

<оператор> – любой оператор Турбо Паскаль.

Например:

With c.bd do month: =9;

это эквивалентно:

With c do With bd do month: =9;

Турбо Паскаль разрешает использовать записи с так называемыми вариативными полями, например:

Type

Forma =record

Name: string;

case byte of

0: (Birth Place: string [40]);

1: (Country: string [20];

Entri Port: string [20];

Entry Pate: 1…31;

Exite Pate: 1…31)

End;

В этом примере тип FORMA определяет запись с одним фиксированным полем Name и вариативной частью, которая задается предложением case of. Вариативная часть состоит из нескольких вариантов (в примере для двух вариантов: 0 и 1). Каждый вариант определяется константой выбора, за которой следует двоеточие и список полей, заключенный в круглые скобки. В любой записи может быть только одна вариативная часть, и, если она есть, то должна располагаться за всеми фиксированными полями.

Отличительной особенностью вариативной части является то обстоятельство, что все заданные в ней варианты «накладываются» друг на друга, т.е. каждому из них выделяется одна и та же область памяти. Это открывает дополнительные возможности преобразования типов, например:

Var

met 4: record

case byte of

0: (by: array [0…3]of byte);

1: (wo: array [0…1]of word);

2: (lo: longint);

end;

В этом примере запись met 4 имеет три варианта, каждый из которых занимает в памяти один и тот же участок в 4 байт. В зависимости от того, к какому полю мы обращаемся в программе, этот участок может рассматриваться как массив из 4 байт (поле by) массив из двух целых типа Word или, наконец, как одно целое число типа Longint. Например, этой записи можно сначала присвоить значение как длинному целому, а затем проанализировать результат по байтам или словам.

Var

x: word;

xb: byte;

xl: LongInt;

Begin

....

with m do

begin

lo:= trunc(2*pi*x);

if wo[1]=0 then

if wo[1] =0 then

xb: =x[0]

else

x:= wo[0]

else

x1: =lo

end;

....

End.

Предложение CASE…OF, открывающее вариативную часть, внешне похоже на соответствующий оператор выбора, но на самом деле играет лишь роль своеобразного служебного слова, обозначающего начало вариативной части. Именно поэтому в конце вариативной части не следует ставить END как пару к CASE…OF (Поскольку вариативная часть всегда последняя в записи, за ней все же стоит END, но лишь как пара к RECORD)

Ключ выбора в предложении CASE…OF фактически игнорируется компилятором: единственное требование, предъявляемое к нему Турбо Паскаль, состоит в том, чтобы ключ определял некоторый стандартный или предварительно объявленный порядковый тип. Причем сам этот тип никак не влияет ни на количество следующих ниже вариативных полей, ни даже констант выбора. В Турбо Паскаль можно в поле ключа выбора указывать переменную порядкового типа и даже присваивать ей в программе значение.

Это, однако, не влияет на выбор поля. Значения констант выбора в Турбо Паскаль могут быть производными, в том числе повторяющимися, например:

type

rec1= record

a: byte;

b: word;

end;

rec 2 =record

c: longint;

case x: byte of

1: (d: word);

2: (e: record case Boolean of

3: (f: rec 1);

3: (g: single);

'3': (c: word)

end)

end;

var

r: rec2;

begin

r.x:= 255;

if r.e.g =0 then

writeln('O.K.')

else

writeln (r.e.g.);

End.

В этом предложении case Boolean of в записи, определяемой в поле Е, объявляет ключом выбора логический тип, который, как известно, имеет лишь значения TRUE и FALSE. Константы же выбора следующих далее вариантов не только содержат совершенно не свойственные этому типу значения, но и две из них повторяющиеся, а общее количество вариантов три, а не два, как следовало бы ожидать.

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

МНОЖЕСТВА

Множества – это наборы однотипных логически связанных друг с другом объектов. Характер связей между объектами лишь подразумевается программистом и никак не контролируется Турбо Паскаль. Количество элементов, входящих в множество, может меняться в пределах от 0 до 255 (множество не содержащее элементов называется пустым).

Именно непостоянством количества своих элементов множества отличаются от массивов и записей.

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

Пример:

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

type

digitChar=set of '0'…'9';

digit=set of 0…9;

var

s1, s2, s3: digit Char;

s4, s5, s6: digit;

begin

....

S1: =['1', '2', '3'];

S2: =['3', '2', '1'];

S3: =['2', '3'];

S4: =[0…3, 6];

S5: =[4, 5];

S6: =[3…9];

....

end.

В этом примере множества S1 и S2 эквивалентны, а множество S3 включено в S2, но не эквивалентно ему.

Описание типа множества имеет вид:

<имя типа> = SET OF <баз.тип>

Здесь <имя типа> – правильный идентификатор;

SET OF –зарезервированные слова (множество, из);

<баз.тип> – базовый тип элементов множества, в качестве которого может использоваться любой тип, кроме Word, integer, longint.

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

Над множествами определены следующие операции:

* – пересечение множеств; результат содержит элементы, общие для обоих множеств, например:

S4*S6 содержит [3], S4*S5 –пустое множество;

+ – объединение множеств; результат содержит элементы первого множества; дополненные недостающими элементами из второго множества

S4+S5 содержит [0, 1, 2, 3, 4, 5, 6];

S4*S5 содержит [3, 4, 5, 6, 7, 8, 9];

- – разность множеств; результат содержит элементы из первого множества, которые не принадлежат второму:

S6-S5 содержит [3, 6, 7, 8, 9];

S4-S5 содержит [0, 1, 2, 3, 6];

= – проверка эквивалентности; возвращает TRUE, если оба множества эквивалентны;

< > – проверка неэквивалентности; возвращает TRUE, если оба множества неэквивалентны;

<= - проверка вхождения; возвращает TRUE, если первое множество включено во второе;

>= - проверка вхождения; возвращает TRUE, если второе множество включено в первое;

IN – проверка принадлежности. В этой операции первый элемент –выражение, а второй – множество одного и того же типа; возвращает TRUE, если выражение имеет значение, принадлежащее множеству:

3 in S6 возвращает TRUE;

2*2 in S1 возвращает FALSE.

Дополнительно к этим операциям можно использовать две процедуры

INCLUDE – включает новый элемент во множество

(Include(S,I), где S – множество, I – элемент);

EXCLUDE – исключает элемент из множества

(Exclude(S,I), где S – множество, I – элемент).

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

Пример:

Разработать программу выделения из первой сотни натуральных чисел всех простых чисел.

В основе программы лежит прием, известный под названием «решето Эратосфена». Суть программы состоит в следующем. Сначала формируется множество BEGINSET, состоящее из всех целых чисел в диапазоне от 2 до N. в множество PRIMERSET (оно будет содержать искомые простые числа) помещается 1. Затем циклически повторяются следующие действия.

- взять из BEGINSET первое входящее в него число NEXT и поместить его в PRIMERSET;

- удалить из BEGINSET число NEXT и все другие числа, кратные ему, т.е. 2*NEXT, 3*NEXT и т.д.

Цикл повторяется до тех пор, пока множество BEGINSET не станет пустым.

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

Program PrimerNumberDetect;

{Выделение всех простых чисел из первых N целых}

Const

N=255; {Количество элементов исходного множества}

Type

SetOfNumber =set of 1…N;

Var

N1, next, i: word;{Вспомогательные переменные}

BeginSet;{Исходное множество}

Primer Set: SetOfNumber;{Множество простых чисел}

Begin

BeginSet:= [2…N];{Создаем исходное множество}

Primer Set:= [1];{Первое простое число}

Next:= 2;{Следующее простое число}

While Begin Set < >[]do

begin

n1:=next; {n1-число, кратное очередному простому (next)}

{Цикл удаления из исходного множества непростых чисел}

while n1<=N do

begin

Exlude(beginSet, n1);

n1:=n1+next{Следующее кратное}

end;

Include(PrimerSet, next);

{Получаем следующее простое, которое есть первое не вычеркнутое из исходного множества}

repeat

inc(next)

until (next in BeginSet) or (next >N)

end; {Конец основного цикла}

{Выводим результат:}

for i:=1 to N do

if i in PrimerSet then Write (i:8);

writeln

End.

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

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

<идентификатор>: <тип> = <значение>

Здесь<идентификатор> – идентификатор константы,

<тип> – тип константы,

<значение> – значение константы.

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

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

Поскольку типизированная константа фактически не отличается от переменной, ее нельзя использовать в качестве значения при объявлении других констант или границ диапазона.