Міністерство освіти і науки України Вінницький національний технічний університет Кафедра КН Лабораторна робота №2 з дисципліни: «Дискретна математика» На тему: «Розробка алгоритму і програми для розв’язання задачі про покриття на множинах методом мінімального стовпчика - максимального рядка та методом ядерних рядків»  Вінниця 2016 Мета роботи: набути навиків застосування методу мінімального стовпчика - максимального рядка та методу ядерних рядків для побудови покриття на множинах. Завдання: розробити схему алгоритму і програму побудови покриття методом мінімального стовпчика - максимального рядка та методом ядерних рядків. Продемонструвати роботу програми побудови покриття методом мінімального стовпчика - максимального рядка на прикладі №14, та методом ядерних рядків на власному прикладі. Варіант №24 1 2 3 4 5 6 7 8 9 a  А   1   1   1 2  Б 1    1  1 1  2  В  1 1 1      1  Г 1   1 1    1 3  Д     1 1    2  Е 1 1     1   1  Ж  1 1   1 1 1  3  Власний приклад 1 2 3 4 5 6 7 8 9 10  А   1   1   1   Б 1      1 1  1  В  1 1 1        Г 1   1      1  Д     1 1  1  1  Е 1 1     1     Ж  1 1   1 1 1    З 1         1  И    1   1 1    К  1     1   1  Схема Алгоритму:
Рисунок 1- Блок-схема програми для побудови покриття на множинах методом мінімального стовпчика - максимального рядка
Рисунок 2 - Блок-схема програми для побудови покриття на множинах методом ядерних рядків Результати тестування програми: Рисунок 3 - Результат роботи програми побудови покриття методом мінімального стовпчика - максимального рядка Рисунок 4 - Результат роботи програми побудови покриття методом ядерних рядків Висновок: Під час виконання лабораторної роботи було набуто навички застосування двох методів для знаходження покриття на множинах: метод мінімального стовпчика - максимального рядка і метод ядерних рядків. Щоб знайти найкортше покриття найкраще використовувати метод мінімального стовпчика - максимального рядка, так як цей метод має простий і зрозуміли алгоритм. Методом ядерних рядків було знайдено 6 покриттів. Метод ядерних рядків зручно використовувати при великих кількостях підмножин. Додаток №1. Інструкція користувача Для запуску програми побудови покриття методом мінімального стовпчика - максимального рядка потрібно натиснути на ярлик з назвою «DM_lab2.exe», для програми побудови покриття методом ядерних рядків - «DM_lab2_2.exe».(Подільші дії однакові для обох програм) Розставити одиниці у відповідних комірках. Щоб запустити методи знаходження покриття на множинах потрібно натиснути кнопку
. Програми виводять покриття у відповідних полях. Додаток 2. Лістінг програми: Методом мінімального стовпчика - максимального рядка. int pos = 0; int danicol = 15; int danirow = 15; int countcol = 0; int countcol1 = 0; int countrow = 0; int countrow1 = 0; int res1 = 0; int res2 = 0; int ckl = 0; int matr[10][10]; String ^ word = "АБВГДЕЖ"; array<String^>^ res = gcnew array<String^>(20); for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) matr[i][j] = 0; } for (int i = 0; i < dataGridView1->RowCount; ++i) { for (int j = 0; j < dataGridView1->ColumnCount; ++j) { matr[i][j] = Convert::ToInt32(dataGridView1->Rows[i]->Cells[j]->Value); } } pos = 0; do { danicol = 15; for (int i = 0; i < 9; i++) { for (int j = 0; j < 7; j++) { if (matr[j][i] == 1) { countcol++; } if (matr[j][i] == 8) { countcol1++; } } if ((countcol<danicol) && (countcol1 != 7)) { danicol = countcol; res1 = i; } countcol = 0; countcol1 = 0; } danirow = 0; for (int k = 0; k < 7; k++) { if (matr[k][res1] == 1) { for (int i = 0; i < 9; i++) { if (matr[k][i] == 1) { countrow++; ...