Две строки матрицы назовем похожими, если совпадают множества чисел, встречающихся в этих строках. Найти количество строк в максимальном множестве попарно непохожих строк заданной матрицы.
Очень срочно надо решение, а я сам не могу даже врубиться в условие этой задачки
klem4
28.12.2005 19:15
1, 2, 3, 4, 5
и
2, 4, 5, 3, 1
похожи - (и там и там одни и теже числа, порядок не важен)
gepard
28.12.2005 21:43
Цитата(klem4 @ 28.12.2005 14:15)
1, 2, 3, 4, 5
и
2, 4, 5, 3, 1
похожи - (и там и там одни и теже числа, порядок не важен)
Да это я понял, а вот как сделать эту задачу?.. Просто как надо перебрать эти все строки?
klem4
28.12.2005 22:18
Вот напирмер ф-я возвращает 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;
volvo
29.12.2005 1:11
klem4, не все так просто:
const n=5; type TMatrix = array[1..n,1..n] of integer;
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);