IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Лексикографическая сортировка числовых векторов.
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Вектор А=(А1,А2,…,Аn) считается лексикографически большим вектора В=(В1,В2,…,Вn), если существует k>=0 такое что Аi=Вi(i<=k),Ak+1>Bk+1. Составить программу лексикографической сортировки числовых векторов. При составлении программы сортировки использовать минимальную необходимую память и эффективные структуры данных.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






KerK, если
Цитата
Аi=Вi(i<=k),Ak+1>Bk+1
, то что делать с 2-мя вот такими векторами:
A = (1, 2, 3, 4, 5)
и
B = (2, 3, 4, 5, 6)?

Здесь ведь нет такого i, при котором a[i] = b[i] ...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(volvo @ 8.11.2006 12:32) *

Здесь ведь нет такого i, при котором a[i] = b[i] ...

volvo, у него нумерация начинается с 1, а k>=0. Так что для твоего случая как бы k=0.
Но тогда непонятно, в чем вообще суть. Что делать с i>k+1 ? На них вообще никаких условий не накладывается?... Странно как-то


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Вот и я про то же (что странно)... Кстати, вроде именно лексикографическая сортировка была где-то на форуме... Да и вообще алгоритмов сортировок штук 10 выложено, причем с описанием, какой требует меньше памяти, а какой - работает быстрее... Или основная проблема как раз и есть в определении отношения больше/меньше между векторами?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Что делать с i>k+1 ? На них вообще никаких условий не накладывается?... Странно как-то


Лексикографический порядок вводится на последовательностях точно так же, как на обычных строках: сравниваем первые элементы; если они равны - сравниваем вторые, и т.д. до первой пары отличающихся элементов. Результат их сравнения и будет результатом сравнения векторов. Если же все пары равны, то и векторы равны.


Ковшовая сортировка здесь не подходит, потому что у нас нет ограничений на числа. Поступим по аналогии.

Идея: сначала сортируем векторы по первому элементу. Затем пробегаем по ним в этом порядке (в порядке неубывания первого элемента), выделяем группы векторов, у которых первый элемент одинаковый, и для каждой такой группы вызываем рекурсивно сортировку по второму элементу, и т. д.

Чтобы не тратить кучу времени на обмен местами векторов, сами вектора не трогаем, а сортируем только номера векторов.

Примерно так:



//не тестил и не компилил
//volvo, ты мне простишь неработающие в TP комментарии "//"?

var vv: array[1 .. n, 1 .. len] of integer;
sorted: array[1 .. n] of integer; //сортируемый массив номеров векторов

procedure SortAt(low_bound, up_bound, sort_by: integer)
//отсортировать группу от sorted[low_bound] до sorted[up_bound] по элементу sort_by

var i, j, t: integer;
begin
if sort_by = len + 1 then //сортировка по (len+1)му элементу -> процесс окончен
exit;

//сортируем пузырьком
for i := 1 to up_bound - low_bound + 1 do
for j := low_bound to up_bound - 1 do
if vv[sorted[j], sort_by] > vv[sorted[j + 1], sort_by] then
begin
//меняем вектора местами
t := sorted[j];
sorted[j] := sorted[j + 1];
sorted[j + 1] := t;
end;

//теперь выделяем группы и рекурсивно их сортируем
i := low_bound;
while i <= up_bound do begin
j := i;
while (j < up_bound) and (vv[sorted[j + 1], sort_by] = vv[sorted[j], sort_by]) do
Inc(j);

//у векторов от sorted[i] до sorted[j] совпадает элемент sort_by
SortAt(i, j, sort_by + 1);
i := j + 1;
end;
end;

var i: integer;
begin
...//читаем вектора

//изначальный порядок
for i := 1 to n do
sorted[i] := i;

SortAt(1, n, 1);
...
end.


Пузырьком я, понятно, для наглядности. Вставь там какую-нибудь быструю сортировку.

Сложность этого алгоритма будет O(len * n log n). Быстрее, надеюсь, нельзя smile.gif
И памяти дополнительной - O(n). Пробуй, спрашивай.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 28
Пол: Мужской

Репутация: -  0  +


Большой фенкс! Сегодня вечером попробую!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 6.11.2024 19:02
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name