Название: упорядочение элементов массива
ЦЕЛЬ РАБОТЫ:
1. Получение практических навыков в использовании оператора цикла.
2. Знакомство с алгоритмами упорядочения.
ПОСТАНОВКА ЗАДАЧИ:
Изучив алгоритмы упорядочения, выбрать один из них. Написать программу, которая работает с любым доступным набором данных. Входную информацию и результаты счета вывести на рабочий диск и на экран, снабдив их соответствующими заголовками.
СОДЕРЖАНИЕ ОТЧЕТА
1. Задание на лабораторную работу.
2. Блок-схему алгоритма и текст программы.
3. Результаты работы программы.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ:
Рассмотрим массив целых и действительных чисел A(1),...,A(N).
Пусть требуется переставить элементы этого массива так, чтобы после перестановки они были упорядочены по не убыванию (возрастанию).
A(1)<=A(2)<=A(3)<=...<=A(N).
Эта задача называется задачей сортировки или упорядочения массива (эту же задачу можно рассматривать применительно к упорядочению по не возрастанию (убыванию)):
A(1)>=A(2)>=A(3)>=...>=A(N)).
Для решения этой задачи можно воспользоваться, например, следующими алгоритмами:
а) Найти элемент массива, имеющий наименьшее значение, переставить его с первым элементом, затем проделать то же самое, начав со второго элемента и т.д. (сортировка выбором). При решении задачи используются два цикла. Во внутреннем цикле находится наименьший элемент и его порядковый номер. После окончания цикла первый элемент из рассматриваемой части массива записывается на место наименьшего, а наименьший - на место первого. Указанные действия повторяются во внешнем цикле, начиная сначала с первого элемента массива, затем со второго и т.д.
б) Последовательным просмотром чисел A(1),...,A(N) найти 'I' такое, что A(I)>A(I+1). Поменять местами A(I) и A(I+1), возобновить просмотр с элемента A(I+1) и т.д. Тем самым наибольшее число передвинется на последнее место. Следующие просмотры начинать опять сначала, пока в процессе просмотра массива не будет перестановок (сортировка обменом).
Пример программы упорядочения массива по не убыванию (возрастанию) методом выбора.
ПРОГРАММА:
program lab91; (* УПОРЯДОЧЕНИЕ МЕТОДОМ ВЫБОРА *)
var a:array[1..50] of integer;
i,j,n,amax,k:integer; f:text;
begin
assign(f,'lab91.dat');rewrite(f); writeln;
write('ВВЕДИТЕ КОЛ-ВО ЭЛЕМЕНТОВ МАССИВА n=');read(n);
writeln('ВВЕДИТЕ ',n,' ЭЛЕМЕНТОВ МАССИВА');
for i:= 1 to n do read(a[i]);
writeln(f,' ИСХОДНЫЙ МАССИВ ');
writeln(' ИСХОДНЫЙ МАССИВ ');
for i:=1 to n do
begin
write(f,' A[',i:2,']=',a[i]:3); write(' A[',i:2,']=',a[i]:3);
if i mod 5=0 then
begin (* ВЫВОД ПО 5 ЭЛ-ОВ В СТРОКЕ *)
writeln(f);writeln
end
end;
for i:=1 to n-1 do
begin
amax:=a[i];k:=i;
for j:=i to n do
begin
if a[j]<=amax then
begin
amax:=a[j];k:=j
end;
end;
a[k]:=a[i];a[i]:=amax
end;
writeln; writeln(f);
writeln(' МАССИВ ПОСЛЕ СОРТИРОВКИ ');
writeln(f,' МАССИВ ПОСЛЕ СОРТИРОВКИ ');
for i:=1 to n do
begin
write(' A[',i:2,']=',a[i]:3);
write(f,' A[',i:2,']=',a[i]:3);
if (i mod 5=0)or(i=n) then
begin
writeln;writeln(f)
end
end;
writeln(f);writeln(f);
writeln(f, 'ПРОГРАММУ СОСТАВИЛ ИВАНОВ И.И.');close(f)
end.
Результаты работы программы
ИСХОДНЫЙ МАССИВ
A[ 1]= 56 A[ 2]= 74 A[ 3]= 23 A[ 4]= 10 A[ 5]= 6
A[ 6]= 45 A[ 7]= 73 A[ 8]= 4 A[ 9]= 62 A[10]= 6
A[11]= 1 A[12]= 50
МАССИВ ПОСЛЕ СОРТИРОВКИ
A[ 1]= 1 A[ 2]= 4 A[ 3]= 6 A[ 4]= 6 A[ 5]= 10
A[ 6]= 23 A[ 7]= 45 A[ 8]= 50 A[ 9]= 56 A[10]= 62
A[11]= 73 A[12]= 74
ПРОГРАММУ СОСТАВИЛ ИВАНОВ И.И.
Пример программы упорядочения массива по не возрастанию (убыванию) методом обмена.
ПРОГРАММА:
program lab92; (* УПОРЯДОЧЕНИЕ МЕТОДОМ ОБМЕНА *)
var a:array[1..50] of integer;
i,r,n,k:integer; f:text;
begin
assign(f,'lab92.dat');rewrite(f);writeln;
write('ВВЕДИТЕ КОЛ-ВО ЭЛЕМЕНТОВ МАССИВА n=');read(n);
writeln('ВВЕДИТЕ ',n,' ЭЛЕМЕНТОВ МАССИВА');
for i:= 1 to n do read(a[i]);
writeln(f,' ИСХОДНЫЙ МАССИВ ');
writeln(' ИСХОДНЫЙ МАССИВ ');
for i:=1 to n do
begin
write(f,' A[',i:2,']=',a[i]:6);
write(' A[',i:2,']=',a[i]:6);
if i mod 5=0 then { ВЫВОД ПО 5 ЭЛ-ОВ В СТРОКЕ }
begin
writeln(f);writeln
end
end;
repeat
k:=0;
for i:=1 to n-1 do if a[i]<a[i+1] then
begin
r:=a[i];a[i]:=a[i+1];a[i+1]:=r;k:=k+1
end;
until k=0;
writeln; writeln(f);
writeln(' МАССИВ ПОСЛЕ СОРТИРОВКИ ');
writeln(f,' МАССИВ ПОСЛЕ СОРТИРОВКИ ');
for i:=1 to n do
begin
write(' A[',i:2,']=',a[i]:6);
write(f,' A[',i:2,']=',a[i]:6);
if (i mod 5=0)or(i=n) then
begin
writeln;writeln(f)
end
end;
writeln(f);writeln(f);
writeln(f,'ПРОГРАММУ СОСТАВИЛ ИВАНОВ И.И.');close(f)
end.
Результаты работы программы
ИСХОДНЫЙ МАССИВ
A[ 1]= 34 A[ 2]= 5 A[ 3]= 67 A[ 4]= 2 A[ 5]= 9
A[ 6]= 0 A[ 7]= 56 A[ 8]= 32 A[ 9]= 17 A[10]= 56
A[11]= 48 A[12]= 3 A[13]= 66 A[14]= 5
МАССИВ ПОСЛЕ СОРТИРОВКИ
A[ 1]= 67 A[ 2]= 66 A[ 3]= 56 A[ 4]= 56 A[ 5]= 48
A[ 6]= 34 A[ 7]= 32 A[ 8]= 17 A[ 9]= 9 A[10]= 5
A[11]= 5 A[12]= 3 A[13]= 2 A[14]= 0
ПРОГРАММУ СОСТАВИЛ ИВАНОВ И.И.
Контрольные вопросы:
1. Какие Вы знаете методы сортировки массивов?
2. В чем отличительная особенность каждого метода?
ЛАБОРАТОРНАЯ РАБОТА №9