Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 28.03.2024 23:56:11 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
3 липня 1928 року в США був проданий перший у світі телевізор. Коштував він 75 доларів, що дорівнювало двом середнім зарплатам простого робітника.
Події
ПнВтСрЧтПтСбНд
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

Birthday(s):
AVATARAlex_neo
AVATARWinner
AVATARinvarian
AVATARsvadsak lol

Перегляд теми
ACM Контестер | ACM College | Задачі
Автор Готуємось до олімпіади
cupidon4uk
Користувач

Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09
Опубліковано 10-02-2010 22:34
У мене два запитання до всі форумчан.

1) Яким чином можна відсортувати масив (з допомогою QuickSort) за двома параметрами? (наприклад, по вісі ОХ, а якшо рівні по ОХ, то по ОУ)? Якшо можна, з зразком коду на Pascal & C++.

2) Хто-небуть може перевести код у статті дерево фенвіка на Pascal? А то я дуже не дуже розумію С++, який круто написаний... Допоможіть...

to Olecksandr То сортування, шо було в задачці 1244 Пряма, воно оптимальне, чи найідіотськіше, яке можна придумати?


GoogleHireMe 557679737 mylyanyk.ivan [Lviv_NU] Надіслати приватне повідомлення
Автор RE: Готуємось до олімпіади
PAWLO1993
Користувач

Повідомлень: 72
Звідки: LNU
Зареєстрований: 27.02.08
Опубліковано 10-02-2010 22:55
1. Погугли сортування по 2 ключам. досить доступно є описано в Кнута.
Надіслати приватне повідомлення
Автор RE: Готуємось до олімпіади
Olecksandr
Модератор

Повідомлень: 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();

initSequence();
printSequence();
QS(0, nmax - 1);
printSequence();
return 0;
}






А взагалі ще можна почитати про використання STL хорошу і доступну. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2
Змінив(ла) Olecksandr, 11-02-2010 12:33
sashka 324288154 Olecksandr Voeca [Lviv NU] Надіслати приватне повідомлення
Автор RE: Готуємось до олімпіади
Olecksandr
Модератор

Повідомлень: 151
Звідки: Lviv NU FAMI
Зареєстрований: 30.04.06
Опубліковано 11-02-2010 12:34
Доречі я вперше(давним-давно) писав сортування по двох ключах подібним способом до твого.
sashka 324288154 Olecksandr Voeca [Lviv NU] Надіслати приватне повідомлення
Автор RE: Готуємось до олімпіади
cupidon4uk
Користувач

Повідомлень: 393
Звідки: LNU
Зареєстрований: 02.01.09
Опубліковано 11-02-2010 15:14
Дуже спасибі... Не так то воно й страшно)..


GoogleHireMe 557679737 mylyanyk.ivan [Lviv_NU] Надіслати приватне повідомлення
Автор RE: Готуємось до олімпіади
Zahar
Користувач

Повідомлень: 29
Зареєстрований: 20.06.22
Опубліковано 20-06-2022 14:30
Дякую за інформацію! Я теж шукав цей код
Надіслати приватне повідомлення
Автор RE: Готуємось до олімпіади
Tikot
Користувач

Повідомлень: 233
Зареєстрований: 09.01.22
Опубліковано 12-06-2023 17:54
cupidon4uk написав:
Дуже спасибі... Не так то воно й страшно)..


Ну кому как... Мне курсовик задали на эту тему и я понимаю, что не получится ничего дельного придумать. Луше уж заказать курсовую работу https://kursach.site/, чем тратить время на понимание этих всех кодов. Другого выхода у меня и нету.
https://anna-kuchyna.com/ Надіслати приватне повідомлення
Перейти на форум:
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

настільні ігри

торт

клавіатура, навушники, флешки і т.д.

квитки в кіно

квитки в аквапарк

квитки на пейнтбол

книги

футболки з логотипом змагання

Для участі в голосуваннях Ви повинні залогуватись.
Міні-чат +
Зараз на сайті -
Гостей: 2
На сайті немає зареєстрованних користувачів

Користувачів: 5,091
новачок: dasha_sha
Powered by PHP-Fusion © 2003-2006
LNU ACMania © 2004-2011 e-mail: webmaster@acm.lviv.ua
23,443,973 унікальних відвідувачів
Our projects: ACM Contester, _College.
  пїЅпїЅпїЅпїЅпїЅпїЅпїЅ Orphus     bigmir)net TOP 100