1. Заголовок темы должен быть информативным. В противном случае тема удаляется ... 2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения. 3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали! 4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора). 5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM! 6. Одна тема - один вопрос (задача) 7.Проверяйте программы перед тем, как разместить их на форуме!!! 8.Спрашивайте и отвечайте четко и по существу!!!
Собственно задача такая. Дано 2 множества точек.Найти пересечение и разность этих множеств. Собственно вопрос возник, как задать эти множества.У меня множесто точек ассоциируется с координатами точки. И выглядеть дожно как то.
type TMnoz= set of 0..100; TToch=array[0..1] of TMoz;
Тут TToch это координаты х и у, а значение- множества, составленные из чисел от 1 до 100.Кстати следующий вопрос.Числа могут быть только целые или нет?
Это именно задано, или это твое предположение? Нет, в принципе никаких проблем, можно реализовать аналог "множества из записей", можно - массив множеств, как у тебя (хоть это и бессмысленно - ты не сможешь определить в таком массиве, где чья координата: будут отдельно упорядочены абсциссы, а отдельно - ординаты, все перемешается напрочь).
Однако, у меня "множество точек" ассоциируется только с массивом записей, каждая из которых хранит координаты одной точки (или просто с двумерным массивом).
Это сугубо мое предположение.Я понял недостаток такого варианта,а жаль. Пока что наваял следующее.(к несчастью именно наваял )
код(Показать/Скрыть)
program kurs26; var mas1 : array[0..1,0..100] of real; mas2 : array[0..1,0..100] of real; peres : array[0..1,0..100] of real; razn1 : array[0..1,0..100] of real; razn2 : array[0..1,0..100] of real; n,p :integer; n1,n2 : integer; pos : integer; Ppos,Rpos1,Rpos2 : integer; begin writeln('Vvedite kol-vo tochek v pervom mnozestve'); read(n1); for n:=0 to n1-1 do begin writeln('Vvedite koordinati elementa pervvogo mnozestva'); read(mas1[0,n]); read(mas1[1,n]); end; writeln('Vvedite kol-vo tochek vo vtorom mnozestve'); read(n2); for n:=0 to n2-1 do begin writeln('Vvedite koordonati elementa vtorogo mnozestva'); read(mas2[0,n]); read(mas2[1,n]); end;
pos := 0; for n:=0 to n1-1 do begin for p:=0 to n2-1 do begin if ((mas1[0,n]=mas2[0,p]) and (mas1[1,n]=mas2[1,p])) then begin peres[0][pos]:=mas1[0][n]; peres[1][pos]:=mas1[1][n]; pos:=pos+1; end; end; end; Ppos:= pos-1;
pos:=0; for n:=0 to n1-1 do begin for p:=0 to Ppos-1 do begin if ((mas1[0,n]<>peres[0,p]) or (mas1[1,n]<>peres[1,p])) then begin razn1[0,pos]:=mas1[0,n]; razn1[1,pos]:=mas1[1,n]; pos:=pos+1; end; end; end; Rpos1:=pos-1;
pos:=0; for n:=0 to n2-1 do begin for p:=0 to Ppos-1 do begin if ((mas2[0,n]<>peres[0,p]) or (mas2[1,n]<>peres[1,p])) then begin razn2[0,pos]:=mas2[0,n]; razn2[1,pos]:=mas2[1,n]; pos:=pos+1; end; end; end;
writeln('Ishodnie mnozestva:'); writeln('Pervoe:'); for n:=0 to n1-1 do begin write('(',mas1[0,n],',',mas1[1,n],') '); writeln; end; writeln('Vtoroe:'); for n:=0 to n2-1 do begin write('(',mas2[0,n],',',mas2[1,n],') '); writeln; end;
writeln('Raznost* pervogo i vtorogo mnozestv'); for n:=0 to Rpos1 do begin write('(',razn1[0,n],',',razn1[1,n],') '); writeln; end; { writeln('Raznost* vtorogo i pervogo mnozestv'); for n:=0 to n2-1 do begin write('(',razn2[0,n],',',razn2[1,n],') '); writeln; end; } writeln('Peresechenie mnozestv'); for n:=0 to Ppos do begin write('(',peres[0,n],',',peres[1,n],') '); writeln; end; readln; end.
Добавлено через 15 мин. Немного изменил.Вроде работает.Но до конца не уверен,проверил всего на 3 тестах и с малыми размерностями.
код(Показать/Скрыть)
program kurs26; var mas1 : array[0..1,0..100] of real; mas2 : array[0..1,0..100] of real; peres : array[0..1,0..100] of real; razn1 : array[0..1,0..100] of real; razn2 : array[0..1,0..100] of real; n,p :integer; n1,n2 : integer; pos : integer; Ppos,Rpos1,Rpos2 : integer; begin writeln('Vvedite kol-vo tochek v pervom mnozestve'); read(n1); for n:=0 to n1-1 do begin writeln('Vvedite koordinati elementa pervvogo mnozestva'); read(mas1[0,n]); read(mas1[1,n]); end; writeln('Vvedite kol-vo tochek vo vtorom mnozestve'); read(n2); for n:=0 to n2-1 do begin writeln('Vvedite koordonati elementa vtorogo mnozestva'); read(mas2[0,n]); read(mas2[1,n]); end;
pos := 0; for n:=0 to n1-1 do begin for p:=0 to n2-1 do begin if ((mas1[0,n]=mas2[0,p]) and (mas1[1,n]=mas2[1,p])) then begin peres[0][pos]:=mas1[0][n]; peres[1][pos]:=mas1[1][n]; pos:=pos+1; end; end; end; Ppos:= pos-1;
pos:=0; for n:=0 to n1-1 do begin for p:=0 to Ppos do begin if (mas1[0,n]<>peres[0,p]) or (mas1[1,n]<>peres[1,p]) then begin razn1[0,pos]:=mas1[0,n]; razn1[1,pos]:=mas1[1,n]; pos:=pos+1; end; end; end; Rpos1:=pos-1;
pos:=0; for n:=0 to n2-1 do begin for p:=0 to Ppos do begin if ((mas2[0,n]<>peres[0,p]) or (mas2[1,n]<>peres[1,p])) then begin razn2[0,pos]:=mas2[0,n]; razn2[1,pos]:=mas2[1,n]; pos:=pos+1; end; end; end; Rpos2:= pos-1;
writeln('Ishodnie mnozestva:'); writeln('Pervoe:'); for n:=0 to n1-1 do begin write('(',mas1[0,n],',',mas1[1,n],') '); writeln; end; writeln('Vtoroe:'); for n:=0 to n2-1 do begin write('(',mas2[0,n],',',mas2[1,n],') '); writeln; end;
writeln('Raznost* pervogo i vtorogo mnozestv');
for n:=0 to Rpos1 do begin write('(',razn1[0,n],',',razn1[1,n],') '); writeln; end;
writeln('Raznost* vtorogo i pervogo mnozestv'); for n:=0 to Rpos2 do begin write('(',razn2[0,n],',',razn2[1,n],') '); writeln; end;
writeln('Peresechenie mnozestv'); for n:=0 to Ppos do begin write('(',peres[0,n],',',peres[1,n],') '); writeln; end; readln; end.
Еще по какой то причине последний readln банально игнорируется,возможно из-за dos boxa.
последний readln банально игнорируется,возможно из-за dos boxa.
DosBox ни при чем. Измени в коде ВСЕ read на ReadLn - не будет игнорироваться. Об этом уже столько раз написано мной на форуме - я со счета сбился...
Хм... По поводу твоего кода: будешь оставлять так, или посмотришь, как в подобных случаях рекомендует поступать господин Ульман (вместе с Ахо и Хопкрофтом)? У него есть реализация множества на деревьях.
> или посмотришь, как в подобных случаях рекомендует поступать господин Ульман (вместе с Ахо и Хопкрофтом)? У него есть реализация множества на деревьях.
Кстати, как у них сделано, мне тоже интересно. Потому что я бы оптимизировал перебор (поиск совпадений) при помощи хеширования, а как делать это деревом - не знаю.
Я бы взглянул,потому что у меня оптимизации просто ноль.Но сам я врятли смогу,у меня с деревьями дела весьма плохи.Книжку глянул,чето я даже идеи оптимизации не совсем понял.
Ну, у них там много разных реализаций на самом деле - и с обычными двоичными деревьями (Krjuger, это есть у меня на сайте, можешь посмотреть), и с нагруженными деревьями, и со сбалансированными деревьями. Целая глава этому посвящена. Я ж не буду всю главу перепечатывать. Если кому надо - говорите куда выслать (там 4Мб), или сами найдите эту книжку, она есть на Инфанате, например, если ссылка еще не умерла.
Ну, смотри: открой книгу на стр 112, и посмотри на приведенную там процедуру Intersection... Она тебе найдет "пересечение" связанных списков. Если ты все свои данные запихаешь в два списка (хочешь - сразу поддерживая упорядоченность, вставляя элементы куда нужно, о чем говорят авторы, хочешь - потом пробежать и отсортировать - дело 5 строк кода), а потом применишь эту процедуру - то получишь те точки, которые присутствуют и в первом и во втором списках. Как сделать Difference - там же написано, на 113 странице. Эта программа уже будет гораздо лучше, чем то, что есть у тебя сейчас.
Я извиняюсь за вторжение и одновременно за флуд.. Krjuger, можно вопросик? )) Мы, конечно, люди темные, университетов не кончали (С).. Но объясни мне, темному человеку - какую цель ты преследовал вот этим:
Цитата(Krjuger @ 27.05.2011 19:16)
var mas1 : array[0..1,0..100] of real; mas2 : array[0..1,0..100] of real; peres : array[0..1,0..100] of real; razn1 : array[0..1,0..100] of real; razn2 : array[0..1,0..100] of real;
- а? Это что, специальная защита от переприсваиваний? Почему не так:
var mas1,mas2, peres,razn1,razn2 : array[0..1,0..100] of real;
Есть на то причина?
Немного поясню: я бы не встрял, но тут такие дела.. Решил я убрать под спойлеры программные тексты, чтоб тема была читабельнее. Убрал - фигак, пост пропал совсем. Чисто, как попка младенца. Стал разбираться.. и разбирался больше часа в общей сложности. Сначала выяснил, что форумскому софту не нравится большое количество квадратных скобок. Потом обнаружились другие подробности.. Короче, в результате все поправилось переделкой верхней цитаты в старинный эпистолярный жанр )). Я извиняюсь за это, позже попробую исправить этот баг. Но в процессе экспериментов по поиску причины я и обратил внимание на ту деталь, к которой теперь в свою очередь привлекаю внимание автора темы..
--------------------
я - ветер, я северный холодный ветер я час расставанья, я год возвращенья домой