现代程序设计——homework-02

关于题目：

　　题目地址：http://www.cnblogs.com/xinz/p/3318230.html

　　首先，不得不说自从写完第一次作业，我就开始“抠”这个题，第一眼看这个题就感觉好“坑”，读一遍之后什么都木有发现，满满的一头雾水。连题目的描述都木有看明白！如图：文件格式描述中的输入数据格式是“每一行的元素，”样例元素是“5,6，-3,8,-9，2”。那么，“2”这个行末元素后面要不要加个逗号呢？32位有符号整数是默认成二进制表示的？我们假设输入格式是有“，”并且老师不会搞一个32位的十进制整数搞死我们。那么，可以的开始我们的苦逼解题之路：

解题之路：

阶段一：

第一步：

　　容错问题看起来有很多的样子：

1. 文件打开错误处理；
2. 输入的行列数与矩阵大小不等；
3. 输入的数字并非合法数字；
4. 输入数字、运算结果溢出；

　　。

　　。

　　。

　　。

　　。

　　。

瞬间头大的感觉，我们还是一条一条开始慢慢解决吧！

1、文件打开错误处理：

　　写了一个暑假的Html和JavaSript，感觉命令行程序已经好久没碰过了，好陌生的感觉。翻一翻C语言的手册吧……在Stander I/O 里面找到了fopen函数，原来文件打开失败就会返回空指针，打开成功就返回文件指针，貌似有点儿头绪了……

 if(argc==)
     {
         if((in = fopen(argv[],"r+"))==NULL)
         {
             printf("Open file error, please make sure you have inputed right file name and location!");
             return ;
         }
     }
     else
     {
         printf("Only one parameter of input file name is needed!");
         return ;
     }

　　2、输入的行列数与矩阵的大小不等：

　　　　我假设input.txt文件的内容来自其他程序的输出，并且那个程序可能出现运行错误，那么我们就“顺理成章”地遇到了这种错误，遇到这种错误　　　怎么办？行列数小一点还好办，大不了读入的矩阵不完全，至少程序能顺利跑完，行列数都大一点儿也好办，至少我能亲眼看见程序死掉了。万一一个　　　大一点，一个小一点！？那就坑死人的节奏了！！！！这时候突然想到样例那个诡异的输入，“5,6，-3,8,-9，2”，原来少个“，”也会有好处！？　　　那么，我就以矩阵为标准进行读入了，行列号只是用来作为一个判断，本人比较懒，并且严重不喜欢动态分配空间，铁了心搞一个固定大小的数组，输　　　入的数组大了的话就对不起了，爷不给你算了！这用户两头要讲究一点儿嘛，说多大就多大，买张饼你想换个大的还得另加钱呢！　

 fscanf(in,"%d,%d,",&row,&column);
 if(row>Max_R||column>Max_C)
 {
     printf("Come on! Don't break rules of our deal!");
     return ;
 }

　　3、输入的数字并非合法数字：

　　　　我笃定"Everything is possible"，那么，我们需要判断每个输入的数字是否是个合法的数字，再次翻出手册，然后又尝试了几下，scanf同志还　　　是很地道的，输入的是数字他就吃进来，输入的不是数字就放到后面等着，还很人性的返回个“0”

 if(fscanf(in,"%d,%d",&row,&column)!=)
     {
         printf("%d %d",row,column);
         printf("Row Column number illegal!");
         system("pause");
         return ;
     }
     fgetc(in);
     if(row>Max_R||column>Max_C)
     {
         printf("Come on! Don't break rules of our deal!");
         system("pause");
         return ;
     }
     printf("%d %d",row,column);
     for(i=,endflag=;i<row;i++)
     {
         for(j=;j<column;j++)
         {

             endflag=fscanf(in,"%d",&matrix[i][j]);
             if(endflag==)
             {
                 printf("Matrix number illegal!");
                 system("pause");
                 return ;
             }
             if(endflag==EOF)
                 break;
             c=fgetc(in);
             if(c!=',')
                 if(j!=column-)
                 {
                     printf("Shit problem!");
                     system("pause");
                     return ;
                 }
                 else
                     break;
             //printf("%d%c",matrix[i][j],c);
         }
         if(endflag==EOF)
             if(i!=row-)
             {
                 printf("Shit problem!");
                 system("pause");
                 return ;
             }
             else
                 break;
     }

