Код булевая матрица проверка на транзитивность

@AmericanoBox · 06.04.2020, 13:10. **Показов** 5290. **Ответов** 5

Студворк — интернет-сервис помощи студентам

Как сделать проверку булевой матрицы на транзитивность?

C#
1
2
3
4
5
6
7
8
9
10
11
12
var K = new[] { "aaa", "", "c", "ob", "obob", "cc" }; 
                bulevaya = new bool[K.Length, K.Length];
                for (int i = 0; i < K.Length; i++)
                {
                    for (int j = 0; j < K.Length; j++)
                    {
                        if (K[i] == K[j] + K[j])
                            bulevaya[i, j] = true;
                        Console.Write(bulevaya[i, j] ? "1 " : "0 ");
                    }
                    Console.WriteLine();
                }

Как сделать проверку булевой матрицы на транзитивность, нужно дописать код чтобы проверялось и выводилось является ли транзитивным, или нет

(В задании даны эти пары, (х,у) принадлежит R. Строка х состоит из двух сцепленных строк у)

@AndrewLis · 06.04.2020, 15:44

Поправьте, если не прав, но транзитивность -- это свойство бинарного отношения, а не булевой матрицы.
Проверку на транзитивность, используя матрицу отношения, можно так:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool p, t = true;
for (int i = 0; i < K.Length; i++)
{
    for (int j = 0; j < K.Length; j++)
    {
        p = false;
        for (int k = 0; k < K.Length; k++)
            p = bulevaya[i, k] && bulevaya[k, j] || p;
        if (t = p && !bulevaya[i, j]) break;
    }
    if (t) break;
}
if (t) Console.WriteLine("Отношение не транзитивно");
else Console.WriteLine("Отношение транзитивно");

@AmericanoBox · 06.04.2020, 16:11 **[ТС]**

Тогда скажите пожалуйста, вот у меня есть пары
var G = new[] { "a", "b", "c" };
var R = new[] { ("a", "a"), ("b", "b"), ("c", "c"), ("a", "b"), ("b", "a"), ("c", "b") };

R это уже заданное отношение

Если вписать туда ваш код и изменить K на G.Length

То получится что он выдает отношение транзитивное, но оно является не транзитивным

@AndrewLis · 06.04.2020, 16:57

Сообщение от AmericanoBox

Если вписать туда ваш код

Прошу прощения, вписать куда?

@AmericanoBox · 06.04.2020, 17:53 **[ТС]**

Ой, извините, мой косяк, но у меня вопрос.

Вы можете обьяснить словами, желательно каждый ход, что делает ваш алгоритм, потому что я не очень понимаю
1. почему зачем задаются две переменные p и t
2. почему p было true, а стало false
3. Что означает эта строка p = bulevaya[i, k] && bulevaya[k, j] || p
4. Что означает эта строка if (t = p && !bulevaya[i, j]) break;
5. И что означает if (t) break; Всмысле? Как это: Если t. Не очень понимаю

Добавлено через 15 минут
Имеется ввиду то что t == true?

@AndrewLis · 06.04.2020, 18:50

1. Переменная p используется для вычисления элементов квадрата матрицы отношения (сам квадрат явно не вычисляется, только отдельно элементы).
Переменная t используется для хранения промежуточных результатов проверки на транзитивность.
2. Извините, не понял вопроса.
3. В цикле вычисляется элемент квадрата матрицы отношения. Т.к. матрица булева, вместо умножения используется логическое И, вместо сложения -- логическое ИЛИ.
4. Проверка того, является ли квадрат матрицы отношения подматрицей матрицы отношения. Здесь bulevaya[i, j] -- элемент матрицы отношения, а p -- соответственный элемент квадрата матрицы отношения. Если первый элемент равен 0 (false), а второй -- 1 (true) хотя бы для одной пары элементов, отношение R не является транзитивным.
Выражение p == true && bulevaya[i, j] == false эквивалентно выражению p && !bulevaya[i, j].
5. Да, это значит if (t == true)

Новые блоги и статьи Все статьи Все блоги /
Перемещение выделенных строк ТЧ из одного документа в другой Maks 30.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .

@AmericanoBox Заблокирован
	06.04.2020, 16:11 [ТС]
	Тогда скажите пожалуйста, вот у меня есть пары var G = new[] { "a", "b", "c" }; var R = new[] { ("a", "a"), ("b", "b"), ("c", "c"), ("a", "b"), ("b", "a"), ("c", "b") }; R это уже заданное отношение Если вписать туда ваш код и изменить K на G.Length То получится что он выдает отношение транзитивное, но оно является не транзитивным 0

@AmericanoBox Заблокирован
	06.04.2020, 17:53 [ТС]
	Ой, извините, мой косяк, но у меня вопрос. Вы можете обьяснить словами, желательно каждый ход, что делает ваш алгоритм, потому что я не очень понимаю 1. почему зачем задаются две переменные p и t 2. почему p было true, а стало false 3. Что означает эта строка p = bulevaya[i, k] && bulevaya[k, j] \|\| p 4. Что означает эта строка if (t = p && !bulevaya[i, j]) break; 5. И что означает if (t) break; Всмысле? Как это: Если t. Не очень понимаю Добавлено через 15 минут Имеется ввиду то что t == true? 0

@AndrewLis 202 / 120 / 85 Регистрация: 15.12.2016 Сообщений: 235
	06.04.2020, 18:50
	1. Переменная p используется для вычисления элементов квадрата матрицы отношения (сам квадрат явно не вычисляется, только отдельно элементы). Переменная t используется для хранения промежуточных результатов проверки на транзитивность. 2. Извините, не понял вопроса. 3. В цикле вычисляется элемент квадрата матрицы отношения. Т.к. матрица булева, вместо умножения используется логическое И, вместо сложения -- логическое ИЛИ. 4. Проверка того, является ли квадрат матрицы отношения подматрицей матрицы отношения. Здесь bulevaya[i, j] -- элемент матрицы отношения, а p -- соответственный элемент квадрата матрицы отношения. Если первый элемент равен 0 (false), а второй -- 1 (true) хотя бы для одной пары элементов, отношение R не является транзитивным. Выражение p == true && bulevaya[i, j] == false эквивалентно выражению p && !bulevaya[i, j]. 5. Да, это значит if (t == true) 0

Код булевая матрица проверка на транзитивность

Решение