Алгоритм, дискретная математика, матрица отношений

[[TrusT]]

Прошу помочь с алгоритмом для нахождения решения: матрица отношений (только 0 и 1) транзитивна или нет.
Лабораторная по дискретной математике.
Пишу программу на КУМИРе (аналог Паскаля), поэтому я с логическими переменными не очень... эээ... дружу.
У меня самой уже шарики за ролики заехали(
вот мой пример алгоритма:
s:=0
цел h=0,j,k1=0
нц для i от 1 до n
*нц для k от 1 до n
**нц для j от 1 до n
***если (A[i,k]=1)
****то если (A[i,k]=A[k,j])
*****то если (A[k,j]=A[i,j])
******то h:=h+1
*****иначе s:=s+1
*****все
****все
***все
**кц
*кц
кц
если (h<>0)
то вывод "транзитивна."
все
если (s<>0)
то вывод "антитранзитивна."
все

запись создана: 08.03.2011 в 21:47

@темы: Вопрос, Алгоритм

Comments

[Слушатель]

[TrusT]
Вот набросок:

Изначально задать значение f = 1
Если во время цикла, найдутся i, j, k, которые не выполняют условие транзитивности - сбросить f на 0.
После завершения цикла - проверить f.

Обратите внимание, что если (i, k) = 0 и/или (k, j) = 0 то отношение транзитивно. Т.е. для того чтобы транзитивность не выполнялась нужно чтобы выполнилось (i, k) = 1 и (k, j) = 1 но не выполнилось следствие т.е. (i, j) = 0