　　　　不得不吐槽一把，容错处理好是一个“D”疼，中间测试了各种问题和不出问题的结果，各种截图会撑爆这篇博客的！！！，在此上一张图请注意问题的名称，感受一下我　　　当时的心情！！！

　　4、输入数字、运行结果溢出：

　　　　在第一天看这个题的时候，我和一个搞竞赛的“大牛”讨论过这个问题，他竟然说出了用“高精度”，我勒个擦的，当年写C语言作业就对这个玩　　　意儿有了阴影，就不手写了，重申一下，我是个比较懒的人，搞那么大的矩阵还要搞那么大的数！我真心不想给你算出结果来，于是，我这样处理，得　　　知long long int类型的数是有范围的（-9223372036854775808~9223372036854775807），那么，我搞一个字符串存这两个值的一半，如果你的输入中　　　的数有超过我的半值范围的，不好意思，我就不给你算了。至于结果嘛，我要弄一个乘数一个模最值的余数，用两个部分表示。

　　　　我的方法实在是又有点投机取巧了，于是好好学习了一把高精度整数加法，附上链接一枚：

　　　　　　http://blog.csdn.net/tukangzheng/article/details/6918922

　　　　　

 #include<stdio.h>
 #include<stdlib.h>
 #define Max_R 10000
 #define Max_C 10000
 long long matrix[Max_R][Max_C];
 long long Min=-;
 long long Max=;
 int main(int argc, char *argv[])
 {
     int i,j,row,column,endflag,multtem=,mult=;
     long long tempsub,minsub,maxsub;
     char c;
     FILE *in;
     if(argc>=)
     {
         if((in = fopen(argv[argc-],"r+"))==NULL)
         {
             printf("%s %s Open file error, please make sure you have inputed right file name and location!",argv[],argv[]);
             system("pause");
             return ;
         }
     }
     else
     {
         printf("%d,Only one parameter of input file name is needed!",argc);
         system("pause");
         return ;
     }
     //printf("%d",fscanf(in,"%d,%d,",&row,&column));
     if(fscanf(in,"%d,%d",&row,&column)!=)
     {
         printf("%d %d",row,column);
         printf("Row Column number illegal!");
         system("pause");
         return ;
     }
     fgetc(in);
     if(row>Max_R||column>Max_C)
     {
         printf("Come on! Don't break rules of our deal!");
         system("pause");
         return ;
     }
     printf("%d %d",row,column);
     for(i=,endflag=;i<row;i++)
     {
         for(j=;j<column;j++)
         {

             endflag=fscanf(in,"%lld",&matrix[i][j]);
             if(matrix[i][j]>Max||matrix[i][j]<Min)
             {
                 printf("Please! I can't handle that");
                 system("pause");
                 return ;
             }
             if(endflag==)
             {
                 printf("Matrix number illegal!");
                 system("pause");
                 return ;
             }
             if(endflag==EOF)
                 break;
             c=fgetc(in);
             if(c!=',')
                 if(j!=column-)
                 {
                     printf("Shit problem!");
                     system("pause");
                     return ;
                 }
                 else
                     break;
             //printf("%d%c",matrix[i][j],c);
         }
         if(endflag==EOF)
             if(i!=row-)
             {
                 printf("Shit problem!");
                 system("pause");
                 return ;
             }
             else
                 break;
     }
     if(row==)
     {
         tempsub=;
         //to get the minimum maxsub, find the minimum subarray;
         for(i=;i<column;i++)
         {
             if(i==)
                 minsub=matrix[][];
             if(minsub>matrix[][i])
                 minsub=matrix[][i];
         }
         maxsub=minsub;
         for(i=;i<column;i++)
         {
             if(multtem>||tempsub+matrix[][i]>matrix[][i])
                 tempsub=tempsub+matrix[][i];
             else
                 tempsub=matrix[][i];
             if(tempsub>Max)
             {
                 tempsub-=Max;
                 multtem++;
             }
             if(tempsub<Min)
             {
                 tempsub+=Max;
                 multtem--;
             }
             if(tempsub>maxsub)
             {
                 maxsub=tempsub;
                 mult=multtem;
             }
         }
         printf("Multiplier:%d Remainder:%lld\n",mult,maxsub);
         system("pause");
         return ;
     }
 }

