ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Serg Belyaev                         2:5015/166.7   13 Oct 2002  18:12:27
 To : Alexander Pashchenko
 Subject : Алгоритм
 -------------------------------------------------------------------------------- 
 

 07-Oct-02 10:42:46, Alexander Pashchenko wrote to All
           Subject: Алгоритм
 
  AP> Задали тут задачку:
  AP>
  AP> Дан массив A[m,n] Известно, что среди его эл-тов
  AP> всего 2 равны между собой. Hапечатать их индесксы.
  AP>
  AP> Как ее правильно решить.
  AP>
  AP> Я так думаю, что надо проходить по матрице и сравнивать текущий элемент с
  AP> запомненным, исключая сам запомненный. И если они равны вывести индексы.
  AP> Hо вот тут-то я и запутался.
 
 Решение достаточно простое - после сортировки идет
 сравнение соседних пар, - об этом уже писали здесь.
 Hо, как обычно бывает, многие умудряются путаться в
 реализации (я тоже не безгрешен). Один из вариантов
 реализации приведен ниже - используется быстрая
 сортировка. Логически она очень прозрачна и проста
 для запоминания, но начинающие программисты часто
 относятся к ней как к "священной корове".
 Как работать с индексами и не трогать основной
 массив? Очень просто.
 Сортировка позволяет найти все повторы, а не только
 2-х элементов - создается ощущение, что для данной
 конкретной задачи можно найти более простой алгоритм.
 Hиже сделана попытка использовать специфику задачи,
 но, надо признать, что это больше похоже на самообман -
 никакого выигрыша в быстродействии эти "выкрутасы"
 не дают. Однако этого не следует бояться, надо же
 на чем-то тренироваться - использование пакетных
 процедур можно рекомендовать только профессионалам,
 но никак не начинающим.
 ---------------------cut-------------------
 const m=51;n=117;
 
 type ind=record x,y:word end;
 
 var  A:array[1..m,1..n] of integer;
      I:array[1..m*n] of ind;
      r:ind;
      k,l:word;
 
 procedure stop(i1,i2:word);
 begin
   if i1=i2 then exit;
   writeln('A(',I[i1].x,',',I[i1].y,')=A(',I[i2].x,',',I[i2].y,')');
   halt
 end;
 
 procedure sort(i1,i2:word);
 var AM:integer;k,ia,ib:word;
 begin
   if i1>=i2 then exit;
   ia:=i1;ib:=i2;k:=i1+random(i2-i1+1);AM:=A[I[k].x,I[k].y];
   if A[I[i1].x,I[i1].y]=AM then stop(i1,k);
   if A[I[i2].x,I[i2].y]=AM then stop(k,i2);
   repeat
     while A[I[i1].x,I[i1].y]<AM do inc(i1);
     while A[I[i2].x,I[i2].y]>AM do dec(i2);
     if i2>=i1 then begin
       r:=I[i1];I[i1]:=I[i2];I[i2]:=r;
       inc(i1);dec(i2)
     end;
   until i1>i2;
   sort(ia,i2);sort(i1,ib);
 end;
 
 begin
   for k:=0 to m-1 do for l:=1 to n do begin
     I[k*n+l].x:=k+1;I[k*n+l].y:=l end;
   for k:=1 to m do for l:=1 to n do A[k,l]:=-(n*k+l);
   A[1,20]:=A[5,17];
   sort(1,m*n);
 end.
 ---------------------cut-------------------
  Всего доброго,
  <SVB> (Serg Belyaev)
 --- Terminate 5.00/Pro
  * Origin: (svb@sandy.ru) or (2:5015/166.7)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Алгоритм   Alexander Pashchenko   07 Oct 2002 11:42:46   Алгоритм   Alexander Chelmodeev   08 Oct 2002 00:01:30   Re: Алгоритм   Victor Pogolsha   08 Oct 2002 12:03:07   Алгоритм   Alexander Chelmodeev   09 Oct 2002 09:24:29   Алгоритм   Andrew Plyako   08 Oct 2002 00:59:08   Re: Алгоритм   Sergey Andrianov   08 Oct 2002 16:48:54   Алгоритм   Ianos Gnatiuc   08 Oct 2002 23:35:51   Re: Алгоритм   Michael Sedov   09 Oct 2002 19:36:29   Алгоритм   Serg Belyaev   13 Oct 2002 18:12:27