Часто в задачах требуется отсортировать массив и достаточно быстро. Можно использовать сортировку Хоара:
procedure qsort (k, r: integer);
var i,j: integer;
z,b: real;
begin
b:=a[(k+r) div 2 ];
i:=k; j:=r;
while i<=j do begin
while a[i]<b do i:=i+1;
while a[j]>b do j:=j-1;
if i<=j then begin
z:=a[i]; a[i]:=a[j]; a[j]:=z;
i:=i+1; j:=j-1;
end;
end;
if k<j then qsort(k, j);
if i<r then qsort(i, r);
end;
Этот пример взят из qsort.pas, который есть в полной установке Borland Pascal 7.0. Чтобы применить эту процедуру используйте вызов qsort(1,n), где n - размер массива.Это одна из быстрых сортировок, которая применяется для больших массивов.
Чтобы запомнить этот алгоритм, нужно несколько раз провести пошаговое выполнение этой процедуры на нескольких тестовых примерах.
Идея метода - в разбиении массива на две части и перестановки из левой части в правую наибольших элементов и, наоборот, из правой в левую - наименьших. Это делает цикл While. Когда все элементы переставлены, рассматривается каждая часть как новый массив и с каждым из них выполняется такая же процедура до тех пор, пока не останется 1 элемент. Видно, что этот алгоритм рекурсивный, причем вызов самой себя происходит два раза: для левой и для правой части массива.
Массив упорядочивается по возрастанию. Если надо по убыванию, то просто переставьте знаки < и > в циклах while. где идет сравнение a[i] с серединным элементом массива b.
Иногда нужно отсортировать по двум, трем и даже по четырем параметрам. Например, упорядочить фамилию, имя, отчество по алфавиту. Причем сортировка строк работает точно также как и сортировка чисел. Не надо придумывать дополнительные циклы для проверки каждого символа!
Предлагаем разобрать этот пример на сортировке пузырьком. Эта сортировка похожа на процесс всплытия пузырьков (более легких по отношению к молекулам воды) в кипящей воде. Сравниваются всегда только два рядом стоящие элементы.
var
i,j,n,z:integer;
f:boolean;
a:array[1..100] of integer;
begin
readln(n);
for i:=1 to n do read(a[i]);
i :=1;
repeat
f:=true;
for j:=1 to n-i do
if a[j]>a[j+1] then begin
z:=a[j]; a[j]:=a[j+1]; a[j+1]:=z;
f:=false;
end;
inc(i);
until f;
for i:=1 to n do write(a[i], ' ');
end.
Итак, если фамилии разные, то все просто, а если одинаковы, то проверяем имена. Теперь если имена разные, то тоже понятно, а если они одинаковы, то сравниваем отчества.
Обозначим массив для фамилий как Family, под имена - Name, под отчества - Parent. Тогда условие для сравнения в сортировке выглядит так:
(Family[j]>Family[j+1]) or (Family[j]=Family[j+1])
and ((Name[j]>Name[j+1]) or (Name[j]=Name[j+1])
and (Parent[j]>Parent[j+1]))
При этом придется делать перестановку всех трех массивов. Чтобы этого избежать используйте тип запись.
type fio=record
family:string[25];
name:string[15];
parent:string[25];
end;
var
i,j,n:integer;
f:boolean;
c:char;
s:string;
z:fio;
a:array[1..100] of fio;
begin
readln(n);
for i:=1 to n do begin
{организуем посимвольный ввод фамилии, имени, отчества через пробел}
read(c); s:='';
while c<>' ' do begin
s:=s+c; read(c);
end;
a[i].family:=s;
read(c); s:='';
while c<>' ' do begin
s:=s+c; read(c);
end;
a[i].name:=s;
readln(a[i].parent);
end;
i :=1;
repeat
f:=true;
for j:=1 to n-i do
if(a[j].Family>a[j+1].Family) or (a[j].Family=a[j+1].Family)
and ((a[j].Name>a[j+1].Name) or (a[j].Name=a[j+1].Name)
and (a[j].Parent>a[j+1].Parent))then begin
z:=a[j]; a[j]:=a[j+1]; a[j+1]:=z;
f:=false;
end;
inc(i);
until f;
for i:=1 to n do writeln(a[i].family,' ', a[i].name, ' ', a[i].parent);
end.
Тоже условие можно ввести и в сортировку Хоара, только там нужно вводить два условия: одно для сравнения на "меньше", другой на "больше", а переменные z и b должны быть объявлены как fio.
Такого же типа сортировки с двумя условиями применяют и в случае упорядочивания данных по минимальному весу предмета и его максимальной стоимости в классической задаче о рюкзаке. В этом случае знаки < и > нужно расставить в условии так, чтобы массивы упорядочивались правильно.
Задача о рюкзаке: Дано N предметов K с указанием веса W и стоимости каждого предмета V. Определить набор предметов T с максимальной стоимостью груза S, вес которого не больше P.
Решение: Для решения этой задачи используем рекурсивный перебор вариантов для массива весов, проверяя условия на достижение оптимального веса P и максимальной стоимости S выбранных предметов из массива T. Каждый раз начинаем перебор с текущего предмета в массиве W.
Для эффективного перебора необходимо отсортировать массив стоимостей по убыванию и затем, для одинаковых значений стоимостей, массив весов сортируем по возрастанию, например, по методу пузырька.
Var now, t, w, v:array[1..50] of integer;
S, Smax, N, P, i:integer;
Procedure Swap(var A, B: integer);
Begin
A := A xor B;
B := A xor B;
A := A xor B;
End;
Procedure Solve (k, P, S:integer);
Var i: integer;
Begin
If (P<0) then exit;
If ((k>N) or (P=0)) and (S > Smax) then Begin
T := now ; Smax := S;
End
Else if (k<=N) then begin
For I := 1 to ( P div W [k] ) do
Now [k] := I; Solve( k+1, P - I * W [k], S + i* V [k] )
End;
End;
Procedure Sort;
Var I,j:integer;
Begin
For i:=1 to N-1 do
For j:=1 to n-i do
If (v[i]>v[i+1]) or (v[i]=v[i+1]) and (w[i]<w[i+1]) then
begin
Swap(v[i],v[i+1]);
Swap(w[i],w[i+1]);
End;
End;
BEGIN
{ввод данных}
Readln( N, P );
For i:=1 to N do Readln( W [i], V [i] );
{сортировка массивов}
sort;
{обнуление переменных}
Smax:=0;
Fillchar(now, sizeof(now),0);
{вызов рекурсивной процедуры}
Solve (1, P, 0);
{вывод результатов}
Writeln( Smax );
For i:=1 to N do
if T [i] <> 0 then writeln( i, T [i], W [i], V [i] );
END.
Такая же ситуация возникает и при определении выпуклого многоугольника. Перед решением задачи рекомендуется отсортировать точки по правиле левого верхнего угла, т.е по х - по возрастанию, по у - по убыванию. и только затем перебирать точки и составлять многоугольник.
Задача о построении выпуклого многоугольника: Даны точки на плоскости. Построить по этим точкам выпуклый многоугольник.
Решение: Есть несколько алгоритмов решения данной задачи:
1) Все треугольники, образованные тройками соседних вершин в порядке их обхода, имеют одну ориентацию. Просматривая все тройки точек по очереди, вычисляем ориентированную площадь треугольника по трем точкам. Если ориентация точек не совпадает с заданной (по часовой стрелке), то точка лежит вне многоугольника.
2) Пусть найден центр тяжести всех координат. Упорядочим точки относительно полярного угла (можно сравнивать сумму абсолютных значений координат). Так как внутренние точки принадлежат некоторому треугольнику, то будем последовательно просматривать отсортированный массив и удалять внутренние вершин. Оставшиеся точки будут являться вершинами выпуклой оболочки.
3) Отрезок, определяемый двумя точками, является ребром выпуклой оболочки тогда и только тогда, когда все другие точки множества лежат на отрезке или с одной стороны от него. Для каждого из этих отрезков можно определить положение остальных N-2 точек относительно него, так чтобы угол, образованный лучами имел минимальное значение. Если таких точек несколько, то выбирается точка, находящаяся на максимальном расстоянии от текущей. Таким образом, можно найти все пары точек, определяющих ребра выпуклой оболочки.
4) Исходное множество из N точек разбивается на два подмножества, каждое из которых будет содержать одну из двух ломаных, которые при соединении образуют выпуклую оболочку. Для начала нужно определить две точки, которые будут являться соседними вершинами выпуклой оболочки. Проведем прямую через эти две точки. Нужно найти точку максимально удаленную от прямой. Все точки, лежащие в образованном треугольнике исключаются из дальнейшего рассмотрения. Остальные точки будут делиться на два подмножества: точки, которые лежать левее, и точки, которые лежат правее новых прямых. С каждым из подмножеств проделываем то же самое. Каждое из них содержит ломаные, которые и дают выпуклую оболочку. Это реализуется рекурсивной процедурой, которая для данного ей множества возвращает соответствующую часть выпуклой оболочки.
Комментариев нет:
Отправить комментарий