Re: Алгоритм

From

Dmitriy Krylov ()

To

Alexander Pashchenko

Date

2002-10-09T05:37:58Z

Area

RU.ALGORITHMS

From: "Dmitriy Krylov" <krylov@mail.primorye.ru>

Привет, Alexander!
Вы писали to All on Mon, 07 Oct 2002 10:42:46 +0400:

 AP> Задали тут задачку:

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

 AP> Как ее правильно решить.

 AP> Я так думаю, что надо проходить по матрице и сравнивать текущий
 AP> элемент с запомненным, исключая сам запомненный. И если они равны
 AP> вывести индексы.
 AP> Но вот тут-то я и запутался.

Ну, если есть память, то можно сделать сделать бинарное дерево, в котором
разместить элементы и соответствующие индексы в порядке прохождения массива.

Например, так:

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
      // Нашли повторяющийся элемент
      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)