ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Dmitriy Krylov                       2:5020/400     09 Oct 2002  05:37:58
 To : Alexander Pashchenko
 Subject : Re: Алгоритм
 -------------------------------------------------------------------------------- 
 

 Привет, Alexander!
 Вы писали to All on Mon, 07 Oct 2002 10:42:46 +0400:
 
  AP> Задали тут задачку:
 
  AP> Дан массив A[m,n] Известно, что среди его эл-тов всего 2 равны между
  AP> собой. Hапечатать их индесксы.
 
  AP> Как ее правильно решить.
 
  AP> Я так думаю, что надо проходить по матрице и сравнивать текущий
  AP> элемент с запомненным, исключая сам запомненный. И если они равны
  AP> вывести индексы.
  AP> Hо вот тут-то я и запутался.
 
 Hу, если есть память, то можно сделать сделать бинарное дерево, в котором
 разместить элементы и соответствующие индексы в порядке прохождения массива.
 
 Hапример, так:
 
 type
   PInedx = ^TIndex;
   TIndex = record   // Координаты в матрице
     X, Y: integer;
   end;
 
   PBinaryTree = ^TBinaryTree;
   TBinaryTree = record
     El: TElem; // А TElem - это тип элементов
     Index: TIndex;
     Left: PBinaryTree;   // Слева - меньшие элементы
     Right: PBinaryTree;  // Справа - большие
   end;
 
 var
   Root: PBinaryTree; // Корень дерева;
 
 // <- Tree - поддерево, в которое помещается элемент
 // <- El - помещаемый элемент
 // <- Index - индекс
 
 // -> результат размещения:
 
 //    nil - элемента в дерева не было, элемент помещен
 //    <>nil - элемент уже есть, результат - ссылка на индекс
 function Add(ATree: PBinaryTree; AEl: TElem; AIndex: TIndex): PIndex;
 
   function CreateTree(AEl: TElem; AIndex: TIndex): PTree;
   begin
     New(Result);
     with Result^ do
     begin
       Left := nil;
       Right := nil;
       Index := AIndex;
       El := AEl;
     end;
   end;
 
 begin
   // Дерево еще не создано, создаем его
   if Root = nil then
   begin
     Root := CreateTree(AEl, AIndex);
     Result := nil;
   end
   else
   begin
     // Дерево уже создано, поиск элемента в нем...
     if AEl = ATree^.El then
     begin
       // Hашли повторяющийся элемент
       Result = @(ATree^.Index);
     end
     // Иначе размещаем в поддеревьях
     else if El > ATree^.El then
     begin
       // Проходим а правое поддерево
       if ATree^.Right = nil then
       begin
         // Поддерева нет, создаем
         ATree^.Right := CreateTree(AEl, AIndex)
         Result := nil;
       end
       else
         // Поддерево есть - проходим
         Result := Add(ATree^.Right, AEl, AIndex);
     end
     else
     begin
       // Проходим в левое поддерево
       if ATree^.Left = nil then
       begin
         // Поддерева нет, создаем
         ATree^.Left := CreateTree(AEl, AIndex)
         Result := nil;
       end
       else
         // Поддерево есть - проходим
         Result := Add(ATree^.Left, AEl, AIndex);
     end;
   end;
 end;
 
 function MakeIndex(AX, AY: integer): TIndex;
 begin
   Result.X := AX;
   Result.Y := AY;
 end;
 
 // А теперь обход матрицы
 var
   I: PIndex; // Индекс найденного элемента
   i, j, fi, fj: integer;
 begin
   Root := nil;
   I := nil;
   for i := 1 to MaxX do
     if I <> nil then
       Break
     else
       for j := 1 to MaxY do
       begin
         I := Add(Root, Matrix[i, j], MakeIndex(i, j));
         if I <> nil then
         begin
           fi := i; fj := j; // Сохранение индексов
           Break;
         end;
       end;
 
   if I <> nil then
   begin
     // Распечатка
     WriteLn('Первое вхождение:', I^.X, ' ', I^.Y);
     WriteLn('Второе вхождение:', fi, fj);
     WriteLn('Элемент:', Matrix[fi, fj]);
   end
   else
   begin
     WriteLn('Совпадений не найдено');
   end;
 
   // Уничтожение дерева...
 end;
 
 -----------------------
 
 Вот. А еще, если элементы из маленького множества (TElem = byte), то
 вообще - песня:
 размещай пройденные элементы в множестве (set), и всё... Можно сделать и для
 больших элементов, но тогда придется делать большое бинарное множество.
 
 ----------------------
 
 В случае деревьев сложность будет в худшем случае O((MaxX * MaxY) ^ 2) (если
 дерево не балансировать), а в среднем O((MaxX * MaxY) * log(MaxX * MaxY)).
 
 Если дерево еще и балансировать, то будет O((MaxX * MaxY) * log(MaxX * MaxY)
 ^ 2). В C++ STL в классе set<> балансировка включена, так что, если
 программируешь на C++, используй этот класс.
 
 В случае, если удастся разместить элементы в бинарном множестве, сложность
 будет O(MaxX * MaxY) (т.е. линейно по отношению к размеру матрицы).
 
 Удачи!
 __________________________________________________
 --{ Dmitriy Krylov aka "Abulafia"   }-------------
 --{ mailto: krylov@mail.primorye.ru }-------------
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

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