Міністерство освіти і науки України Вінницький національний технічний університет ІнІТКІ Кафедра комп’ютерних наук Лабораторна робота № 1 З дисципліни Дискретна матиматика Тема: : Розробка алгоритму і програми для розв’язання задачі про покриття на множинах методом повного перебору Мета: набути навиків застосування методу повного перебору для знаходження найкоротшого і мінімального покриття Хід роботи Блок-схема програми, що обчислює всі можливі покриття за у мовами задачі про покриття представлена на Рисунку 1. / Рисунок 1 - Блок-схема програми, що обчислює всі можливі покриття за умовами задачі про покриття Висновок Виконав[ім’я автора приховано]ктиці у вигляді програми «DM_lab1»в програмному середовищі С++. Результати тестування програми підтвердили її працездатність. Додатки. Інструкції користувача: Запустити програму, відкривши файл під назвою «DM_lab1.exe». Вводимо таблицю покриттів по якій необхідно обчислити всі можливі покриття за умовою задачі про покриття та натиснути кнопку «Enter». Вводимо таблицю цін та натиснути кнопку «Enter». Буде здійснюватися обчислення всіх можливих покриттів за у мовами задачі про покриття. Нижче відобразяться всі можливі покриття за у мовами задачі про покриття. Нижче відобразяться номер мінімального покриття та номер найкоротшого покриття. Лістинг програми: #include <iostream> #include <stdio.h> #include <math.h> using namespace std; void main() { int n,m; n=7; m=9; int A[100][100]; int B[100]; cout<<"Enter array A:\n"; for(int i = 0; i< n; i++) {for(int j=0; j<m; j++) {std::cin>>A[i][j];}} cout<<"Enter array B:"; for(int j=0; j<n; j++) {std::cin>>B[j];} cout<<'\n'; int C[100]; int cina=0; for(int i1=0; i1<n; i1++) for(int i2=i1+1; i2<n; i2++) for (int j=0; j<m; j++) { C[j]=A[i1][j] + A[i2][j]; } if(C[0]!=0 && C[1]!=0 && C[2]!=0 && C[3]!=0 && C[4]!=0 && C[5]!=0 && C[6]!=0 && C[7]!=0 && C[8]!=0) { cina = B[i1]+ B[i2]; std::cout<<"{"<<(i1+1)<<","<<(i2+1)<<"}="<<cina; cina=0; std::cout<<'\n'; for(int i1=0; i1<n; i1++) for(int i2=i1+1; i2<n; i2++) for(int i3=i2+1; i3<n; i3++) for (int j=0; j<m; j++) { C[j]=A[i1][j] + A[i2][j]+ A[i3][j]; } if(C[0]!=0 && C[1]!=0 && C[2]!=0 && C[3]!=0 && C[4]!=0 && C[5]!=0 && C[6]!=0 && C[7]!=0 && C[8]!=0) { cina = B[i1]+ B[i2]+ B[i3]; std::cout<<"{"<<(i1+1)<<","<<(i2+1)<<","<<(i3+1)<<"}="<<cina; cina=0; std::cout<<'\n'; for(int i1=0; i1<n; i1++) for(int i2=i1+1; i2<n; i2++) for(int i3=i2+1; i3<n; i3++) for(int i4=i3+1; i4<n; i4++) for (int j=0; j<m; j++) { C[j]=A[i1][j] + A[i2][j]+ A[i3][j] + A[i4][j]; } if(C[0]!=0 && C[1]!=0 && C[2]!=0 && C[3]!=0 && C[4]!=0 && C[5]!=0 && C[6]!=0 && C[7]!=0 && C[8]!=0) { cina = B[i1]+ B[i2]+ B[i3]+ B[i4]; std::cout<<"{"<<(i1+1)<<","<<(i2+1)<<","<<(i3+1)<<","<<(i4+1)<<"}="<<cina; cina=0; std::cout<<'\n'; for(int i1=0; i1<n; i1++) for(int i2=i1+1; i2<n; i2++) for(int i3=i2+1; i3<n; i3++) for(int i4=i3+1; i4<n; i4++) for(int i5=i4+1; i5<n; i5++) for (int j=0; j<m; j++) {C[j]=A[i1][j] + A[i2][j]+ A[i3][j] + A[i4][j]+ A[i5][j]; } if(C[0]!=0 && C[1]!=0 && C[2]!=0 && C[3]!=0 && C[4]!=0 && C[5]!=0 && C[6]!=0 && C[7]!=0 && C[8]!=0) { cina = B[i1]+ B[i2]+ B[i3]+B[i4]+ B[i5]; std::cout<<"{"<<(i1+1)<<","<<(i2+1)<<","<<(i3+1)<<","<<(i4+1)<<","<<(i5+1)<<"}="<<cina; cina=0; std::cout<<'\n'; for(int i1=0; i1<n; i1++) for(int i2=i1+1; i2<n; i2++) for(int i3=i2+1; i3<n; i3++) for(int i4=i3+1; i4<n; i4++) for(int i5=i4+1; i5<n; i5++) for(int i6=i5+1; i6<n; i6++) for (int j=0; j<m; j++) { C[j]=A[i1][j] + A[i2][j]+ A[i3][j] + A[i4][j]+ A[i5][j]+A[i6][j]; } if(C[0]!=0 && C[1]!=0 && C[2]!=0 && C[3]!=0 && C[4]!=0 && C[5]!=0 && C[6]!=0 && C[7]!=0 && C[8]!=0) { cina = B[i1]+ B[i2]+ B[i3]+B[i4]+ B[i5]+B[i6]; std::cout<<"{"<<(i1+1)<<","<<(i2+1)<<","<<(i3+1)<<","<<(i4+1)<<","<<(i5+1)<<","<<(i6+1)<<"}="<<cina; cina=0; std::cout<<'\n'; for (int j=0; j<m; j++) { C[j]=A[0][j] + A[1][j]+ A[2][j] + A[3][j]+ A[4][j]+A[5][j]+ A[6][j]; } if(C[0]!=0 && C[1]!=0 && C[2]!=0 && C[3]!=0 && C[4]!=0 && C[5]!=0 && C[6]!=0 && C[7]!=0 && C[8]!=0) { cina = B[0]+ B[1]+ B[2]+B[3]+ B[4]+B[5]+ B[6]; std::cout<<"{1,2,3,4,5,6,7}="<<cina; cina=0; std::cout<<'\n'; } std::cout<<'\n'; system("pause");} Результати тестування: //