Міністерство освіти і науки України Вінницький національний технічний університет Кафедра КН Лабораторна робота №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++; } } if (countrow > danirow) { danirow = countrow; res2 = k; } countrow = 0; } } res[pos] = Convert::ToString(word[res2]); pos++; for (int b = 0; b < 9; b++) { if (matr[res2][b] == 1) { for (int j = 0; j < 7; ++j) { matr[j][b] = 8; } } } for (int j = 0; j < 9; ++j) { matr[res2][j] = 8; } int count_1 = 0; int count_8 = 9; int povt = 0; for (int i = 0; i < 7; i++) { count_1 = 0; count_8 = 9; for (int j = 0; j < 9; j++) { if (matr[i][j] == 1) { count_1++; } if (matr[i][j] == 8) { count_8--; } } if (count_8 == 0) { povt++; } if ((count_1 == count_8) && (count_8 != 0)) { res[pos] = Convert::ToString(word[i]); pos++; ckl = 1; } } if (povt == 7) { ckl = 1; } if (ckl != 1) { ckl = 2; } } while (ckl == 2); for (int i = 0; i < pos; i++) { this->textBox1->Text += res[i];} this->textBox1->Text += "\r\n"; Метод ядерних рядків. int pos = 0; int danicol = 15; int danirow = 15; int countcol = 0; int countcol1 = 0; int countrow = 0; int countrow1 = 0; int res1[10]; int res1count = 0; int res2[10]; int res2count = 0; int allrowdelet=0; int allcoldelet = 0; int ckl = 0; int prov = 0; int matr[10][10]; int matr2[10][10]; String ^ word = "АБВГДЕЖЗИК"; array<String^>^ yadrres = gcnew array<String^>(20); array<String^>^ mass_notyadrrow = gcnew array<String^>(2000); 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 { prov = 2; ckl = 1; res1count = 0; res2count = 0; danicol = 1; for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { if (matr[j][i] == 1) { countcol++; } if (matr[j][i] == 8) { countcol1++; } } if ((countcol == danicol) && (countcol1 != 10)) { danicol = countcol; res1[res1count] = i; res1count++; prov = 1; ckl = 2; } countcol = 0; countcol1 = 0; } if (prov == 1) { for (int yadrdelet = 0; yadrdelet < res1count; yadrdelet++) { for (int k = 0; k < 10; k++) { if (matr[k][res1[yadrdelet]] == 1) { res2[res2count] = k; res2count++; } } } for (int yadrrow = 0; yadrrow < res2count; yadrrow++) { yadrres[pos] = Convert::ToString(word[res2[yadrrow]]); pos++; allrowdelet++; } for (int yadrrowdelet = 0; yadrrowdelet < res2count; yadrrowdelet++) { for (int b = 0; b < 10; b++) { if (matr[res2[yadrrowdelet]][b] == 1) { for (int j = 0; j < 10; ++j) { matr[j][b] = 8; } } } for (int j = 0; j < 10; ++j) { matr[res2[yadrrowdelet]][j] = 8; } } int count_1 = 0; int count_8 = 10; int povt = 0; for (int i = 0; i < 10; i++) { count_1 = 0; count_8 = 10; for (int j = 0; j < 10; j++) { if (matr[i][j] == 0) { count_1++; } if (matr[i][j] == 8) { count_8--; } } if (count_8 == 0) { povt++; } if ((count_1 == count_8) && (count_8 != 0)) { for (int delet_zero_row = 0; delet_zero_row < 10; delet_zero_row++) { matr[i][delet_zero_row] = 8; allrowdelet++; } } } if (povt == 10) { ckl = 1; } int poglcol = 0; int poglcol1 = 0; int poglmascol[10]; int contr = 0; int poglmascolind = 0; int poglrow = 0; int poglrow1 = 0; int poglmasrow[10]; int poglmasrowind = 0; int col_not_delet[10]; int row_not_delet[10]; int coldeletcount = 0; int rowdeletcount = 0; int row_not_delet_count = 0; int col_not_delet_count = 0; for (int i = 0; i < 10; i++) { coldeletcount = 0; for (int j = 0; j < 10; j++) { if (matr[j][i] == 8) { coldeletcount++; } } if (coldeletcount != 10) { col_not_delet[col_not_delet_count] = i; col_not_delet_count++; } } int sum1 = 0; for (int i = 0; i < col_not_delet_count - 1; i++) { poglcol = 0; poglcol1 = 0; sum1 = 0; for (int j = 0; j < 10; j++) { if (matr[j][col_not_delet[i]] != matr[j][col_not_delet[i + 1]]) { sum1++; } if (sum1 == 1) { if (matr[j][col_not_delet[i]] < matr[j][col_not_delet[i + 1]]) { poglcol++; } if (matr[j][col_not_delet[i + 1]] < matr[j][col_not_delet[i]]) { poglcol1++; } } } if ((poglcol == 1) && (sum1 == 1)) { poglmascol[poglmascolind] = col_not_delet[i + 1]; poglmascolind++; } if ((poglcol1 == 1) && (sum1 == 1)) { poglmascol[poglmascolind] = col_not_delet[i]; poglmascolind++; } } for (int i = 0; i < poglmascolind; i++) { for (int j = 0; j < 10; j++) { matr[j][poglmascol[i]] = 8; } } for (int i = 0; i < 10; i++) { rowdeletcount = 0; for (int j = 0; j < 10; j++) { if (matr[i][j] == 8) { rowdeletcount++; } } if (rowdeletcount != 10) { row_not_delet[row_not_delet_count] = i; row_not_delet_count++; } } int sum = 0; for (int i = 0; i < row_not_delet_count - 1; i++) { poglrow = 0; poglrow1 = 0; sum = 0; for (int j = 0; j < 10; j++) { if (matr[row_not_delet[i]][j] != matr[row_not_delet[i + 1]][j]) { sum++; } if (sum == 1) { if (matr[row_not_delet[i]][j] < matr[row_not_delet[i + 1]][j]) { poglrow++; } if (matr[row_not_delet[i + 1]][j] < matr[row_not_delet[i]][j]) { poglrow1++; } } } if ((poglrow == 1) && (sum == 1)) { poglmasrow[poglmasrowind] = row_not_delet[i]; poglmasrowind++; } if ((poglrow1 == 1) && (sum == 1)) { poglmasrow[poglmasrowind] = row_not_delet[i + 1]; poglmasrowind++; } } for (int i = 0; i < poglmasrowind; i++) { for (int j = 0; j < 10; j++) { matr[poglmasrow[i]][j] = 8; } } } }while (ckl==2); if (pos == 10) { for (int i = 0; i < pos; i++) { this->textBox1->Text += yadrres[i]; } } int letter[10]; int vuvod = 0; int indvuvod = 0; for (int i = 0; i < 10; i++) { vuvod = 0; for (int j = 0; j < 10; j++) { if (matr[i][j] == 8) { vuvod++; } } if (vuvod != 10) { letter[indvuvod] = i; indvuvod++; } } int row_ind_mas = 0; int col_ind_mas = 0; int ind_8 = 0; int col_ind = 0; int col_ind_contr = 0; for (int i = 0; i < 10; i++) { ind_8 = 0; col_ind_mas = 0; for (int j = 0; j < 10; j++) { if (matr[i][j] != 8) { matr2[row_ind_mas][col_ind_mas] = matr[i][j]; col_ind_mas++; } if (matr[i][j] == 8) { ind_8++; } } if (ind_8 != 10) { row_ind_mas++; col_ind = col_ind_mas; } if ((ind_8 != 10)&&(col_ind_contr==1)) { col_ind = col_ind_mas; col_ind_contr++; } } array<String^>^ strpokr = gcnew array<String^>(8); array<String^>^ strporiv = gcnew array<String^>(8); bool inword = false; bool inword1 = false; bool start = false; bool start2 = false; int outword = 2; int outword2 = 2; int outword3 = 2; int outword4 = 2; int strpoktcount = 0; int strgovcount = 0; int stpcount = 0; int stporcount = 0; int perev = 0; int poch = 0, kin = 0; int countpokr = 0; for (int baggo = 0; baggo < masind; baggo++, strgovcount++) { start = false; if (((mass_notyadrrow[baggo]) != " ") && !inword1) { inword1 = true; outword = 1; strgovcount = 0; stpcount = 0; for (int i = 0; i < 8; i++) { strpokr[i] = "\0"; } } if (((mass_notyadrrow[baggo]) == " ") && inword1) { inword1 = false; outword2 = 1; } if (inword1) { strpokr[strgovcount] = mass_notyadrrow[baggo]; stpcount++; } if (((mass_notyadrrow[baggo]) == " ") && (outword2 == 1) && (outword == 1)) { outword = 0; outword2 = 0; start = true; } if (start) { for (int i = 0; i < pos; i++) { this->textBox1->Text += yadrres[i]; } for (int word = 0; word < stpcount; word++) { this->textBox1->Text += strpokr[word]; } countpokr++; this->textBox1->Text += "\r\n"; for (int bag = 0; bag < masind; bag++, strpoktcount++) { perev = 0; start2 = false; if (((mass_notyadrrow[bag]) != " ") && !inword) { inword = true; poch = bag; outword3 = 1; for (int i = 0; i < 8; i++) { strporiv[i] = "\0"; } strpoktcount = 0; stporcount = 0; } if (((mass_notyadrrow[bag]) == " ") && inword) { inword = false; outword4 = 1; kin = bag; } if (inword) { strporiv[strpoktcount] = mass_notyadrrow[bag]; stporcount++; } if (((mass_notyadrrow[baggo]) == " ") && (outword3 == 1) && (outword4 == 1)) { outword3 = 0; outword4 = 0; start2 = true; } if (start2) { for (int i = 0; i < stpcount; i++) { for (int j = 0; j < stporcount; j++) { if (strpokr[i] == strporiv[j]) { perev++; } } } } if (perev == stpcount) { for (int i = poch; i < kin; i++) { mass_notyadrrow[i] = " "; } } } } } this->textBox2->Text += Convert::ToString(countpokr);