1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| #include "stdafx.h"
#include <iostream>
using namespace std;
void Perebor(int**A,int M, int N, int**B, int c);
void Min_column(int**A, int N, int M, int* Sum, int**B,int c);
void Max_row(int**A, int MCN, int M, int N, int**B, int c);
void Build_cover(int**A,int**B,int c, int MRN, int N,int M);
void Erase_columns(int**A,int**B,int MRN, int M, int N, int c);
int _tmain(int argc, _TCHAR* argv[])
{
int M,N,c=0; //М - для хранения кол-ва строк, N- для хранения кол-ва столбцов
cout<<"Enter number of rows: ";cin>>M;
cout<<"Enter number of columns: ";cin>>N;
int **B= new int*[M-1]; // массив В организован для хранения покрытия
int **A= new int*[M];
for (int i=0; i<M; i++) {A= new int[N];}
cout<<"Fill the matrix\n";
for (int i=0; i<M; i++){
for (int j=0; j<N; j++){scanf("%u", &A[j]);}
}
Perebor(A,M,N,B,c);
return 0;
};
void Perebor(int**A,int M, int N, int**B, int c){
int *Sum= new int[N]; //в массиве Sum будем хранить кол-во единиц в каждом столбце матрицы
for (int j=0; j<N; j++){
Sum[j]=0;
for (int i=0; i<M; i++){
Sum[j]=Sum[j]+A[j];
}
if (Sum[j]==0) {
cout<<"There is no cover in this matrix\n"; delete[]Sum;
for(int i=0; i<M; i++) delete[]A; delete[]A; delete[]B; exit(1);}
};
Min_column(A,N,M,Sum,B,c);
}
void Min_column(int**A, int N, int M, int* Sum, int**B,int c){
int MCS=0; //Переменная для хранения кол-ва единиц в минимальном столбце
int MCN=0; // Переменная для хранения номера минимального столбца
for (int j=0; j<N-1; j++){
if (Sum[j]<=Sum[j+1]){
if (MCS==0){MCS=Sum[j];MCN=j;} //организовано для того, чтобы мин. столбцом
else{ if(MCS>Sum[j]){MCS=Sum[j];MCN=j;}} //стал первый обнаруженный мин. столбец
}
else {if (MCS==0){MCS=Sum[j+1];MCN=j+1;}}
}
delete[] Sum;
Max_row(A,MCN,M,N,B,c);
}
void Max_row(int**A, int MCN, int M, int N, int**B, int c){
int *Sum= new int[M];
int MRS=0,MRN=0;
for (int i=0; i<M; i++){
Sum=0;
if (A[MCN]==1){
for(int j=0; j<N; j++) Sum=Sum+A[j];
}
}
for (int i=0; i<M-1; i++){
if (Sum-Sum[i+1]!=0){
if(Sum>Sum[i+1]){
if (MRS==0) {MRS=Sum; MRN=i;}
else{
if(MRS<Sum) {MRS=Sum; MRN=i;}
}
}
else{
if (MRS==0) {MRS=Sum[i+1]; MRN=i+1;}
else{
if(MRS<Sum[i+1]) {MRS=Sum[i+1]; MRN=i+1;}
}
}
}
if (Sum!=0 && Sum[i+1]!=0 && Sum==Sum[i+1]){
if (MRS==0) {MRS=Sum[i+1]; MRN=i+1;}
else{
if(MRS<=Sum[i+1]) {MRS=Sum[i+1]; MRN=i+1;}
}
}
}
delete[] Sum;
Build_cover(A,B,c,MRN,N,M);
}
void Build_cover(int**A,int**B,int c, int MRN, int N,int M){
B[c]=new int[N];
for(int j=0; j<N; j++) B[c][j]=A[MRN][j];
c++;
Erase_columns(A,B,MRN,M,N,c);
}
void Erase_columns(int**A,int**B,int MRN, int M, int N, int c){
int d=0,e=0; // Счётчики для массива Temp (d-строки, е-столбцы)
int ed=0; //Счётчик количества единиц в максимальной строке
for (int j=0; j<N; j++) if (A[MRN][j]==1) ed++;
if (ed==N){cout<<"Cover is built\n"; for(int i=0; i<M; i++) delete[]A; delete[]A; delete[]B; system("Pause"); exit(1);}
int**Temp=new int*[M];
for (int i=0; i<M; i++) Temp=new int[N-ed];
for (int j=0; j<N; j++){
if (A[MRN][j]!=1){
for (int i=0; i<M; i++){Temp[d][e]=A[j]; d++;}
e++;d=0;}
}
for (int i=0; i<M; i++){delete[]A;}
delete[]A;
N=N-ed;
int**A=new int*[M];
for(int i=0; i<N; i++) A=new int[N];
for (int i=0; i<M; i++){ for (int j=0; j<N; j++) A[j]=Temp[j];}
for (int i=0; i<M; i++) delete[]Temp;
delete[]Temp;
Perebor(A,M,N,B,c);
} |
(
