bool Transitivity()
{
bool status = false;
// производим умножение матрицы на саму себя
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
f1[j] = 0;
for(int k = 0; k < n; k++)
{
f1[j]=d[k] * d[k][j];
//если число отличное от 0 пишем 1
if(f1[j] > 0) f1[j] = 1;
}
}
}
// определяем транзитивность отношения
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
if(d[j] == 1 && d[j][k] == 1 && d[k] == 1)status = true;
return status;
}
Транзитивное отношение по бинарной матрице
Здравствуйте. Подскажите пожалуйста как по бинарной матрице отношения определить свойство транзитивности. пишу след код но работает не на всех парах отношений... может гдя ошибся.? В заранее спаибо.
вот код.
вот код.
Код:
А зачем ты умножаешь матрицу на себя(к тому же неправильно), а затем не пользуешься результатом этого?
извиняюсь неправильно написал,,,просто скопировал код со старого исходника)))
Код:
bool Transitivity()
{
bool status = false;
// производим умножение матрицы на саму себя
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
f1[j] = 0;
for(int k = 0; k < n; k++)
{
f1[j]+=d[k] * d[k][j]; //я так понял здесь ошибка была.
//если число отличное от 0 пишем 1
if(f1[j] > 0) f1[j] = 1;
}
}
}
// определяем транзитивность отношения
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
if(f1[j] == 1 && f1[j][k] == 1 && f1[k] == 1)status = true;
return status;
}
{
bool status = false;
// производим умножение матрицы на саму себя
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
f1[j] = 0;
for(int k = 0; k < n; k++)
{
f1[j]+=d[k] * d[k][j]; //я так понял здесь ошибка была.
//если число отличное от 0 пишем 1
if(f1[j] > 0) f1[j] = 1;
}
}
}
// определяем транзитивность отношения
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
if(f1[j] == 1 && f1[j][k] == 1 && f1[k] == 1)status = true;
return status;
}
Во-первых, неплохо бы вынести if(f1[j] > 0) f1[j] = 1; за пределы цикла по k, ведь внутри него элемент посчитан не полностью. Во-вторых, зачем сравнивать с единицей по три раза, когда достаточно одного?
это я исправил ...но все равно не работает...например задаю множество a,b,c. и пары ab bc и ac . по идеи отношение транзитивно. а мне выдает что нет. может ошибка где то в самом алгоритме?
у тебя ошибка в проверке.
http://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B0%D0%BD%D0%B7%D0%B8%D1%82%D0%B8%D0%B2%D0%BD%D0%BE%D1%81%D1%82%D1%8C
http://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B0%D0%BD%D0%B7%D0%B8%D1%82%D0%B8%D0%B2%D0%BD%D0%BE%D1%81%D1%82%D1%8C
Цитата: paska
извиняюсь неправильно написал,,,просто скопировал код со старого исходника)))
Код:
bool Transitivity()
{
bool status = false;
// производим умножение матрицы на саму себя
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
f1[j] = 0;
for(int k = 0; k < n; k++)
{
f1[j]+=d[k] * d[k][j];
//если число отличное от 0 пишем 1
if(f1[j] > 0) f1[j] = 1;
}
}
}
// определяем транзитивность отношения
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
if( f1[COLOR="Red"][j][/COLOR] == 1 && f1[j][k] == 1 && f1[k] == 1) status = true;
// вот так должно бить
if( f1[COLOR="Red"][j][/COLOR] == 1 && f1[j][k] == 1 && f1[k] == 1) status = true;
return status;
}
{
bool status = false;
// производим умножение матрицы на саму себя
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
f1[j] = 0;
for(int k = 0; k < n; k++)
{
f1[j]+=d[k] * d[k][j];
//если число отличное от 0 пишем 1
if(f1[j] > 0) f1[j] = 1;
}
}
}
// определяем транзитивность отношения
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < n; k++)
if( f1[COLOR="Red"][j][/COLOR] == 1 && f1[j][k] == 1 && f1[k] == 1) status = true;
// вот так должно бить
if( f1[COLOR="Red"][j][/COLOR] == 1 && f1[j][k] == 1 && f1[k] == 1) status = true;
return status;
}
вот мой рабочий код
Код:
function Tranzetivne(a: TMatrix; row :integer; col: integer):boolean;
var
i,j,k,k1 : integer;
begin
k1 := 0 ;
Result := False;
for i := 0 to row-1 do begin
for j := 0 to col-1 do begin
k1 := k1 + a[i,j];
if i <> j then
for k := 0 to col-1 do
if (i <> k) and (j <> k) then
if ((a[i,j] = a[j,k]) and (a[j,k] = a[i,k]) and (a[i,k] = 1))then
Result := True
else if ((a[i,j] = a[j,k]) and (a[j,k] = 1) and (a[i,k] = 0)) then begin
Result := False;
break;
end;
end;
end;
if k1 = 1 then Result := True;
end;
var
i,j,k,k1 : integer;
begin
k1 := 0 ;
Result := False;
for i := 0 to row-1 do begin
for j := 0 to col-1 do begin
k1 := k1 + a[i,j];
if i <> j then
for k := 0 to col-1 do
if (i <> k) and (j <> k) then
if ((a[i,j] = a[j,k]) and (a[j,k] = a[i,k]) and (a[i,k] = 1))then
Result := True
else if ((a[i,j] = a[j,k]) and (a[j,k] = 1) and (a[i,k] = 0)) then begin
Result := False;
break;
end;
end;
end;
if k1 = 1 then Result := True;
end;