 |
Метод простых обменов (Пузырьковая сортировка)
|
|
|
|
Виды массивов
Одномерные массивы
Каждому используемому в программе конкретному массиву должно быть дано свое имя. Это имя будем называть полной переменной, поскольку ее значение есть весь массив. Каждая компонента массива может быть явно обозначена путем указания имени массива, за которым следует селектор компоненты — взятый в квадратные скобки индекс, задающий правило вычисления номера нужной компоненты. Это отличие от привычной записи индекса в математике, когда он указывается справа в нижней позиции, объясняется необходимостью использования линейной записи программы, так что многоуровневая запись должна быть исключена. При ссылке на компоненты массива индекс записывается на одном уровне с именем и заключается в квадратные скобки. Таким образом, для ссылки на отдельные компоненты используется запись вида (имя массива) [<индекс>] которую будем называть частичной переменной (поскольку ее значением является не весь массив, а отдельная его компонента, номер которой задается индексом) — применительно к массивам она называется переменной с индексом. В нашем примере массив получит имя v, а ссылки на отдельные его компоненты производятся с помощью частичных переменных v[ 1], v[2],..., v[1ОО]. В общем случае в качестве индекса может, быть использовано выражение, значение которого и определяет номер компоненты массива. При этом важно, что в индексное выражение могут входить переменные, так что при изменении их значений меняется и значение индекса, которое определяет номер компоненты массива. Таким образом, одна и та же переменная с индексом в процессе выполнения программы может обозначать различные компоненты массива. Тип значения индексного выражения называют типом индекса. Множество значений типа индекса должно быть перенумерованным множеством, тем самым определяя количество компонент и их упорядоченность. При задании регулярного типа кроме типа индекса необходимо задать тип компонент. Задание такого регулярного типа, как одномерный массив, т.е. вектор, имеет вид:
|
|
|
аrrау [(тип индекса)] оf <тип компонент>,где <тип компонент> — имя или задание типа.
Примеры задач
Задача 1. Дан линейный массив целых чисел. Подсчитать, сколько в нем различных чисел.
{Подсчет количества различных чисел в линейном массиве}.
ИДЕЯ РЕШЕНИЯ: заводим вспомогательный массив, элементами
которого являются логические величины (False - если элемент
уже встречался ранее, True - иначе)}
Program Razlichnye_Elementy;
Var I, N, K, Kol: Integer;
A: Array [1..50] Of Integer;
Lo: Array [1..50] Of Boolean;
Begin
Write('Введите количество элементов массива: '); ReadLn(N);
FOR I:= 1 TO N DO
Begin
Write('A[', I, ']='); ReadLn (A[I]);
Lo[I]:= True; {Заполняем вспомогательный массив значениями True}
End;
Kol:= 0; {переменная, в которой будет храниться количество различных чисел}
FOR I:= 1 TO N DO
IF Lo[I] THEN
Begin
Kol:= Kol + 1;
FOR K:= I TO N DO
{Во вспомогательный массив заносим значение False,
если число уже встречалось ранее или совпадает с текущим элементом A[I]}
Lo[K]:= (A[K] <> A[I]) And Lo[K];
End;
WriteLn('Количество различных чисел: ', Kol)
END.
Тест: N = 10; элементы массива - 1, 2, 2, 2, -1, 1, 0, 34, 3, 3. Ответ: 6.
Задача 2. Дан линейный массив. Упорядочить его элементы в порядке возрастания.
{Сортировка массива выбором (в порядке возрастания)}.
Идея решения: пусть часть массива (по K-й элемент включительно)
отсортирована. Нужно найти в неотсортированной части массива
минимальный элемент и поменять местами с (K+1)-м}
Program Sortirovka;
Var N, I, J, K, Pr: Integer; A: Array [1..30] Of Integer;
Begin
Write('Введите количество элементов: '); ReadLn(N);
For I:= 1 To N Do
Begin
Write('Введите A[', I, '] '); Readln(A[I]);
End;
WriteLn;
|
|
|
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;
Pr:= A[I]; A[I]:= A[K]; A[K]:= Pr;
End;
For I:= 1 To N Do Write(A[I], ' ');
End.
Тест: N = 10; элементы массива - 1, 2, 2, 2, -1, 1, 0, 34, 3, 3.
Ответ: -1, -1, 0, 1, 2, 2, 2, 3, 3, 34.
Двумерные массивы
Двумерный массив (прямоугольная таблица (матрица, набор векторов)) - это пример массива, в котором элементы нумеруются двумя индексами.
В качестве номера (индекса) элемента массива используется выражение порядкового типа (чаще integer).
Двумерным массивом называется таблица, состоящая из строк и столбцов. Для описания массива используются два индекса.
А11 А12 А13 … А1m
A21 A22 A23... А2m
...............
...............
...............
An1 An2 An3... Anm
Описание массива
Способ 1. В разделе описания переменных
var
ИмяМассива: array [Верх.Гр.1..Ниж.Гр.1,Верх.Гр.2..Ниж.Гр.2] of ТипЭлементов;
Способ 2. В разделе описания типов
ИмяМассива: array [Верх.Гр.1..Ниж.Гр.1,Верх.Гр.2..Ниж.Гр.2] of ТипЭлементов;
Способ 3. В разделе описания констант
const
ИмяМассива: array[1..3,1..3] of real=((1.2,2.4,0.4),(0.045,-0.47,0.003),(1.24,1,-7.4));
Заполнение массива данными (ввод элементов)
Массив, описанный как типизированная константа, уже содержит данные. Массивы, объявленные в разделе описания переменных, необходимо заполнить данными, прежде чем выполнять с ними какие-либо действия.
Значения элементов массива также можно задать следующими способами: при вводе данных с клавиатуры:
write('Введите количество строк и столбцов');
readln(n,m);
for i:=1 to n do
for j:=1 to m do
begin
write('a[',i,',',j,']='); {Можно эту строчку в программе не использовать}
readln(a[i,j]);
end;
с помощью датчика случайных чисел:
randomize;
writeln('Введите количество элементов массива');
readln(n);
for i:=1 to n do
begin
a[i]:=random(50);
writeln('a[',i,',',j,']=',a[i,j]);
end;
присваением заданных значений (например по формуле i*i/i+2):
writeln('Введите количество элементов массива');
readln(n);
for i:=1 to n do
begin
a[i]:=i*i/i+2;
writeln('a[',i,',',j,']=',a[i,j]);
end;
Вывод массива
вывод в столбец:
for i:=1 to n do
writeln(a[i,j]);
по строкам и столбцам:
for i:=1 to n do
begin
for j:=1 to m do
begin
write(a[i,j]:3);
end;
readln;
end;
Обработка массивов
Часто требуется вычислить сумму элементов массива, их среднее арифметическое значение или найти значения и номера максимального и минимального элементов, а также изменить значения элементов массива и т.д. Особенность работы с двумерными массивами заключается в том, что расширяется возможность обработки массива (появились новые элементы: строки, столбцы - являющиеся одномерными массивами). Подробно все действия можно рассмотреть в задачах разобранных в этом разделе.
|
|
|
Квадратная матрица
Квадратной называется такая матрица, в которой количество строк равно количеству столбцов. Выделяют следующие элементы квадратной матрицы:
главная диагональ;
побочная диагональ;
элементы, расположенные выше главной диагонали;
элементы, расположенные ниже главной диагонали;
элементы, расположенные выше побочной диагонали;
элементы, расположенные ниже побочной диагонали;
Главная диагональ. Если значения индексов (i, j) элемента равны, то элементы расположены на главной диагонали.
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
if i=j then <инструкции>
Побочная диагональ. Если для значений индексов (i, j) элементов выполняется равенство: i+j=n+1, то элементы расположены на побочной диагонали.
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
if i+j=n+1 then <инструкции>
Для элементов, расположенных выше главной диагонали необходимо использовать один из следующих фрагментов программы:
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
for i:=1 to n do
for j:=1 to n do
if i < j then <инструкции>
for i:=1 to n-1 do
for j:=i+1 to n do
<инструкции>
Если элементы расположены на главной диагонали и выше её необходимо использовать следующий фрагмент программы:
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
for i:=1 to n do
for j:=1 to n do
if i<=j then <инструкции>
Для элементов, расположенных ниже главной диагонали необходимо использовать следующий фрагмент программы:
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
for i:=1 to n do
for j:=1 to n do
if i>j then <инструкции>
Для элементов, расположенных ниже главной диагонали и не ней необходимо использовать следующий фрагмент программы:
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
for i:=1 to n do
for j:=1 to n do
if i>=j then <инструкции>
|
|
|
Если элементы, расположены выше побочной диагонали, то необходимо использовать следующий фрагмент программы:
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
for i:=1 to n-1 do
for j:=1 to n-1 do
if i+j<=n then <инструкции>
Если элементы, расположены ниже побочной диагонали, то необходимо использовать следующий фрагмент программы:
А11 А12 А13 А14
A21 A22 A23 А24
A31 A32 A33 А34
A41 A42 A43 А44
for i:=2 to n do
for j:=2 to n-1 do
if i+j>n+1 then <инструкции>
Транспонирование матрицы.
Транспонированной матрицей называется матрица, у которой столбцы соответствуют строкам исходной квадратной матрицы. При этом элементы главной диагонали исходной и транспонированной матриц, одни и те же.
Операция транспонирования сводится к обмену элементов матрицы, расположенных симметрично главной диагонали.
Исходная матрица
Транспонированная матрица
1
5
9
13
1
2
3
4
Фрагмент программы транспонирования матрицы:
for i:=1 to n do {Просмотр всех строк матрицы}
for j:=i+1 to n do {Просмотр всех элементов в строке, расположенных выше главной диагонали}
begin
k:=a[i,j];
a[i,j]:= a[j,i];
a[j,i]:= k;
end;
1.4 Примеры задач
1. Найти сумму всех элементов некоторого двумерного массива и сравнить их с произведением элементов некоторой строки.
program zadacha_1;
uses crt;
var
a: array[1..50,1..50] of integer; {массив}
i,j: integer; {переменные счетчики}
n,m: integer; {количество строк и столбцов массива}
s: integer; {сумма элементов массива}
p: integer; {произведение элементов некоторой строки}
q: integer; {некоторая строка}
begin
clrscr;
write('Введите количество строк: ');
readln(n);
write('Введите количество столбцов: ');
readln(m);
for i:=1 to n do
for j:=1 to m do
begin
write('a[',i,',',j,']=');
readln(a[i,j]);
end;
writeln('Матрица:');
for i:=1 to n do
begin
for j:=1 to m do
begin
write(a[i,j]:3);
end;
readln;
end;
for i:=1 to n do
for j:=1 to m do
begin
s:=s+a[i,j];
end;
write('Введите номер строки для работы: ');
readln(q);
p:=1;
for j:=1 to m do
begin
p:=p*a[q,j];
end;
writeln('Сумма элементов матрицы: ',s);
writeln('Произведение элементов строки ',q,' равна ',p);
if s>p then
begin
writeln('Сумма больше произведения');
end
else
begin
writeln('Произведение больше произведения');
end;
readln;
end.
2.Поменять второй столбец матрицы с предпоследним.
program zadacha_2;
uses crt;
var
a: array [1..50,1..50] of integer;
b: array [1..50,1..50] of integer;
m,n,i,j: integer;
begin
clrscr;
writeln('Количество строк');
readln(n);
writeln('Количество столбцов');
readln(m);
for i:= 1 to n do
for j:= 1 to m do
begin
write ('a[',i,',',j,']=');
readln (a[i,j]);
end;
writeln('Исходная матрица:');
for i:=1 to n do begin
for j:=1 to m do
write (a[i,j]);
writeln;
end;
for i:=1 to n do begin
for j:=1 to m do
b[i,j]:=a[i,j];
end;
for i:=1 to n do begin
a[i,2]:=b[i,m-1];
end;
for i:=1 to n do begin
a[i,m-1]:=b[i,2];
end;
writeln('Полученная матрица:');
for i:=1 to n do begin
for j:=1 to m do
write (a[i,j]);
writeln;
end;
readln;
end.
3.Дана матрица размерности m*n. Расположить элементы последнего столбца по убыванию.
|
|
|
program zadacha_3;
uses crt;
var
a:array [1..50] of integer;
b:array [1..50] of integer;
k,i,m,j,n,r,l:integer;
begin
clrscr;
write('Введите количество строк');
readln(n);
write('Введите количество столбцов');
readln(m);
for i:=1 to n do
for j:=1 to m do
begin
write('a[',i,']={b[',j,']=}');
readln(a[i]);
end;
for i:=1 to n-1 do
for k:=i+1 to n do
{for j:=1 to m do}
if a[k]>a[i] then
begin
r:=a[i];
a[i]:=a[k];
a[k]:=r;
end;
writeln('Отсортированый массив:');
for i:=1 to n do
writeln(a[i]:4);
readln;
end.
4. Дана квадратная матрица. Транспонировать её. Посчитать сумму всех нечётных элементов транспонированной матрицы.
program zadacha_4;
uses crt;
var
a:array [1..5,1..5] of integer;
S,i,j,n,c:integer;
begin
clrscr;
write ('введите кол-во строк и столбцов ');
readln (n);
for i:=1 to n do
for j:=1 to n do
begin
write ('a[',i,',',j,']=');
readln (a[i,j]);
end;
for i:=1 to n do
for j:=i+1 to n do
begin
c:=a[i,j];
a[i,j]:=a[j,i];
a[j,i]:=c;
end;
S:=0;
for j:=1 to n do
for i:=1 to n do
begin
if a[j,i] mod 2 <>0 then
begin
S:=S+a[j,i];
end;
end;
writeln ('S=',S);
readln;
end.
5. Дан двумерный массив. Посчитать сумму его двух столбцов, вывести большую сумму.
program zadacha_5
uses crt;
var
a:array[1..3,1..3] of integer;
i,j,m,n,s,s1,p,p1,max,p3:integer;
begin
clrscr;
write('введите количество строк');
readln(n);
write('введите количество столбцов');
readln(m);
for i:=1 to n do
for j:=1 to m do
begin
write('a[',i,',',j,']=');
readln(a[i,j]);
end;
begin
write('введите номер столбца');
readln(p);
for i:=1 to n do
for j:=1 to m do
if j=p then s:=s+a[i,p];
write('s=',s);
readln;
end;
s1:=0;
begin
write('введите номер другого столбца');
readln(p1);
for i:=1 to n do
for j:=1 to m do
if j=p1 then s1:=s1+a[i,p1];
write ('s1=', s1);
readln;
end;
begin
max:=s;
if s < s1 then
begin
max:=s1;
write('максимальная сумма',max);
readln;
write('вывести на экран номер столбца большей суммы', p3);
readln(p3);
end;
end;
end.
end.
6. Заполнить матрицу по образцу:
0
0
0
0
program zadacha_6;
uses crt;
var
a:array [1..50,1..50] of integer;
n:integer;
i,j,k:integer;
begin
clrscr;
write ('Введите количество строк и столбцов в матрице');
readln (n);
k:=0;
for i:=1 to n do
for j:=1 to n do
if i=j then
begin
a[i,j]:=k;
k:=k+1;
end
else
begin
a[i,j]:=0;
end;
for i:=1 to n do
for j:=1 to n do
begin
writeln('a[',i,',',j,']=',a[i,j]);
readln;
end;
readln; end.
7. Дана квадратная матрица порядка N. В матрице вычислить среднее арифметическое положительных элементов, стоящих на главной диагонали
program zadacha_7;
uses crt;
Var
a:array[1..50,1..50] of integer;{массив}
i,j:integer;
s,n,k:integer;
sr:real;
begin
clrscr;
write('введите кол-во строк');
readln(n);
write('введите кол-во столбцов');
readln(n);
write ('введите кол-во чисел');
readln(k);
for i:=1 to n do
for j:=1 to n do
begin
write('a[',i,',',j,']=');
readln(a[i,j]);
end;
s:=0;
begin
for i:=1 to n do
for j:=1 to n do
if a[i,j] > 0 then
s:=s+a[i,j];
sr:=s/n;
end;
write('sr=',sr);
readln;
end.
8. Найти сумму всех элементов квадратной матрицы, расположенных по главной диагонали и выше ее.
program zadacha_8;
uses crt;
var
a: array [1..30,1..30] of integer;
i,j,s,n: integer;
begin
clrscr;
writeln ('введите количество строк и столбцов: ');
readln (n);
for i:=1 to n do
for j:=1 to n do
begin
write('a[',i,',',j,']=');
readln (a[i,j]);
end;
for i:=1 to n do
for j:=i+1 to n do
begin
if j>=i then
begin
s:=s+a[i,j];
end;
end;
writeln('s=',s);
readln;
end.
9. Дана вещественная матрица размерности n*m. Удалить k столбец матрицы.
program zadacha_9;
uses crt;
var
a: array [1..100,1..100] of real;
b: array [1..100,1..100] of real;
i,j: integer; {переменные счётчики}
n,m: integer; {количество строк и столбцов в массиве}
k: integer; {№ строки которую необходимо удалить}
begin
clrscr;
write ('Введите количество строк в массиве');
readln (n);
write ('введите количество столбцов в массиве');
readln (m);
write ('Введите № строки которую надо удалить');
readln (k);
randomize; {ввод массива случайных чисел}
for i:=1 to n do
for j:=1 to m do
begin
a[i,j]:=random(100);
end;
for i:=1 to n do
for j:=1 to m do
begin
writeln ('a[',i,',',j,']=',a[i,j]);
end;
writeln ('Новый массив');
for i:=1 to n do
for j:=1 to m do
begin
if j<>k then
{Проверка условия № столбца
неравен № столбца,
который необходимоудалить}
begin
b[i,j]:=a[i,j];
{если да, то новому массиву
присваиваем проверяемый элемент }
end;
end;
for i:=1 to n do {вывод нового массива}
for j:=1 to m do
writeln ('b[',i,',',j,']=',b[i,j]);
readln;
end.
10. Дана вещественная матрица размерности n*m. Вывести номера столбцов, содержащих только отрицательные элементы.
program zadacha_10;
uses crt;
var
a: array[1..50,1..50] of real;
i,j: integer;
n,m: integer;
begin
clrscr;
write('введите кол-во строк ');
readln(n);
write('введите кол-во столбцов ');
readln(m);
for i:=1 to n do
for j:=1 to m do
begin
write('a[',i,',',j,']= ');
readln(a[i,j]);
end;
for j:=1 to m do
begin
if a[i,j]<0 then
begin
writeln ('номер столбца, в котором все элементы отрицательные= ', J);
readln;
end
else
begin
writeln ('в столбце ',J,' нет отрицательных или не
все отрицательные элементы ');
end;
end;
readln;
end.
11. В двумерном массиве найти минимальное число и определить в какой строке и каком столбце он находится.
program zadacha_11;
uses crt;
var
a:array [1..50,1..50] of integer; {описание масива}
i,j:integer; {переменные-счетчики}
min: real; { минимальное число}
n,m: integer; { кол-во строк, кол-во столбцов}
begin {начало программы}
clrscr;
write('введите кол-во строк '); {ввод кол-ва строк}
readln(n);
write('введите кол-во столбцов '); {ввод кол-ва столбцов}
readln(m);
for i:=1 to n do
for j:=1 to m do
begin
write('a[',i,',',j,']= '); { ввод элементов массива }
readln(a[i,j]);
end;
min:=a[1,1];
for i:=1 to n do
for j:=1 to m do
begin
if a[i,j] < min then {поиск минимального числа}
min:=a[i,j];
end;
for i:=1 to n do
for j:=1 to m do
begin
if a[i,j]=min then
begin
writeln('минимальное число = ',min:5);
{вывод минимального числа}
writeln('номер элемента i=',i,',','j=',j);
{вывод номера мин. чис-ла}
end;
end;
readln;
end.
12. Развернуть квадратную матрицу на 90 градусов по часовой стрелке.
program zadacha_12;
uses crt;
var
a: array [1..30,1..30] of integer; {исходная матрица}
b: array [1..30,1..30] of integer; {промежуточная матрица}
c: array [1..30,1..30] of integer; {Матрица развёрнута на 90?}
i,j: integer; {переменные счётчики}
m,n: integer; {количество строк и столбцов}
begin
clrscr;
write ('введите количество строк и столбцов ');
readln (n);
for i:=1 to n do {ввод элементов массива}
for j:=1 to n do
begin
write ('a[',i,',',j,']=');
readln (a[i,j]);
end;
for i:=1 to n do
for j:=1 to n do
begin
b[i,j]:=a[n+1-i,j]; {промежуточной матрицы присваиваем
элементы первоначальной матрицы по закону: первому элементу
присваиваем строки последний, последнему первый, второму
элементу предпоследний, предпоследнему второй и тд.}
end;
writeln ('Матрица развёрнута на 90?.');
for i:=1 to n do
for j:=1 to n do
begin
c[i,j]:=b[j,i]; {третьей матрице присваиваем
элементы промежуточной по закону: первая строка
становится первым столбцом и тд. }
writeln ('c[',i,',',j,']=',c[i,j]); {печать массива развёрнутого на 90?}
readln;
end;
end.
Сортировка массивов
Задача сортировки (упорядочения) элементов массива в соответствии с их значениями относится к классу классических задач, которые решались еще на первых е- mail –ах.
В настоящее время разработано достаточно много различных методов сортировки. Одни из них относятся к методам простых сортировок. Другие к улучшенным. Однако до сегодняшнего момента задача разработки метода, сочетал бы в себе все лучшие качества остается открытой. Договоримся, что линейный массив, который необходимо упорядочить уже задан, т.е. описан и сгенерирован.
Различают следующие типы сортировок:
1) по возрастанию
2) по убыванию
3) по не убыванию
4) по не возрастанию
При рассмотрении каждого метода будем сортировать элементы по неубыванию.
Метод простых обменов (Пузырьковая сортировка)
Идея метода: Весь массив рассматривается несколько раз, причем при каждом рассмотрении сравниваются значения 2-х соседних элементов. Если они стоят в неправильном порядке, то производится их перестановка. Так происходит до тех пор, пока не будет выполнено ни одной перестановки. Метод называют пузырьковой сортировкой потому что меньшие значения элементов постепенно "всплывают", как пузырики воздуха в воде, перемещаясь в начало массива, а "тяжелые" элементы "оседают на дно".
7 0 -4 3 1 -2 5
-4 7 0 -2 3 1 5
-4 -2 7 0 1 3 5
-4 -2 0 7 1 3 5
-4 -2 0 1 7 3 5
-4 -2 0 1 3 7 5
-4 -2 0 1 3 5 5
Фрагмент:
For i:=2 to n do
For j:=n downto i do
if v[j] <v[j-1] then
begin
x:=v[j];
v[j]:=v[j-1];
v[j-1]:=x;
end;
|
|
|
12 |
