Похожие строки в матрицах, Попробуйте, поймите или... решите Опции

[gepard]

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

Очень срочно надо решение, а я сам не могу даже врубиться в условие этой задачки

[klem4]

1, 2, 3, 4, 5

и

2, 4, 5, 3, 1

похожи - (и там и там одни и теже числа, порядок не важен)

[gepard]

1, 2, 3, 4, 5

и

2, 4, 5, 3, 1

похожи - (и там и там одни и теже числа, порядок не важен)

Да это я понял, а вот как сделать эту задачу?.. Просто как надо перебрать эти все строки?

[klem4]

Вот напирмер ф-я возвращает true, если 2 троки (i1 и i2 матрицы) похожи

const
   n=3;
type
   TMatrix = array[1..n,1..n] of integer;

function IsSimilar(mx : TMatrix; i1,i2 : byte) : boolean;
var
   j1,j2 : byte;
   find : boolean;
begin

   find := true;

   j1 := 1;
   while(j1 <= n) and find do begin
      j2 := 1;
      find := not(find);
      while (j2 <= n) and (not(find)) do
       if mx[i1,j1] = mx[i2,j2] then find := true
        else inc(j2);
      inc(j1);
   end;

   IsSimilar := find;
end;

Сообщение отредактировано: klem4 - 28.12.2005 18:20

[volvo]

klem4, не все так просто:

const
   n=5;
type
   TMatrix = array[1..n,1..n] of integer;

{ Здесь - твоя функция IsSimilar }

const
  a: tmatrix =
  (
    (1, 1, 3, 4, 5),
    (2, 3, 4, 5, 1),
    (1, 3, 3, 4, 5),
    (5, 4, 3, 2, 1),
    (5, 4, 2, 3, 1)
  );

begin
  writeln(IsSimilar(a, 1, 2)); { Как ты думаешь, какой должен быть ответ? }
end.

Со своей стороны могу предложить такой вариант:

const
   n=5;
type
   TVector = array[1 .. n] of integer;
   TMatrix = array[1 .. n] of TVector;

function IsSimilar(mx : TMatrix; i1,i2 : byte) : boolean;

  procedure sort(var v: TVector);
  var i, j, T: integer;
  begin
    for i := 1 To n Do
      for j := n downto i + 1 do
        if v[pred(j)] > v[j] then begin
          T := v[pred(j)]; v[pred(j)] := v[j]; v[j] := T
          end
  end;

var
  i: integer;
begin
  sort(mx[i1]); sort(mx[i2]);
  i := 1;
  while (i <= n) and (mx[i1][i] = mx[i2][i]) do inc(i);

  IsSimilar := (i > n);
end;

const
  a: tmatrix =
  (
    (1, 1, 3, 4, 5),
    (2, 3, 4, 5, 1),
    (1, 3, 3, 4, 5),
    (5, 4, 3, 2, 1),
    (5, 4, 2, 3, 1)
  );

begin
  writeln(issimilar(a, 1, 2));
end.

[gepard]

Спасибо большое, действительно помогли. Не думал даже, что этот форум такой классный. Вообщем, не забуду!:)