　　　　这是处理完第四个问题的代码，下面是运行的结果们：

输入文件：

1,

6,

5,6,-3,8,-9,2

输入文件：

1,

6,

5,6,3611686018427387904,4511686018427387904,2611686018427387904,1611686018427387904

阶段二：

第一步：

　　分析一把这个题，还是可以按照老套路来的无非先枚举一下，不错，O(n^2*m^2)个子矩阵，如果每个矩阵都“善良”地一个一个求和，那么这个复杂度是O(n^4*m^4)于是，有点接受不了了，然后，无非Trade Memory一把，记录一下以前的计算结果，恩恩，非常明显O(n^3*m^3)了……，当然，这还是不能接受的，我们还是坐下来谈谈动态规划吧，说实话，我没有想出来什么好的动态规划的方法，我能想到的方法最坏情况下还是能到O(n^3*m^3)的，当然，我也就没闲心去计算它的平均复杂度了，于是找“度娘”请教了一把动态规划的方法，好像看明白了。于是玩命儿码代码，然后就是“第二天”了……

　　代码加在一起实在是有点儿略长了，又是在第一个的基础上面改的，代码活生生就是一坨翔的感觉了，而且下面还有好长的路要走的！，不管怎么样，还是贴出来看一看，可能有些变量是全局变量，有些变量是在main函数里面，找起来好费劲的

　　在main函数中：

 　　　　if(getsmatrix(in,row,column)==)
         {
             system("pause");
             return ;
         }
         printf("MaxSubmatrix:%d",MaxStep2(row,column));
         system("pause");
         return ;

　　getsmatric函数：

 int getsmatrix(FILE *in,int row, int column)
 {
     int i,j,endflag;
     char c;
     for(i=,endflag=;i<row;i++)
     {
         for(j=;j<column;j++)
         {

             endflag=fscanf(in,"%d",&smatrix[i][j]);
             if(smatrix[i][j]>Max||smatrix[i][j]<Min)
             {
                 printf("Please! I can't handle that");
                 //system("pause");
                 return ;
             }
             if(endflag==)
             {
                 printf("Matrix number illegal!");
                 //system("pause");
                 return ;
             }
             if(endflag==EOF)
                 break;
             c=fgetc(in);
             if(c!=',')
                 if(j!=column-)
                 {
                     printf("Shit problem!");
                     //system("pause");
                     return ;
                 }
                 else
                     break;
             //printf("%d%c",matrix[i][j],c);
         }
         if(endflag==EOF)
             if(i!=row-)
             {
                 printf("Shit problem!");
                 //system("pause");
                 return ;
             }
             else
                 break;
     }
     return ;
 }

　　（PS：这个函数是专门为非特别大的数准备的，我一直很怀疑long long型的变量计算起来会多消耗不止一两倍的时间，于是搞了一份int型的，毕竟超时死得更惨烈一些）

　　MaxStep2函数：

 int MaxStep2(int row, int column)
 {
     int i,j,k,tempsub,maxsub,temparray[];
     //calculate sub;
     //memset(smatrix,0,sizeof(smatrix));
     for(i=;i<row;i++)
     {
         for(j=;j<column;j++)
             if(i==)
                 record[i][j]=smatrix[i][j];
             else
                 record[i][j]=record[i-][j]+smatrix[i][j];
     }
     for(i=,maxsub=smatrix[][];i<row;i++)
     {
         for(j=;j<=i;j++)
         {
             if(j==)
                 tempsub=MaxSubarr(record[i],column);
             else
             {
                 for(k=;k<column;k++)
                     temparray[k]=record[i][k]-record[j-][k];
                 tempsub=MaxSubarr(temparray,column);
             }
             maxsub=MyMax(tempsub,maxsub);
         }
     }
     return maxsub;
 }

测试数据1：

3,
6,
5,6,-3,8,-9,2
1,-12,20,0,-3,-5
-9,-7,-3,6,7,-1

测试结果：　

　

测试数据2：

