Лексикографическая сортировка числовых векторов. |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Лексикографическая сортировка числовых векторов. |
KerK |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 28 Пол: Мужской Репутация: 0 |
Вектор А=(А1,А2,…,Аn) считается лексикографически большим вектора В=(В1,В2,…,Вn), если существует k>=0 такое что Аi=Вi(i<=k),Ak+1>Bk+1. Составить программу лексикографической сортировки числовых векторов. При составлении программы сортировки использовать минимальную необходимую память и эффективные структуры данных.
|
volvo |
Сообщение
#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] ... |
Lapp |
Сообщение
#3
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Здесь ведь нет такого i, при котором a[i] = b[i] ... volvo, у него нумерация начинается с 1, а k>=0. Так что для твоего случая как бы k=0. Но тогда непонятно, в чем вообще суть. Что делать с i>k+1 ? На них вообще никаких условий не накладывается?... Странно как-то -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
volvo |
Сообщение
#4
|
Гость |
Вот и я про то же (что странно)... Кстати, вроде именно лексикографическая сортировка была где-то на форуме... Да и вообще алгоритмов сортировок штук 10 выложено, причем с описанием, какой требует меньше памяти, а какой - работает быстрее... Или основная проблема как раз и есть в определении отношения больше/меньше между векторами?
|
Michael_Rybak |
Сообщение
#5
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата Что делать с i>k+1 ? На них вообще никаких условий не накладывается?... Странно как-то Лексикографический порядок вводится на последовательностях точно так же, как на обычных строках: сравниваем первые элементы; если они равны - сравниваем вторые, и т.д. до первой пары отличающихся элементов. Результат их сравнения и будет результатом сравнения векторов. Если же все пары равны, то и векторы равны. Ковшовая сортировка здесь не подходит, потому что у нас нет ограничений на числа. Поступим по аналогии. Идея: сначала сортируем векторы по первому элементу. Затем пробегаем по ним в этом порядке (в порядке неубывания первого элемента), выделяем группы векторов, у которых первый элемент одинаковый, и для каждой такой группы вызываем рекурсивно сортировку по второму элементу, и т. д. Чтобы не тратить кучу времени на обмен местами векторов, сами вектора не трогаем, а сортируем только номера векторов. Примерно так:
Пузырьком я, понятно, для наглядности. Вставь там какую-нибудь быструю сортировку. Сложность этого алгоритма будет O(len * n log n). Быстрее, надеюсь, нельзя И памяти дополнительной - O(n). Пробуй, спрашивай. |
KerK |
Сообщение
#6
|
Новичок Группа: Пользователи Сообщений: 28 Пол: Мужской Репутация: 0 |
Большой фенкс! Сегодня вечером попробую!
|
Текстовая версия | 6.11.2024 19:02 |