Пересечение множества точек. |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Пересечение множества точек. |
Krjuger |
27.05.2011 15:59
Сообщение
#1
|
Профи Группа: Пользователи Сообщений: 652 Пол: Мужской Реальное имя: Алексей Репутация: 20 |
Собственно задача такая.
Дано 2 множества точек.Найти пересечение и разность этих множеств. Собственно вопрос возник, как задать эти множества.У меня множесто точек ассоциируется с координатами точки. И выглядеть дожно как то.
Тут TToch это координаты х и у, а значение- множества, составленные из чисел от 1 до 100.Кстати следующий вопрос.Числа могут быть только целые или нет? |
IUnknown |
27.05.2011 17:33
Сообщение
#2
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Цитата И выглядеть дожно как то. Это именно задано, или это твое предположение? Нет, в принципе никаких проблем, можно реализовать аналог "множества из записей", можно - массив множеств, как у тебя (хоть это и бессмысленно - ты не сможешь определить в таком массиве, где чья координата: будут отдельно упорядочены абсциссы, а отдельно - ординаты, все перемешается напрочь).Однако, у меня "множество точек" ассоциируется только с массивом записей, каждая из которых хранит координаты одной точки (или просто с двумерным массивом). |
Krjuger |
27.05.2011 18:16
Сообщение
#3
|
Профи Группа: Пользователи Сообщений: 652 Пол: Мужской Реальное имя: Алексей Репутация: 20 |
> Это именно задано, или это твое предположение?
Это сугубо мое предположение.Я понял недостаток такого варианта,а жаль. Пока что наваял следующее.(к несчастью именно наваял ) код (Показать/Скрыть)
Добавлено через 15 мин. Немного изменил.Вроде работает.Но до конца не уверен,проверил всего на 3 тестах и с малыми размерностями. код (Показать/Скрыть)
Еще по какой то причине последний readln банально игнорируется,возможно из-за dos boxa. Сообщение отредактировано: Lapp - 28.05.2011 1:25 |
IUnknown |
27.05.2011 18:39
Сообщение
#4
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Цитата последний readln банально игнорируется,возможно из-за dos boxa. DosBox ни при чем. Измени в коде ВСЕ read на ReadLn - не будет игнорироваться. Об этом уже столько раз написано мной на форуме - я со счета сбился...Хм... По поводу твоего кода: будешь оставлять так, или посмотришь, как в подобных случаях рекомендует поступать господин Ульман (вместе с Ахо и Хопкрофтом)? У него есть реализация множества на деревьях. |
-TarasBer- |
27.05.2011 19:08
Сообщение
#5
|
Гость |
> или посмотришь, как в подобных случаях рекомендует поступать господин Ульман (вместе с Ахо и Хопкрофтом)? У него есть реализация множества на деревьях.
Кстати, как у них сделано, мне тоже интересно. Потому что я бы оптимизировал перебор (поиск совпадений) при помощи хеширования, а как делать это деревом - не знаю. |
Krjuger |
27.05.2011 20:05
Сообщение
#6
|
Профи Группа: Пользователи Сообщений: 652 Пол: Мужской Реальное имя: Алексей Репутация: 20 |
Я бы взглянул,потому что у меня оптимизации просто ноль.Но сам я врятли смогу,у меня с деревьями дела весьма плохи.Книжку глянул,чето я даже идеи оптимизации не совсем понял.
Сообщение отредактировано: Krjuger - 27.05.2011 20:12 |
IUnknown |
27.05.2011 20:49
Сообщение
#7
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Ну, у них там много разных реализаций на самом деле - и с обычными двоичными деревьями (Krjuger, это есть у меня на сайте, можешь посмотреть), и с нагруженными деревьями, и со сбалансированными деревьями. Целая глава этому посвящена. Я ж не буду всю главу перепечатывать. Если кому надо - говорите куда выслать (там 4Мб), или сами найдите эту книжку, она есть на Инфанате, например, если ссылка еще не умерла.
|
Krjuger |
27.05.2011 22:12
Сообщение
#8
|
Профи Группа: Пользователи Сообщений: 652 Пол: Мужской Реальное имя: Алексей Репутация: 20 |
Ну книгу я скачал и мельком просмотрел,с первого раза осмыслению оно не поддалось.
|
IUnknown |
27.05.2011 23:56
Сообщение
#9
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Значит, читай второй раз, третий, и так далее...
Ну, смотри: открой книгу на стр 112, и посмотри на приведенную там процедуру Intersection... Она тебе найдет "пересечение" связанных списков. Если ты все свои данные запихаешь в два списка (хочешь - сразу поддерживая упорядоченность, вставляя элементы куда нужно, о чем говорят авторы, хочешь - потом пробежать и отсортировать - дело 5 строк кода), а потом применишь эту процедуру - то получишь те точки, которые присутствуют и в первом и во втором списках. Как сделать Difference - там же написано, на 113 странице. Эта программа уже будет гораздо лучше, чем то, что есть у тебя сейчас. |
Lapp |
28.05.2011 1:58
Сообщение
#10
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Я извиняюсь за вторжение и одновременно за флуд..
Krjuger, можно вопросик? )) Мы, конечно, люди темные, университетов не кончали (С).. Но объясни мне, темному человеку - какую цель ты преследовал вот этим: var Это что, специальная защита от переприсваиваний? Почему не так: varЕсть на то причина? Немного поясню: я бы не встрял, но тут такие дела.. Решил я убрать под спойлеры программные тексты, чтоб тема была читабельнее. Убрал - фигак, пост пропал совсем. Чисто, как попка младенца. Стал разбираться.. и разбирался больше часа в общей сложности. Сначала выяснил, что форумскому софту не нравится большое количество квадратных скобок. Потом обнаружились другие подробности.. Короче, в результате все поправилось переделкой верхней цитаты в старинный эпистолярный жанр )). Я извиняюсь за это, позже попробую исправить этот баг. Но в процессе экспериментов по поиску причины я и обратил внимание на ту деталь, к которой теперь в свою очередь привлекаю внимание автора темы.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Krjuger |
28.05.2011 13:20
Сообщение
#11
|
Профи Группа: Пользователи Сообщений: 652 Пол: Мужской Реальное имя: Алексей Репутация: 20 |
А это,чтобы вы могли исправить ошибки форумского софта......О как завернул.
Цитата Мы, конечно, люди темные, университетов не кончали Ну мы пока что люди ничуть не светлые,самим еще долго до просветления. |
Текстовая версия | 27.04.2024 13:28 |