8,
12,
8,-10,-3,26,-11,-1,-6,12,17,6,28,4
20,-13,-20,-13,-15,-254,5,8,9,-4,-9,29
-11,18,-25,9,12,-9,-2,23,8,-1,3,-14
-16,-7,0,201,-1,309,3,6,-18,11,24,-8
-1,-7,11,100,21,292,-2,2,-18,-8,-10,9
26,-11,-19,-18,20,-981,2,-14,12,-14,1,27
9,-20,5,28,-15,26,-20,-8,-16,30,3,20
-6,-7,-5,-9,-16,-15,5,-16,22,-17,11,-18

　　测试结果2:

阶段三：

第一步：

　　在我还在做第一次作业的时候，肖神就已经在群里吵吵这个阶段不好做了，我记得当时大家在群里嚷嚷着要用状压DP、插头DP什么的，更有好事儿的还证明了一下这个问题是个NP，至少是个NPC问题，我勒个去的，他们好歹也都是搞ACM的，我等弱还是先绕路而行吧！

　　我对这个题的一系列YY，因为大神们都说了要连通性状压DP了，而且都指数级复杂度了，我就不花时间琢磨精确解的事儿了，让我得出精确解，无非直接枚举——>判断连通性——>……然后复杂度很现实O(2^(m*n)*m*n)；然后，剩下就是回溯搜索+剪枝了，因为利用连通性进行剪枝，相比于第一种做法优化效果还是很明显的，而且效果会随着矩阵的增大而更加明显。于是我就黔驴技穷了……

　　当然，我就考虑“牺牲精度”了，当时跟鲁大师讨论这个问题，我说：“直接贪心一个次优解吧”，大师说：“那就是n优解了”……于是，我就考虑用贪心做了，贪心出来一个“次的n次方优解”还是可以接受的。我的贪心策略：利用规则子矩阵得到一个解——>对子矩阵轮廓进行扩展，加入邻接正值，删除边上负值……

 void MaxStep3(FILE *in,int row, int column)
 {
     int i,j,k,tempsub,maxsub,temparray[Max_C],cstart,cend,rstart,rend;
     struct SubarrayInfo sub;
     if(getsmatrix(in,row,column)==)
         return ;
     //calculate sub;
     for(i=;i<row;i++)
     {
         for(j=;j<column;j++)
             if(i==)
                 record[i][j]=smatrix[i][j];
             else
                 record[i][j]=record[i-][j]+smatrix[i][j];
     }
     for(i=,maxsub=smatrix[][];i<row;i++)
     {
         for(j=;j<=i;j++)
         {
             if(j==)
             {
                 sub=IMaxSub(record[i],column);
                 tempsub=sub.max;
             }
             else
             {
                 for(k=;k<column;k++)
                     temparray[k]=record[i][k]-record[j-][k];
                 sub=IMaxSub(temparray,column);
                 tempsub=sub.max;
             }
             if(tempsub>maxsub)
             {
                 maxsub=tempsub;
                 cstart=sub.start;
                 cend=sub.end;
                 rstart=j;
                 rend=i;
             }
         }
     }
     maxsub=AMaxSub(rstart,rend,cstart,cend,row,column,maxsub);
     printf("Step3---MaxSubmatrix:%d",maxsub);
 }
 struct SubarrayInfo IMaxSub(int *a,int n)
 {
     int tempsub,maxsub,start,tempstart=,end;
     int i;
     struct SubarrayInfo sub;
     tempsub=;
     maxsub=a[n-];
     for(i=;i<n;i++)
     {
         if(tempsub+a[i]<a[i])
         {
             tempstart=i;
             tempsub=a[i];
         }
         else
             tempsub+=a[i];
         if(tempsub>maxsub)
         {
             maxsub=tempsub;
             start=tempstart;
             end=i;
         }
     }
     sub.max=maxsub;
     sub.start=start;
     sub.end=end;
     return sub;
 }
 int AMaxSub(int rstart,int rend,int cstart,int cend,int row,int column,int maxsub)
 {
     int flag[Max_R][Max_C],i,j;
     memset(flag,,sizeof(flag));
     for(i=rstart;i<=rend;i++)
         for(j=cstart;j<=cend;j++)
             flag[i][j]=;
     while(rstart>||rend<row-||cstart>||cend<column-)
     {
         if(rstart>)
             for(rstart--,i=cstart;i<column&&i<=cend&&i<column;i++)
                 if(flag[rstart+][i]==&&smatrix[rstart][i]>=)
                 {
                     flag[rstart][i]=;
                     maxsub+=smatrix[rstart][i];
                 }
         if(rend<row-)
             for(rend++,i=cstart;i<=cend&&i<column;i++)
                 if(flag[rend-][i]==&&smatrix[rend][i]>+)
                 {
                     flag[rend][i]=;
                     maxsub+=smatrix[rend][i];
                 }
         if(cstart>)
             for(cstart--,j=rstart;j<=rend&&j<row;j++)
                 if(flag[cstart-][j]==&&smatrix[cstart][j]>=)
                 {
                     flag[cstart][j]=;
                     maxsub+=smatrix[cstart][j];
                 }
         if(cend<column-)
             for(cend++,j=rstart;j<=rend&&j<row;j++)
                 if(flag[cend+][j]==&&smatrix[cend][j]>=)
                 {
                     flag[cend][j]=;
                     maxsub+=smatrix[cend][j];
                 }
     }
     return maxsub;
 }

