Лекции по Turbo Pascal (стр. 10 )

end;

for i:=1 to n-1 do begin

k:=i;

for j:=i+1 to n do

if a[j]<a[k] then k:=j;

c:=a[i];

a[i]:=a[k];

a[k]:=c;

end;

for i:=1 to n do

writeln (a[i]);

readln;

end.

Метод прямого обмена (метод пузырька).

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

program vosr;

uses crt;

var a: array [1..15] of integer;

i, j, k, n, m, c, f: integer;

begin

clrscr;

writeln (‘’); readln (n);

for i:=1 to n do begin

write (i,’:’); readln (a[i]);

end;

for i:=1 to n-1 do begin

for j:=1 to n-1 do

if a[j]>a[j+1] then begin

c:=a[j];

a[j]:=a[j+1];

a[j+1]:=c;

end;

end;

for i:=1 to n do

writeln (a[i]);

readln;

end.

program vosr;

uses crt;

var a: array [1..15] of integer;

i, j, k, n, m, c, f: integer;

begin

clrscr;

writeln (‘’); readln (n);

for i:=1 to n do begin

write (i,’:’); readln (a[i]);

end;

k:=n-1;

repeat

f:=0;

for i:=1 to k do

if a[i]>a[i+1] then begin

f:=1;

c:=a[i];

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

a[i+1]:=c;

end;

dec(k);

until f=0;

for i:=1 to n do

writeln (a[i]);

readln;

end.

6) Упорядочение массива

Упорядочение (сортировка) - это расположение значений элементов массива в порядке возрастания или убывания их значений.

Сортировка простым выбором.

Рассмотрим идею этого метода на примере. Пусть исходный массив А состоит из 10 элементов : 5 13 7 9 1 8 16 4 10 2.

После сортировки массив : 1 2 4 5 7 8 9 10 13 16

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

5 13 7 9 1 8 16 4 10 2   5 13 7 9 1 8 2 4 10 16

1 шаг Рассмотрим весь массив и найдем в нем максимальный элемент - 16. Поменяем его местами с последним элементом - с числом 2.

2 шаг. Рассмотрим часть массива, исключая последний элемент. Максимальный элемент этой части - 13, он стоит на втором месте. Поменяем его местами с последним элементом этой части - с числом 10.

И т. д.

Фрагмент программы :

for i:=n downto 2 do

begin {цикл по длине рассматриваемой части массива}

maxi:=i;

for j:=1 to i-1 do if a[j]>a[maxi] then maxi:=j;

if maxi<>i then begin {перестановка элементов}

k:=a[i]; a[i]:=a[maxi]; a[maxi]:=k

end;

end;

«Пузырьковый метод»

Массив просматривают слева направо. Каждый предыдущий элемент сравнивается с последующим. Если предыдущий элемент больше последующего, то предыдущий и последующий элементы меняются местами.

Program sort1;

const n=10;

label metka;

var a: array [1..n] of integer;

i, c, k : integer;

begin

for i:=1 to n do readln(a[i]);

metka: k=0; {счетчик перестанокок}

for i:=1 to n-1 do

if a[i]>a[i+1] then begin c:=a[i];

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

a[i+1]:=c;

k:=1;

end;

if k=1 then goto metka

else writeln(‘упорядочен‘);

for i:=1 to n do writeln(a[i]);

еnd.

Тоже самое, но с использованием вложенных циклов

Program sort2;

const n=10;

var a: array [1..n] of integer;

i, k, c : integer;

begin

for i:=1 to n do readln(a[i]);

for i:=1 to n-1 do

for k:=1 to n-i do

if a[k]>a[k+1] then begin c:=a[k];

a[k]:=a[k+1];

a[k+1]:=c;

end;

for i:=1 to n do writeln(a[i]);

еnd.

Двухмерные массивы.

Описание двумерного массива определяет имя, размер массива (количество строк и столбцов) и базо­вый тип. Формат описания в разделе переменных:

Var <имя маcсива > : array [<тип индекса1> , <тип индекса2>] of <базовый тип>;

Двумерный массив — массив, у которого положение каждого элемента характеризуется двумя числами, первое из них определяет номер строки, второе – номер столбца, на пересечении которых находится элемент. Он так же, как и одномерный массив, состоит из значений одного типа. В двумерных массивах хра­нятся значения прямоугольных таблиц. Примеры описания двумерных массивов:

