Версия для печати темы

Автор: klem4 31.10.2005 23:07

Давно : n<=50, x[1..n] - n/2 отрезков на числовой оси (x1..x2, x3..x4, ..., xn-1.. xn), определить, имеют ли они все общие точки ... вот решил, но может кто покороче(читай побыстрее) предложит ? :confused:

program _611A;
uses crt;
type
   TArr = array[1..50] of integer;
var
   A : TArr;
   n : byte;

procedure FillArray(var x : TArr; size : byte);
var
   i : byte;
begin
   for i := 1 to size do begin
      write('x[',i,']=');
      readln(x[i]);
   end;

   writeln;

end;

function IsIncluds(x : TArr; size : byte) : boolean;
var
   i,j,k : integer;
   include : boolean;
begin

   include := true;

   i := 1;

   while (i<=n-3)and(include) do begin

      include := false;

      j := x[i];

      while (j<=x[i+1]) and not(include) do begin

         k := x[i+2];
         while (k<=x[i+3]) and not(include) do
          if j=k then inc(include)
           else inc(k);

         inc(j);

      end;
      inc(i,2);
   end;

   IsIncluds := include;

end;

begin

   clrscr;

   repeat

      write('n='); readln(n);

      if odd(n) then begin
         writeln('N doljno bit" chetnim !');
         delay(2000);
         clrscr;
      end;

   until not(odd(n));

   FillArray(A, n);

   writeln(IsIncluds(A, n));

   readln;
end.

Автор: volvo 31.10.2005 23:18

To: klem4
Поиск для кого?
http://forum.pascal.net.ru/index.php?showtopic=6528&view=findpost&p=48349 Если это не оно самое, то ОЧЕНЬ похожее...

Автор: klem4 31.10.2005 23:34

Спасибо, посмотрю :smile:

Автор: dummy 1.11.2005 2:35

Можно просто найти максимум всех чисел, являющихся координатами левых концов отрезков, минимум всех чисел, являющихся координатами правых концов, а потом сравнить получившиеся числа. Если максимум левых окажется больше минимума правых, то общих точек у них нет!

Автор: volvo 1.11.2005 3:33

dummy, что же ты это не сделал, когда от тебя это требовалось, ведь это "так просто" !!!

А тот алгоритм, на который я привел ссылку, кстати, в случае ненахождения общих точек будет работать гораздо быстрее тупого перебора, т.к. чтобы найти максимум/минимум в массиве, ты должен перебрать ВСЕ его элементы, а если второй отрезок даст отрицательный результат, то остальные 48 ты будешь перебирать просто так.