Міністерство освіти і науки, молоді та спорту України Вінницький національний технічний університет Інститут Інформаційних Технологій та Комп’ютерної Інженерії Лабараторна робота № 3 з дисципліни: Дискретна математика. Тема: Розробка алгоритму і програми для розв’язання задачі про покриття на множинах методом мінімального стовпчика - максимального рядка. м.Вінниця 2013 Мета: набути навиків застосування методу мінімального стовпчика - максимального рядка для побудови покриття на множинах. Порядок виконання роботи: Ознайомитися з методом мінімального стовпчика - максимального рядка. Отримати варіант індивідуального завдання для виконання. Розробити схему алгоритму побудови покриття методом мінімального стовпчика - максимального рядка. Розробити програму побудови покриття методом мінімального стовпчика - максимального рядка. Для заданого варіанту принести результати тестування програми у покроковому режимі. Зробити висновки про результати застосування цього методу для побудови покриття, відзначити його особливість і відмінність від відомих вам методів Завдання для виконання №25
3.Блок-схема Рисунок 1. 4. Приклади тестування програми / 5. Висновок: Побудовано алгоритм, блок-схему програми, розроблено програму мовою C++ що реалізує побудову покриття методом мінімального стовпчика - максимального рядка. 6.Додаток ( Лістинг програми що реалізує мінімального стовпчика - максимального рядка.) #include <iostream> #include <conio.h> #include <stdio.h> main() { setlocale(LC_ALL,"Ukrainian"); int A[100][100],B[100]={0},C[100]={100},K[100]={0}; int a,b,i,j,n,n1,p,l,cina; char ch[12]="АБВГДЕЖ "; printf("ВВЕДiТb КiЛЬКiСТЬ МНОЖИН: \n"); scanf("%d",&a); printf("ВВЕДiТb КiЛЬКiСТЬ СТОВПЦiВ:\n"); scanf("%d",&b); printf(" "); for(i=0;i<b;i++) { printf(" "); printf("%d",i+1); } printf(" цiна"); printf("\n"); for (i=0;i<a;i++) { printf("\n"); printf("%c",ch[i]); for(j=0;j<=b;j++) { printf(" "); scanf("%d",&A[i][j]); } } n1=0;l=0; cina=0; for(j=0;j<a;j++) { n=0; for(i=0;i<b;i++) { if(A[j][i]==1) n++; if(n>n1) {n1=n; p=j; } } } printf("\n"); while(l!=b) { for(i=0;i<b;i++) { if(C[i]!=i) { if(A[p][i]==1) { C[i]=i;l++; } } } cina+=A[p][b]; printf("%c",ch[p]); n1=0; for(j=0;j<a;j++) { n=0; for(i=0;i<b;i++) { if(i!=C[i]) { if(A[j][i]==1) n++; if(n>n1) { n1=n; p=j; }} } } } printf(" - цiна - %d\n",cina); getch(); }