3,
6,
5,6,-3,8,-9,2
-1,-12,20,0,-3,-5
-9,-7,-3,6,7,-1,

　　（PS：陈丹琦老师的论文和ppt一时半会儿是看不懂了，等我从状压DP到连通性状压DP啃一遍再来补大神们的实现方案）

阶段四：

第一步：

　　分析一下这个问题，看着好像挺玄乎的，好好的一个矩阵还要给人连起来，弄得没法下嘴开个口来做这个题，同时当时纠结在这个“在3的基础上”会不会也要求要不规则额？？？那岂不是死翘翘的节奏了。当然，后来鲁大师说这疑问还是挺水的，于是就默认矩阵是规则的了。突破口还是在一维上，只不过先把圆圈剪开，然后扫就好了，至于怎么剪，我打算把数组按照正负相间的子段进行合并，当然，把首位两部分同号的合并，于是：

　　输入：5,6，-3,8，-9,2

　　处理：13，-3,8-9

　　对了？

　　高兴太早了，这样还是没有完全剪断前后的联系的……

　　于是，继续想，只能把每个数当头分别扫面一遍了，如果时间承受不了，可以用上面的方法优化一下长度。同理可解决垂直。

第二步：

　　终于算是高出来一个"/h“

　　照例，贴上源代码+部分测试

 void MaxStep4H(FILE *in,int row, int column)
 {
     int i,j,k,tempsub,maxsub,temparray[];
     if(getsmatrix(in,row,column)==)
         return ;
     //calculate sub;
     //memset(smatrix,0,sizeof(smatrix));
     for(i=;i<row;i++)
     {
         for(j=;j<column;j++)
             if(i==)
                 record[i][j]=smatrix[i][j];
             else
                 record[i][j]=record[i-][j]+smatrix[i][j];
     }
     for(i=,maxsub=smatrix[][];i<row;i++)
     {
         for(j=;j<=i;j++)
         {
             if(j==)
                 tempsub=LMaxSubarr(record[i],column);
             else
             {
                 for(k=;k<column;k++)
                     temparray[k]=record[i][k]-record[j-][k];
                 tempsub=LMaxSubarr(temparray,column);
             }
             maxsub=MyMax(tempsub,maxsub);
         }
     }
     printf("Step4H---MaxSubmatrix:%d",maxsub);
 }
 int LMaxSubarr(int *a, int n)
 {
     int tempsub,maxsub,doua[];
     int i,j;
     for(i=;i<n;i++)
         doua[i]=a[i];
     for(j=;i<*n;j++,i++)
         doua[i]=a[j];
     maxsub=a[n-];
     for(i=;i<n;i++)
         for(j=i,tempsub=;j<i+n;j++)
         {
             tempsub=MyMax(tempsub+doua[j],doua[j]);
             if(tempsub>maxsub)
                 maxsub=tempsub;
         }
     return maxsub;
 }

测试样例：

1,

6,

5,6,-3,8,-9,2

　　测试结果：

第三步：

　　02:32:49

