Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна робота 2 Дискретна математика
Інформація про навчальний заклад
ВУЗ:
Вінницькій національний технічний університет
Інститут:
О
Факультет:
СІ
Кафедра:
КН
Інформація про роботу
Рік:
2018
Тип роботи:
Лабораторна робота
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Вінницький національний технічний університет
Кафедра КН
Лабораторна робота №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);
03.10.2018 00:12
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора