Пересечение множества точек. Опции

[Krjuger]

Собственно задача такая.
Дано 2 множества точек.Найти пересечение и разность этих множеств.
Собственно вопрос возник, как задать эти множества.У меня множесто точек ассоциируется с координатами точки.
И выглядеть дожно как то.

type
 TMnoz= set of 0..100;
   TToch=array[0..1] of TMoz;

Тут TToch это координаты х и у, а значение- множества, составленные из чисел от 1 до 100.Кстати следующий вопрос.Числа могут быть только целые или нет?

[IUnknown]

И выглядеть дожно как то.

Это именно задано, или это твое предположение? Нет, в принципе никаких проблем, можно реализовать аналог "множества из записей", можно - массив множеств, как у тебя (хоть это и бессмысленно - ты не сможешь определить в таком массиве, где чья координата: будут отдельно упорядочены абсциссы, а отдельно - ординаты, все перемешается напрочь).

Однако, у меня "множество точек" ассоциируется только с массивом записей, каждая из которых хранит координаты одной точки (или просто с двумерным массивом).

[Krjuger]

> Это именно задано, или это твое предположение?

Это сугубо мое предположение.Я понял недостаток такого варианта,а жаль.
Пока что наваял следующее.(к несчастью именно наваял )

код (Показать/Скрыть)

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.

Сообщение отредактировано: Lapp - 28.05.2011 5:25

[IUnknown]

последний readln банально игнорируется,возможно из-за dos boxa.

DosBox ни при чем. Измени в коде ВСЕ read на ReadLn - не будет игнорироваться. Об этом уже столько раз написано мной на форуме - я со счета сбился...

Хм... По поводу твоего кода: будешь оставлять так, или посмотришь, как в подобных случаях рекомендует поступать господин Ульман (вместе с Ахо и Хопкрофтом)? У него есть реализация множества на деревьях.

[-TarasBer-]

> или посмотришь, как в подобных случаях рекомендует поступать господин Ульман (вместе с Ахо и Хопкрофтом)? У него есть реализация множества на деревьях.

Кстати, как у них сделано, мне тоже интересно. Потому что я бы оптимизировал перебор (поиск совпадений) при помощи хеширования, а как делать это деревом - не знаю.

[Krjuger]

Я бы взглянул,потому что у меня оптимизации просто ноль.Но сам я врятли смогу,у меня с деревьями дела весьма плохи.Книжку глянул,чето я даже идеи оптимизации не совсем понял.

Сообщение отредактировано: Krjuger - 28.05.2011 0:12

[IUnknown]

Ну, у них там много разных реализаций на самом деле - и с обычными двоичными деревьями (Krjuger, это есть у меня на сайте, можешь посмотреть), и с нагруженными деревьями, и со сбалансированными деревьями. Целая глава этому посвящена. Я ж не буду всю главу перепечатывать. Если кому надо - говорите куда выслать (там 4Мб), или сами найдите эту книжку, она есть на Инфанате, например, если ссылка еще не умерла.

[Krjuger]

Ну книгу я скачал и мельком просмотрел,с первого раза осмыслению оно не поддалось.

[IUnknown]

Значит, читай второй раз, третий, и так далее...

Ну, смотри: открой книгу на стр 112, и посмотри на приведенную там процедуру Intersection... Она тебе найдет "пересечение" связанных списков. Если ты все свои данные запихаешь в два списка (хочешь - сразу поддерживая упорядоченность, вставляя элементы куда нужно, о чем говорят авторы, хочешь - потом пробежать и отсортировать - дело 5 строк кода), а потом применишь эту процедуру - то получишь те точки, которые присутствуют и в первом и во втором списках. Как сделать Difference - там же написано, на 113 странице. Эта программа уже будет гораздо лучше, чем то, что есть у тебя сейчас.

[Lapp]

Я извиняюсь за вторжение и одновременно за флуд..
Krjuger, можно вопросик? ))
Мы, конечно, люди темные, университетов не кончали (С).. Но объясни мне, темному человеку - какую цель ты преследовал вот этим:

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;

Есть на то причина?

Немного поясню: я бы не встрял, но тут такие дела..
Решил я убрать под спойлеры программные тексты, чтоб тема была читабельнее. Убрал - фигак, пост пропал совсем. Чисто, как попка младенца. Стал разбираться.. и разбирался больше часа в общей сложности. Сначала выяснил, что форумскому софту не нравится большое количество квадратных скобок. Потом обнаружились другие подробности.. Короче, в результате все поправилось переделкой верхней цитаты в старинный эпистолярный жанр )). Я извиняюсь за это, позже попробую исправить этот баг. Но в процессе экспериментов по поиску причины я и обратил внимание на ту деталь, к которой теперь в свою очередь привлекаю внимание автора темы..

[Krjuger]

А это,чтобы вы могли исправить ошибки форумского софта......О как завернул.

Мы, конечно, люди темные, университетов не кончали

Ну мы пока что люди ничуть не светлые,самим еще долго до просветления.