　　实在是有点儿早了，再熬我就实在饿得受不了了，贴上垂直的代码和测试，明天继续！

 void MaxStep4V(FILE *in,int row, int column)
 {
     int i,j,l,temp[*Max_R][Max_C],maxsub,tempsub;
     if(getsmatrix(in,row,column)==)
         return ;
     for(i=;i<row;i++)
         for(j=;j<column;j++)
             temp[i][j]=smatrix[i][j];
     for(l=;i<*row;i++,l++)
         for(j=;j<column;j++)
             temp[i][j]=smatrix[l][j];
     //calculate sub;
     //memset(smatrix,0,sizeof(smatrix));
     for(i=,maxsub=smatrix[][];i<row;i++)
     {
         tempsub=NMaxStep2(temp,row,column,i);
         maxsub=MyMax(tempsub,maxsub);
     }
     printf("Step4V---MaxSubmatrix:%d",maxsub);
 }
 int NMaxStep2(int a[][Max_C],int row,int column,int start)
 {
     int i,j,k,tempsub,maxsub,temparray[Max_C];
     //calculate sub;
     for(i=start,k=;i<start+row;i++,k++)
     {
         for(j=;j<column;j++)
             if(i==start)
                 record[k][j]=a[i][j];
             else
                 record[k][j]=record[k-][j]+a[i][j];
     }
     //printf("%d",record[start][0]);
     for(i=,maxsub=smatrix[][];i<row;i++)
     {
         for(j=;j<=i;j++)
         {
             if(j==)
                 tempsub=MaxSubarr(record[i],column);
             else
             {
                 for(k=;k<column;k++)
                     temparray[k]=record[i][k]-record[j-][k];
                 tempsub=MaxSubarr(temparray,column);
             }
             maxsub=MyMax(tempsub,maxsub);
         }
     }
     return maxsub;
 }

测试数据：

3,
6,
5,6,-3,8,-9,2
-10,-10,-10,-10,-9,-9
-7,8,4,7,-9,3

　　输出结果：

阶段五：

　　这步如果只是一个规则的轮胎，那么好吧，把上一步的成果用一下的OK了，

　　就改了几个字母，太饿了，不测试了！！！明天还要搞状压DP呢！！！还要弄单元测试！！！啊啊啊！！！！

 void MaxStep5(FILE *in,int row, int column)
 {
     int i,j,l,temp[*Max_R][Max_C],maxsub,tempsub;
     if(getsmatrix(in,row,column)==)
         return ;
     for(i=;i<row;i++)
         for(j=;j<column;j++)
             temp[i][j]=smatrix[i][j];
     for(l=;i<*row;i++,l++)
         for(j=;j<column;j++)
             temp[i][j]=smatrix[l][j];
     //calculate sub;
     //memset(smatrix,0,sizeof(smatrix));
     for(i=,maxsub=smatrix[][];i<row;i++)
     {
         tempsub=NMaxStep2(temp,row,column,i);
         maxsub=MyMax(tempsub,maxsub);
     }
     printf("Step4V---MaxSubmatrix:%d",maxsub);
 }
 int NMaxStep3(int a[][Max_C],int row,int column,int start)
 {
     int i,j,k,tempsub,maxsub,temparray[Max_C];
     //calculate sub;
     for(i=start,k=;i<start+row;i++,k++)
     {
         for(j=;j<column;j++)
             if(i==start)
                 record[k][j]=a[i][j];
             else
                 record[k][j]=record[k-][j]+a[i][j];
     }
     //printf("%d",record[start][0]);
     for(i=,maxsub=smatrix[][];i<row;i++)
     {
         for(j=;j<=i;j++)
         {
             if(j==)
                 tempsub=LMaxSubarr(record[i],column);
             else
             {
                 for(k=;k<column;k++)
                     temparray[k]=record[i][k]-record[j-][k];
                 tempsub=LMaxSubarr(temparray,column);
             }
             maxsub=MyMax(tempsub,maxsub);
         }
     }
     return maxsub;
 }

感想收获：

　　不得不说，这就一门C语言用得还凑合实在是受不了（le），我要尝试一下C++甚至C#，以前都接触过一点点，不用就扔了；这C语言学得也是很渣，要是有函数指针什么的，代码不会搞得这么多；学一学算法吧，看着大神们张嘴就各种DP各种复杂度，感觉自己太次了。

　　还差一个单元测试！！！！