1) Яким чином можна відсортувати масив (з допомогою QuickSort) за двома параметрами? (наприклад, по вісі ОХ, а якшо рівні по ОХ, то по ОУ)? Якшо можна, з зразком коду на Pascal & C++.
2) Хто-небуть може перевести код у статті дерево фенвіка на Pascal? А то я дуже не дуже розумію С++, який круто написаний... Допоможіть...
to Olecksandr То сортування, шо було в задачці 1244 Пряма, воно оптимальне, чи найідіотськіше, яке можна придумати?
Повідомлень: 151 Звідки: Lviv NU FAMI Зареєстрований: 30.04.06
Опубліковано 11-02-2010 12:30
Код на Паскалі. Ідея дуже проста.
program QS_advanced;
{$APPTYPE CONSOLE}
const
NMax = 20;
Range = 100;
type
TSome = record
x, y: Integer;
end;
var
a: array [1..NMax] of TSome;
function less(const a, b: TSome): Boolean;
begin
if (a.x < b.x) then
begin
Result := true;
end else
begin
if (a.x > b.x) then
begin
Result := false;
end else
begin
Result := a.y < b.y;
end;
end;
end;
procedure QS(const L, R: Integer);
var
x, t: TSome;
i, j: Integer;
begin
i := L;
j := R;
x := a[(L + R) div 2];
repeat
while less(a[i], x) do Inc(i);
while less(x, a[j]) do Dec(j);
if i <= j then
begin
t := a[i];
a[i] := a[j];
a[j] := t;
Inc(i);
Dec(j);
end
until i > j;
if L < j then QS(L, j);
if i < r then QS(i, R);
end;
var
i, j, cnt, sx, k: Integer;
t: TSome;
begin
cnt := 0;
//generate
Randomize();
for i := 1 to NMax do
begin
Inc(cnt);
if (cnt <= NMax) then
begin
sx := cnt;
a[cnt].x := Random(Range);
a[cnt].y := Random(Range);
for j := 1 to Random(3) + 1 do
begin
Inc(cnt);
if (cnt <= NMax) then
begin
a[cnt].x := a[sx].x;
a[cnt].y := Random(Range);
end else
begin
break;
end;
end;
end else
begin
break;
end;
end;
//shuffle
for k := 1 to NMax do
begin
i := Random(Nmax) + 1;
j := Random(Nmax) + 1;
if (i <> j) then
begin
t := a[i];
a[i] := a[j];
a[j] := t;
end;
end;
//print
for i := 1 to NMax do
begin
Writeln(a[i].x, ' ', a[i].y);
end;
//sort
QS(1, Nmax);
Writeln;
//print sorted
for i := 1 to Nmax do
begin
Writeln(a[i].x, ' ', a[i].y);
end;
Readln;
end.
Ще одна реалізація але на С++. Я написав найпростіший варіант для сприйняиия паскалістом.
#include <cstdio>
#include <algorithm>
using namespace std;
#define INF (2000000000)
struct Some
{
int x, y;
};
bool cmp(const Some& a, const Some& b)
{
if (a.x < b.x)
{
return true;
}
if (a.x > b.x)
{
return false;
}
return a.y < b.y;
}
const int nmax = 20;
const int range = 100;
Some a[nmax];
void initSequence()
{
int i, j, up, sx;
for(i = 0; i < nmax; ++i)
{
sx = i;
a[i].x = rand() % range;
a[i].y = rand() % range;
up = rand() % 3 + 1;
for(j = 0; j < up && i < nmax; ++j, ++i)
{
a[i].x = a[sx].x;
a[i].y = rand() % range;
}
}
random_shuffle(a, a + nmax);
}
void printSequence()
{
int i;
for(i = 0; i < nmax; ++i)
{
printf("%d %d\n", a[i].x, a[i].y);
}
printf("\n");
}
void QS(int L, int R)
{
Some x = a[(L + R) >> 1];
int i = L;
int j = R;
do
{
while(cmp(a[i], x))
++i;
while(cmp(x, a[j]))
--j;
if (i <= j)
{
swap(a[i], a[j]);
++i;
--j;
}
}
while(i < j);
if (L < j)
{
QS(L, j);
}
if (i < R)
{
QS(i, R);
}
}
int main()
{
initSequence();
printSequence();
sort(a, a + nmax, cmp);
printSequence();
cupidon4uk написав:
Дуже спасибі... Не так то воно й страшно)..
Ну кому как... Мне курсовик задали на эту тему и я понимаю, что не получится ничего дельного придумать. Луше уж заказать курсовую работу https://kursach.site/, чем тратить время на понимание этих всех кодов. Другого выхода у меня и нету.