Q：描述在这么多相似的需求面前, 你怎么维护你的设计 (父类/子类/基类, UML, 设计模式, 或者其它方法) 让整个程序的架构不至于崩溃的?
A：由于使用的是面向过程的C语言，所以维护设计这个问题，更多的是通过调试
Q:给出你做单元测试/代码覆盖率的最终覆盖率的报告, 用截屏显示你的代码覆盖率
A:......我用的GCC工具似乎不具有代码覆盖率检查的功能。。。。
Q:阅读 工程师的能力评估和发展 和相关文章, 在完成作业的时候记录自己花费的时间, 并填下表。如果你对有些术语不太清楚，请查看教材和其它资料。如果你认为你不需要做某个步骤, 那就跳过去。
|
Personal Software Process Stages |
时间百分比(%) |
实际花费的时间 (分钟) |
原来估计的时间 (分钟) |
|
|
计划 |
||||
|
· 估计这个任务需要多少时间，把工作细化并大致排序 |
0 | 0 | 0 | |
|
开发 |
||||
|
· 需求分析 (包括学习新技术) |
5 | 30min | 0 | |
|
· 生成设计文档 |
0 | 0 | 0 | |
|
· 设计复审 (和同事审核设计文档) |
0 | 0 | 0 | |
|
· 代码规范 (制定合适的规范) |
0 | 0 | 0 | |
|
· 具体设计 |
55 | 10h | 4h | |
|
· 具体编码 |
20 | 4h | 4h | |
|
· 代码复审 |
5 | 1h | 30min | |
|
· 测试（自我测试，修改代码，提交修改） |
15 | 3h | 1h | |
|
总结报告 |
||||
| Total | 总计 | 100% | 总用时 | 总估计的用时 |
Q:你在这个作业中学到了什么? 有什么好的设计值得分享? 感想如何 (太容易 / 太难 / 太无趣)?
A:学到了关于命令行的使用，感想就是：太难！
1. 开始之前
在一维的求解中，我们已经知：
假设f[i]表示：1..i这个序列中，包含i这个元素的最大连续序列之和
显然 f[1]=a[1];
f[i]=f[i-1]+a[i]; f[i-1]>0
f[i]=a[i]; f[i-1]<=0
max(f[i])即为最后的结果
2. 二维数组的最大子矩阵
这里假设输入的矩阵为P，行和列值分别约定为m,n
对于2维数组，我们虽然无法直接使用1维中的思路
但是，如果我们可以把一整行看做一个元素
按照1维的思路，我们就可以得到一个最大的n*x的矩阵A，0<x<m
显然A不一定是最后的答案，因为矩阵A的列值y被我们限定为了n
所以我们需要枚举y，即y←1..n
之后要做的就很简单了
枚举行值等于m，列值为y，的所有矩阵D，并找出D中的最大子矩阵E
对于所有的E，max（E）就是最后的答案
时间复杂度=T[求1维最大子数组]*T[枚举矩阵]*T[计算矩阵每一行的值]
前者已知为O(n)
枚举矩阵则需要一个二重的循环，即为O(n^2)
对于计算矩阵D中没一行的值
我们可以进行预处理
假设D在P中的位置为：第x列→第y列
如果我们用一个数组g[i][j]表示：第i行的1..j列的元素之和为g[i][j]；
则对于D中的每一行的和应该为g[i][y]-g[i][x],(0<i<=m)
每次计算的复杂度为O(1)
所以总的时间复杂度为：O(N^3)
空间复杂度：
主要用于存储P,D,E
为：O(n^2
3. 二维数组的最大子矩阵(连通)
联通问题，和不连通的区别只是：边界的连续性问题
因此我们只需增加三个同样的矩阵P1,P2,P3
排列为:
P（原矩阵） P2（如果水平联通）
P1(如果垂直联通) P3（如果同时联通）
按照第二步的思路，同时保证所枚举的矩阵D
行值小于m，列值小于 n
即可求出起解
时间复杂度和空间复杂度同二
时间复杂度为： O(N^3)
空间复杂度： O(n^2)
4. 二维数组的最大连通图形
对于此问题，我暂时想不到更好的解决办法
只能通过递归生成所有联通图形，求解最大值
时间效率相当之低：
O(2^(m*n))
#include <stdio.h>
#include <string.h>
#define M 100
#define max(a,b) (a)>(b)?(a):(b)
#define sinput "input.txt" FILE *file;
int a[M][M],i,j,m,n,s;
int color[M][M];
int dx[]={-,,,},dy[]={,-,,}; void F()
{
int g[M][M],f[M][M],i,j,s,x,k;
for(i=;i<m;i++)
for(j=;j<n;j++) f[i][j]=g[i][j]=; s=a[][]; for(i=;i<m;i++){
g[i][]=a[i][];
for(j=;j<n;j++) g[i][j]=g[i][j-]+a[i][j];
} for(i=;i<m;i++)
for(j=;j<n;j++)
for(k=j;k<n;k++){
x=g[i][k]-g[i][j]+a[i][j];
if(f[j][k]>) f[j][k]+=x;
else f[j][k]=x;
if(f[j][k]>s) s=f[j][k];
}
printf("%d",s);
} void Fvh(int v,int h)
{
int g[M][M],f[M][M],l[M][M],i,j,s,aa[M][M],nn,mm,nx,x,k,; nn=n;
mm=m; if(h) nn=*n;
if(v) mm=*m; for(i=;i<mm;i++)
for(j=;j<nn;j++){
aa[i][j]=a[i%m][j%n];
l[j][k]=f[i][j]=g[i][j]=;
} s=a[][]; for(i=;i<mm;i++){
g[i][]=aa[i][];
for(j=;j<nn;j++) g[i][j]=g[i][j-]+aa[i][j];
} for(i=;i<mm;i++)
for(j=;j<nn;j++)
for(k=j,nx=;k<nn;k++,nx++){ if(nx>=n) break; x=g[i][k]-g[i][j]+aa[i][j]; if(f[j][k]>&&l[j][k]<m){
f[j][k]+=x;
l[j][k]++;
}
else{
f[j][k]=x;
l[j][k]=;
} if(f[j][k]>s) s=f[j][k]; }
printf("%d",s); } int IsInvh(int x,int y)
{
if(x>=&&x<m&&y>=&&y<n) return ;
return ;
} void fany(int x,int y,int z)
{
int tx,ty,i; if(s<z) s=z;
for(i=;i<;i++){
tx=x+dx[i];
ty=y+dy[i];
if(IsInvh(tx,ty)&&!color[tx][ty]){
color[tx][ty]=;
fany(tx,ty,z+a[tx][ty]);
color[tx][ty]=;
}
}
} main(int N,char **CMD)
{
int h,v,u;
u=h=v=;
file=fopen(sinput,"r");
fscanf(file,"%d, %d, ",&m,&n);
for(i=;i<m;i++)
for(j=;j<n;j++) fscanf(file,"%d, ",a[i]+j); fclose(file);
for(i=;i<N;i++){
if(!strcmp(CMD[i],"/h")) h=;
if(!strcmp(CMD[i],"/v")) v=;
if(!strcmp(CMD[i],"/a")) u=;
} if(!(h+v)&&!u){
F();
return ;
}
if(!u){
Fvh(v,h);
return ;
} for(i=;i<m;i++)
for(j=;j<n;j++){
color[i][j]=;
fany(i,j,a[i][j]);
color[i][j]=;
}
printf("%d",s); }