Лексикографическая сортировка числовых векторов. |
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. Составить программу лексикографической сортировки числовых векторов. При составлении программы сортировки использовать минимальную необходимую память и эффективные структуры данных.
|
Michael_Rybak |
Сообщение
#2
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата Что делать с i>k+1 ? На них вообще никаких условий не накладывается?... Странно как-то Лексикографический порядок вводится на последовательностях точно так же, как на обычных строках: сравниваем первые элементы; если они равны - сравниваем вторые, и т.д. до первой пары отличающихся элементов. Результат их сравнения и будет результатом сравнения векторов. Если же все пары равны, то и векторы равны. Ковшовая сортировка здесь не подходит, потому что у нас нет ограничений на числа. Поступим по аналогии. Идея: сначала сортируем векторы по первому элементу. Затем пробегаем по ним в этом порядке (в порядке неубывания первого элемента), выделяем группы векторов, у которых первый элемент одинаковый, и для каждой такой группы вызываем рекурсивно сортировку по второму элементу, и т. д. Чтобы не тратить кучу времени на обмен местами векторов, сами вектора не трогаем, а сортируем только номера векторов. Примерно так:
Пузырьком я, понятно, для наглядности. Вставь там какую-нибудь быструю сортировку. Сложность этого алгоритма будет O(len * n log n). Быстрее, надеюсь, нельзя И памяти дополнительной - O(n). Пробуй, спрашивай. |
Текстовая версия | 24.04.2024 20:47 |