Кто знает где можно достать алгоритм объединения отрезков ответьте или [email protected]
Задача такая: дано n пар чисел - координаты начала и конца отрезка. Надо обединить все отрезки и результат представить как k новых пар.
Если у кого-нить есть что-то подобное, плз, киньте на мыло или ссылку дайте. Буду очень благодарен.

А можно условие задачи по-подробнее?

Цитата(mr @ 5.12.2004, 16:57)

дано n пар чисел - координаты начала и конца отрезка.

Здесь не корректно написано, координаты не могут задаватся как N пар чиел, обычно 2-мя, если 2-ух мерном пространстве, или 3-мя если в 3-ёх мерном пространстве...

Цитата(Zero @ 5.12.2004, 17:53)

Здесь не корректно написано, координаты не могут задаватся как N пар чиел, обычно 2-мя, если 2-ух мерном пространстве, или 3-мя если в 3-ёх мерном пространстве...

Нет, тут координнаты начал и концов отрезков. Отрезки - на прямой. Т. е. если, скажем, есть три пары типа
1 5
4 6
8 9
то надо объединить отрезки [1;5]U[4;6]U[8;9]
результатом будут отрезки [1;6]U[8;9]
и пары чисе
1 6
8 9
Пробовал задать все исходные отрезки как массив записей с целыми полями координат начала и конца, но не могу написать код для получения нового массива с объединенными отрезками.
Вот в этом и вся сложность задачи.

А-а-а-а-а-а-а.... Так бы сразу и сказал, а я то уж подумал чё-то сложное в n-мерном пространстве, а окозалось всё легко...

Код

Program Kurs; Const     max=100;     n=2; var   b:array[1..255] of byte;   a,d:array[1..max,1..n] of byte;   z:set of byte;   m,i,j,c,k,e:integer; Begin   write('Введите кол-во пар отрезков=');   readln(m);   writeln('Ввод отрезков:');   for i:=1 to m do     for j:=1 to n do       begin         write('a[',i,',',j,']=');         readln(a[i,j]);       end;   for i:=1 to m do     z:=z+[a[i,1]..a[i,2]];   i:=0; j:=1; k:=0;   repeat     if i in z then       begin         b[j]:=i;         j:=j+1;         k:=k+1;       end;     i:=i+1;   until i=256;   i:=1;j:=1; c:=1; e:=0;   repeat     repeat       d[i,j]:=b[c];       c:=c+1;       j:=2;     until (b[c]<>b[c-1]+1) or (c=k+1);     if d[i,2]<d[i,1] then d[i,2]:=d[i,1];     e:=e+1;     i:=i+1;     j:=1;   until c=k+1;   writeln;   for i:=1 to e do     begin       write(i,'─ый отрезок имеет координаты:');       writeln('[',d[i,1],',',d[i,2],']');     end; End.

Здесь вначале введёш кол-во отрезков, потом первую координату по оси ОХ, а потом вторую, и т.д.
Но к сожалению прога имеет недостаток ─ числа из предела 0..255 , а в остальном работает без сбоев

Это сообщение отредактировал(а) Zero - 5.12.2004, 20:12

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

Боюсь, рано я радовался.
Прогрмма отличная и работает, но только сеня утром узнал от знакомого об одном маленьком, но очень противном требовании курсовой.
Стандартный тип Set Паскаля использовать совсем запрещено, можно лишь массивы или линейные списки.
Ладно, бум думать, еще время до пятницы есть...

Смог переделать программу без использования множества z.
Просто загоняю все введенные элементы в массив b, потом всем повторяющимся элементам присваиваю 100 и сортирую по возрастанию. Все сотые элементы остаются в конце и кодом

Код

i:=0; repeat  inc(i); until (i>k) and (b[i]=100 k:=i;

);
узнаю реальную мощность получившегося множеста загнаного в массив b. Потом при выводе просто даю указание не выводить отрезки типа [100;x] и [x;100]. Все хорошо НО!!!

Цитата(Zero @ 5.12.2004, 20:11)

а в остальном работает без сбоев

Да нет, один сбой все же есть. При вводе отрезков вроде
1 2
3 4
т. е. когда границы соседних отрезков отличаются на 1, прога вместо положенных
1 2
3 4
выдает
1 4.
И как тут быть? Может кто знает? Помогите!

Цитата(mr @ 6.12.2004, 11:11)

И как тут быть? Может кто знает? Помогите!

Раноя я тебе похоже дал ссылку в письме, не посмотрев здесь , результат абсолютно верный выдаётся, можеш об этом больше и не думать.
А на счёт, множества... раз нельзя исп. стандартный тип, то можеш исп. обычные, заменяюцие множество... Я не совсем понял чё ты там наделал, но ты можеш заполнять массив B (в той проге которую писал я), так: Короче с исп. цикла, проверяеш каждый елемент массива,и если текущий записываемый элемент не находится в массиве, то записываеш его туда, и т.д., тогда ты сможеш убрать привязанность к промежутку [0..255], а выставиш сам какой захочеш, правда чем он будет больше тем прога будет работать медленнее...

Это сообщение отредактировал(а) Zero - 6.12.2004, 19:43

Хотя ладно, я тоже не люблю когда мне не понятно скажут что как делать, а код не представят, поэтому представляю тебе "модифицированый метод Zero, объединения отрезков"

Код

Program Kurs; Const     max=100;     n=2;     Nmax=255;  {max кол-во элэментов в массиве} var   b:array[1..Nmax] of integer;   a,d:array[1..max,1..n] of integer;   m,i,j,c,k,e,x:integer;   have:boolean; Begin   write('Введите кол-во пар отрезков=');   readln(m);   if m<=0 then exit;   writeln('Ввод отрезков:');   for i:=1 to m do     for j:=1 to n do       begin         write('a[',i,',',j,']=');         readln(a[i,j]);       end;   for i:=1 to Nmax do b[i]:=-32768;   {Создание искусственного множества}   e:=0;   for i:=1 to m do     begin       for j:=a[i,1] to a[i,2] do         begin           have:=false;           for k:=0 to 255 do if j=b[k] then have:=true;           if not(have) then             begin               e:=e+1;               b[e]:=j;             end;         end;     end;   {Сортировка множества}   i:=1;   j:=e;   repeat     if b[i]<b[j] then j:=j-1       else         begin           if i=j then begin i:=i+1; j:=e end;           x:=b[i];           b[i]:=b[j];           b[j]:=x;         end;   until i=e;   i:=1; j:=1; c:=1; k:=e; e:=0;   repeat     repeat       d[i,j]:=b[c];       c:=c+1;       j:=2;     until (b[c]<>b[c-1]+1) or (c=k+1);     if d[i,2]<d[i,1] then d[i,2]:=d[i,1];     i:=i+1;     e:=e+1;     j:=1;   until c=k+1;   writeln;   for i:=1 to e do     begin       write(i,'─ый отрезок имеет координаты:');       writeln('[',d[i,1],',',d[i,2],']');     end; End.

Здесь не используется тип Set of (множественный тип), и ещё промежуток не [0..255], а какой ты сам поставиш, единственный, теперь недостаток ─ это медленне работать стала