Алгоритм

From

Serg Belyaev (2:5015/166.7)

To

Alexander Pashchenko

Date

2002-10-13T18:12:27Z

Area

RU.ALGORITHMS

Привет, Alexander.

07-Oct-02 10:42:46, Alexander Pashchenko wrote to All
          Subject: Алгоритм

 AP> Задали тут задачку:
 AP>
 AP> Дан массив A[m,n] Известно, что среди его эл-тов
 AP> всего 2 равны между собой. Напечатать их индесксы.
 AP>
 AP> Как ее правильно решить.
 AP>
 AP> Я так думаю, что надо проходить по матрице и сравнивать текущий элемент с
 AP> запомненным, исключая сам запомненный. И если они равны вывести индексы.
 AP> Но вот тут-то я и запутался.

Решение достаточно простое - после сортировки идет
сравнение соседних пар, - об этом уже писали здесь.
Но, как обычно бывает, многие умудряются путаться в
реализации (я тоже не безгрешен). Один из вариантов
реализации приведен ниже - используется быстрая
сортировка. Логически она очень прозрачна и проста
для запоминания, но начинающие программисты часто
относятся к ней как к "священной корове".
Как работать с индексами и не трогать основной
массив? Очень просто.
Сортировка позволяет найти все повторы, а не только
2-х элементов - создается ощущение, что для данной
конкретной задачи можно найти более простой алгоритм.
Ниже сделана попытка использовать специфику задачи,
но, надо признать, что это больше похоже на самообман -
никакого выигрыша в быстродействии эти "выкрутасы"
не дают. Однако этого не следует бояться, надо же
на чем-то тренироваться - использование пакетных
процедур можно рекомендовать только профессионалам,
но никак не начинающим.
---------------------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)