Форум «Всё о Паскале» > Пересечение множества точек.

Помощь - Поиск - Пользователи - Календарь

Полная версия: Пересечение множества точек.

Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи

Krjuger

27.05.2011 19:59

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


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

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

IUnknown

27.05.2011 21:33

Цитата

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

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

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

Krjuger

27.05.2011 22:16

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

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

)

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


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.

IUnknown

27.05.2011 22:39

Цитата

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

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

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

-TarasBer-

27.05.2011 23:08

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

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

Krjuger

28.05.2011 0:05

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

IUnknown

28.05.2011 0:49

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

Krjuger

28.05.2011 2:12

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

IUnknown

28.05.2011 3:56

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

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

Lapp

28.05.2011 5:58

Я извиняюсь за вторжение и одновременно за флуд..
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;

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

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

Krjuger

28.05.2011 17:20

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

Цитата

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

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

Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.