Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: 6323
Последний выпуск: 19.06.2015

Проверка бинарного отношения на транзитивность. Правильно ли условие?

79K
12 февраля 2012 года
lnxdx
4 / / 12.02.2012
Проверка на транзитивность бинарного отношения.
Получена матрица А*А.
Далее выполняется условие проверки матрицы на транзитивность. Правильно ли оно?

 
Код:
status := True;
for i := 1 to size do
      for j := 1 to size do
        for k := 1 to size do
          if (tr[i,j] <> 1) and (tr[j,k] <> 1) and (tr[i,k] <> 1) then status := False;
316
12 февраля 2012 года
Alm3n
889 / / 29.05.2009
И спрашивал бы в том топике, зачем ещё один создавать, тем более так вырывать код из программы. Не понятно же, о чём он.
79K
12 февраля 2012 года
lnxdx
4 / / 12.02.2012
Цитата: Alm3n
И спрашивал бы в том топике, зачем ещё один создавать, тем более так вырывать код из программы. Не понятно же, о чём он.



Я пояснил, что это умноженная бинарная матрица A*A , чтобы не загружать лишним кодом. (матрица из нулей и единиц A умножается сама на себя и получается новая бинарная матрица из нулей и единиц A*A) Не вижу смысла сувать сюда сам алгоритм умножения, т.к. он здесь был бы лишним, имхо. True - матрица транзитивная, False - нет. tr[][] - это и есть двумерный массив A*A.

80K
12 февраля 2012 года
freeman_
1 / / 12.02.2012
Ребят, вопрос не по теме:
void clear_kb(void);
...
void clear_kb(void){
char buf[40];
gets(buf);
}
Какое предназначение этой функции? Если не сложно.
316
12 февраля 2012 года
Alm3n
889 / / 29.05.2009
Цитата: freeman_
Ребят, вопрос не по теме:
void clear_kb(void);
...
void clear_kb(void){
char buf[40];
gets(buf);
}
Какое предназначение этой функции? Если не сложно.


Читает в буфер с клавиатуры строку до 40-ка символов.

Цитата: lnxdx
Я пояснил, что это умноженная бинарная матрица A*A , чтобы не загружать лишним кодом. (матрица из нулей и единиц A умножается сама на себя и получается новая бинарная матрица из нулей и единиц A*A) Не вижу смысла сувать сюда сам алгоритм умножения, т.к. он здесь был бы лишним, имхо. True - матрица транзитивная, False - нет. tr[][] - это и есть двумерный массив A*A.


Чтобы проверить, транзитивно ли бинарное отношение, нужно сначала получить его транзитивное замыкание. Это делается перемножением отношения самого на себя. Почему ты перемножил всего два раза? Там другое условие количества перемножений.
Потом, когда транзитивное замыкание найдено, его объединяют с предпологаемым транзитивным отношением и, если получается то же отношение, то оно действительно транзитивно.
Правильна ли твоя проверка в контексте этих действий? Нет.

79K
12 февраля 2012 года
lnxdx
4 / / 12.02.2012
Цитата: Alm3n
Читает в буфер с клавиатуры строку до 40-ка символов.

Чтобы проверить, транзитивно ли бинарное отношение, нужно сначала получить его транзитивное замыкание. Это делается перемножением отношения самого на себя. Почему ты перемножил всего два раза? Там другое условие количества перемножений.
Потом, когда транзитивное замыкание найдено, его объединяют с предпологаемым транзитивным отношением и, если получается то же отношение, то оно действительно транзитивно.
Правильна ли твоя проверка в контексте этих действий? Нет.



транзитивное замыкание - это что-то связанное с графами. о графах я ничего не говорил.
Пусть R включено в A*A, тогда отношение R называется транзитивным, если: для всех a,b,c, принадлежащих A: aRb && bRc => aRc. Надо получить сначала матрицу А*А, затем определить транзитивно отношение или нет.
На пальцах пример:
Дана исходная матрица А:
0 1 0 1
0 1 1 0
1 0 1 0
0 0 1 0
Логическим умножением получаем матрицу А*A:
0 1 1 0
1 1 1 0
1 1 1 1
1 0 1 0
Далее определяем, транзитивно ли отношение или нет.

316
12 февраля 2012 года
Alm3n
889 / / 29.05.2009
Цитата: lnxdx
транзитивное замыкание - это что-то связанное с графами. о графах я ничего не говорил.


Надо было сказать сразу, что тебе нужно - телепаты в отпуске.

79K
12 февраля 2012 года
lnxdx
4 / / 12.02.2012
Цитата: Alm3n
Надо было сказать сразу, что тебе нужно - телепаты в отпуске.



виноват, до теории графов еще не дошел(
и все-таки правильно или нет?

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог