- •Министерство образования Республики Беларусь
- •Постановка задачи
- •Описание циклов:
- •Описание констант:
- •Описание типов:
- •Описание переменных:
- •Типы констант и переменных:
- •Код программы:
- •Описание программы:
- •«Улучшенный пузырек»
- •Описание подпрограммы:
- •«Прямое включение»
- •Описание подпрограммы:
- •Результат:
Типы констант и переменных:
A,B,C:TM– определение массивов;
I,T:Integer– целочисленный тип, т.к. счетчики имеют только целые значения;
M:Integer– целочисленный тип, т.к. переменная М по условию принимает значения 2000, 100 и 10;
RK:integer– значение переставляемого элемента массива всегда будет целой;
F:Boolean– переключатель, имеющий два положения «Истина» или «Ложь»;
SR1,SR2,PR1,PR2:integer– количество всегда натуральное число.
Код программы:
program Sortirovka3;
{$APPTYPE CONSOLE}
uses
SysUtils,
Math;
const
n=2000;
type
tm = array[1..n] of Integer;
var
a,b,c: tm;
i,t,m,rk:Integer;
f:boolean;
sr1,sr2,pr1,pr2:integer;
begin
Randomize;
sr1:=0; sr2:=0; pr1:=0; pr2:=0;
for i:=1 to n do //Цикл Rand: Составление массива чисел
begin
a[i]:=Random(50);
end;
b:=a; //Присваивание массивам В и С значения элементов массива А
c:=a;
for i:=1 to 3 do //Цикл А1, сортировка массивов одной из трех размерности
begin
case i of //Определение размерности массивов
1:m:=10;
2:m:=100;
3:m:=2000;
end;
buble(m,b); //Вызов процедуры сортировки пузырьком
incl(m,c); //Вызов процедуры сортировки прямым включением
write(sr1,' sravn1; ',pr1 ,' perest1 ');
writeln(sr2,' sravn2; ',pr2 ,' perest2 ');
sr1:=0; sr2:=0; pr1:=0; pr2:=0; //Обновление значений количества сравнений и перестановок
//Повторная сортировка отсортированных массивов
buble(m,b);
incl(m,c);
write(sr1,' sravn1; ',pr1 ,' perest1 ');
writeln(sr2,' sravn2; ',pr2 ,' perest2 ');
sr1:=0; sr2:=0; pr1:=0; pr2:=0;
for t:=1 to (m div 2) do //Цикл А2, Обращение отсортированных по возрастанию массивов в массивы, отсортированных по убыванию
begin
rk:=b[t];
b[t]:=b[m-t+1];
b[m-t+1]:=rk;
rk:=c[t];
c[t]:=c[m-t+1];
c[m-t+1]:=rk;
end;
buble(m,b);
incl(m,c);
write(sr1,' sravn1; ',pr1 ,' perest1 ');
writeln(sr2,' sravn2; ',pr2 ,' perest2 ');
sr1:=0; sr2:=0; pr1:=0; pr2:=0;
end;
Readln;
end.
Описание программы:
В начале программы в цикле Rand мы задаем основной массив А. Он не будет участвовать в сортировке. Сортироваться будут массивы В и С. В цикле А1 задается одна из трех размерностей М массивов В и С. После этого путем вызова подпрограмм сортировки «пузырьком» и «включением» массивы В и С сортируются («улучшенный пузырек» для В, «прямое включение» для С). Количества сравнений и перестановок выводятся на экран и аннулируются. Те же самые действия происходят при сортировке отсортированных и обращенных массивов. Обращение отсортированных массивов В и С происходит в цикле А2. Элементы, одинаково расположенные относительно центрального элемента (в данном случае b[m div 2]). После каждой сортировки количества сравнений и перестановок обнуляются.
«Улучшенный пузырек»
Описание циклов:
Цикл А1: Сложный, внешний, с предусловием, с неизвестным числом повторений;
Цикл A2: Простой, вложенный, с предусловием, с известным числом повторений;
Описание констант:
Раздел описания констант:
M– константа, задающаяся непосредственно в самой программе и определяющая размерность массива.
Описание переменных:
Раздел описания переменных:
I– флажок;
J– номер сравниваемого элемента массива;
А – массив сортируемых элементов;
Остальные, не объявленные в подпрограмме переменные:
F– переключатель, контролирующий количество перестановок (если их на всем участке не было ни одной, то значит элемент массива находится на своем месте);
Sr1 – количество сравнений;
Pr1 – количество перестановок;
Rk– сохраненное значение элемента массива при перестановке его с другим элементом.
Типы констант и переменных(объявленных в подпрограмме):
M:Integer– целочисленный тип, т.к. М в подпрограмме может имеет значения 2000, 100 или 10.
I,J:Integer– номера элементов массива всегда целые.
A:TM– (о типе ТМ см. в описании программы);
Код подпрограммы:
procedure BUBLE (const m:integer; var a:tm);
var i,j:integer;
begin
i:=2;
f:=true;
while (i<=m) and (f=True) do //Цикл А1
begin
f:=False;
j:=m;
while j>=i do //Цикл А2
begin
if a[j-1]>a[j] then//Сравнение элементов массива
begin //Перестановка элементов массива
rk:= a[j-1];
a[j-1]:= a[j];
a[j]:=rk;
pr1:=pr1+1;
f:=True;
end;
sr1:=sr1+1;
j:=j-1;
end;
i:=i+1;
end;
end;