Var С : array [1. .5, 1. .10] of real;

R1, R2: array [0. .10, 1. .365] of char;

Sim : array [1. .20, 1. .10] of string[20];

Const M=10; N=20;

Var X, S : array [1. .M, 1. .N] of byte;

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

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

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

2. Описание двумерного массива в языке паскаль записывается так:

<Имя_массива> : array[<n1>..<n2>,<k1>..<k2>] of [<тип>]

где строки таблицы имеют номера с n1 по n2, а столбцы - с k1 по k2. Запись <Имя_массива>[n, k] указывает на элемент, стоящий на пересечении n-й строки и k-го столбца. Например, описание

Tab : array[1..10,1..15] of Integer

задает таблицу из 10 строк и 15 столбцов (всего 10 х 15 = 150 элементов), состоящую из целых чисел. Tab[3,5] указывает на 5-й элемент в 3-й строке.

Турнирную таблицу для N участников удобно хранить в двумерном массиве N x N типа Real, т. к. результатом шахматной партии для каждого участника может быть победа (1 очко),

поражение (0 очков) или ничья (0.5 очка). Вот описание таблицы:

Tab : array[1..N,1..N] of Real.

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

writeln('Введите номера участников встречи');

readln(n1,n2);

writeln('Сколько очков у участника ',n1,' ?');

readln(Tab[n1,n2]);

Tab[n2,n1] := 1-Tab[n1,n2];

4. Эти действия нужно повторять столько раз, сколько встреч состоится в турнире. Если все запланированные встречи состоятся, то их количество можно сосчитать по формуле n(n-1) - подумайте, почему. Однако, может случиться, что по каким-то причинам часть встреч не состоится, а какие-то будут сыграны дважды. Поэтому удобнее как-то обозначить окончание ввода данных в программе, например, после каждой встречи выяснять, будут ли еще вводиться данные. Вот фрагмент программы, предназначенный для ввода результатов всех встреч турнира:

kon := 'Д';

while kon <> 'Н' do

begin

writeln('Введите номера участников встречи');

readln(n1,n2);

writeln('Сколько очков у участника ',n1,' ?');

readln(Tab[n1,n2]);

Tab[n2,n1] := 1-Tab[n1,n2];

writeln('Будут ли еще встречи? (Д/Н)');

readln(kon);

end;

5. По окончании турнира нужно вывести турнирную таблицу на экран:

for i := 1 to N do

begin

for k := 1 to N do

write(Tab[i, k]:3:1);

writeln;

end;

7.  Бывают задачи, в которых данные удобно хранить в виде трехмерного (и даже четырех - и более - мерного) массива. Например, результат встречи в футбольном турнире представляет собой не одно, а три числа - количество забитых и пропущенных мячей и количество очков (2 - победа, 0 - поражение, 1 - ничья). Такую таблицу удобно заносить в массив

Football : array[1..N,1..N,1..3] of Integer;

Элемент Football[3,5,2] содержит информацию о количестве мячей, пропущенных 3-й командой в матче с 5-й командой.

Поразмышляйте самостоятельно над процедурой ввода результатов футбольного турнира.

Работа с элементами

В математике часто используют многомерные массивы (двумерные, трехмерные и т. д.). Мы рассмотрим двумерные массивы, иначе называемые матрицами.

Например : 5 4 3 6

2 8 1 7

4 3 9 5

Данная матрица имеет размер 3 на 4, т. е. она состоит из трех строк и четырех столбцов. Если всю матрицу обозначить одним именем, например А, то каждый элемент матрицы будет иметь два индекса - А[i, j]

Здесь первый индекс i обозначает номер строки (i=1,2,3), второй индекс j - номер столбца (j=1,2,3,4).

Такую матрицу можно описать следующим образом :

1 способ :С использованием типа

Type T=array [1..3,1..4] of integer;

Var A: T;

2 способ :

Var A: array [1..3,1..4] of integer;

При решении задач с использованием двумерных массивов во всех случаях (кроме некоторых частных) организуются вложенный циклы.

Перемещение по строке :