一、题目
求二维矩阵中和最大的子矩阵。
二、设计思路
将二维数组转化为一维数组，在运用一维数组求最大子数组方法求出。c[0][]=a[0][]；c[1][]=a[0][]+a[1][];依次往下。
将二维数组存到txt文件中。
三、源代码
1 #include<iostream.h> 2 #include<fstream.h> 3 void writeFile(int a[][20],int length,int row)//文件写入 4 { 5 ofstream outFile; 6 outFile.open("test.txt",ios::app); 7 for(int i=0;i<row;i++) 8 { 9 for(int j=0;j<length;j++) 10 { 11 outFile<<a[i][j]<<" "; 12 } 13 outFile<<endl; 14 } 15 outFile.close(); 16 } 17 int max1(int a[],int N); 18 int column(int a[][20],int length,int num1) //求最大和 19 { 20 int y=0; 21 int d[20]; 22 int e[100]; 23 int c[100][20]; 24 c[0][0]=0; 25 int p=0; 26 int b[100]={0}; 27 for(int j=0;j<num1;j++) 28 { 29 for(int t=j;t<num1;t++) 30 { 31 for(int i=0;i<length;i++) 32 { 33 b[i]=b[i]+a[t][i]; 34 c[p][i]=b[i]; 35 } 36 p=p+1; 37 } 38 for(int o=0;o<100;o++) 39 { 40 b[o]=0; 41 } 42 } 43 for(int l=0;l<p;l++) 44 { 45 46 for(int u=0;u<length;u++) 47 { 48 d[u]=c[l][u]; 49 //cout<<d[u]<<" "; 50 } 51 e[y++]=max1(d,length); 52 //cout<<e[y-1]<<" "; 53 } 54 int Max=e[0]; 55 for(int i=0;i<y;i++) 56 { 57 if(e[i]>=Max) 58 { 59 Max=e[i]; 60 } 61 } 62 return Max; 63 } 64 int max1(int a[],int N) //球一维最大和 65 { 66 67 int b[20]; //正负交替数组 68 int c[20]; //最终比较数组 69 int i; 70 int M; //存放数组b的长度 71 int j=0; 72 int max; //存放最大值 73 int p=0; 74 int sum; //相邻正数和 75 int sum1; //相邻负数和 76 sum=0; 77 sum1=0; 78 int u=0; 79 //判断数组是否全负 80 for(i=0;i<N;i++) 81 { 82 if(a[i]>=0) 83 { 84 u=1; 85 } 86 } 87 if(u==1) 88 { 89 //求出相邻正数或相邻负数的和，形成正负交替数组 90 for(i=0;i<N;i++) 91 { 92 if(a[i]>=0) 93 { 94 if(i<N-1) 95 { 96 if(a[i+1]>=0) 97 { 98 sum=sum+a[i]; 99 } 100 else 101 { 102 b[j++]=sum+a[i]; 103 sum=0; 104 } 105 } 106 else 107 { 108 if(a[i-1]>=0) 109 { 110 b[j++]=sum+a[N-1]; 111 } 112 else 113 { 114 b[j++]=a[N-1]; 115 } 116 } 117 118 } 119 else if(a[i]<0) 120 { 121 if(i<N-1) 122 { 123 if(a[i+1]<0) 124 { 125 sum1=sum1+a[i]; 126 } 127 else 128 { 129 b[j++]=sum1+a[i]; 130 sum1=0; 131 } 132 } 133 else 134 { 135 if(a[i-1]<0) 136 { 137 b[j++]=sum1+a[N-1]; 138 } 139 else 140 { 141 b[j++]=a[N-1]; 142 } 143 } 144 } 145 } 146 M=j; 147 if(b[0]<0) 148 { 149 j=1; 150 } 151 else 152 { 153 j=0; 154 } 155 //对数组B进行操作，将利用算法求的机最大值存入数组c中 156 for(int y=j;y<M;y=y+2) 157 { 158 if(y+2<M) 159 { 160 if(b[y]+b[y+1]>=0) 161 { 162 c[p++]=b[y]; 163 b[y+2]=b[y+2]+b[y+1]+b[y]; 164 if((y+2==M-1)||(y+2==M-2)) 165 { 166 c[p++]=b[y+2]; 167 break; 168 } 169 } 170 else 171 { 172 c[p++]=b[y]; 173 } 174 } 175 else 176 { 177 c[p++]=b[y]; 178 } 179 180 } 181 //对数组c求最大值 182 max=c[0]; 183 for(i=0;i<p;i++) 184 { 185 if(c[i]>=max) 186 { 187 max=c[i]; 188 } 189 } 190 return max; 191 } 192 else 193 { 194 max=a[0]; 195 for(i=0;i<N;i++) 196 { 197 if(a[i]>=max) 198 { 199 max=a[i]; 200 } 201 } 202 return max; 203 } 204 } 205 int main() 206 { 207 ofstream outFile; 208 outFile.open("test.txt",ios::app); 209 int a[20][20]; 210 int length,index; 211 212 cout<<"输入行数列数:"; 213 cin>>index>>length; 214 outFile<<"行数:"<<index<<endl; 215 outFile<<"列数:"<<length<<endl; 216 outFile.close(); 217 int y=0; 218 for(int i=0;i<index;i++) 219 { 220 for(int j=0;j<length;j++) 221 { 222 cin>>a[i][j]; 223 } 224 } 225 writeFile(a,length,index); 226 227 int s=column(a,length,index); 228 cout<<"最大和为:"<<s<<endl; 229 return 0; 230 }
四、截图
五、实验总结
本次实验在文件写入方面，我与他找了些许资料。最终解决了。在思路方面，我们想延用以为数组的方法，但是对于我想象不到如何二维数组怎么使用，但是他提出我们把所有的都列举出来吧。顿时想到转化为一维数组的方法，运用到了程序里。一个人的思维总是有限的，只有思想的碰撞，往往才有更多的激发。
六、我们的合照
