一 实验题目
程序要使用的数组放在一个叫 input.txt 的文件中, 文件格式是:
1、数组的行数,
2、数组的列数,
3、每一行的元素, (用逗号分开)
4、每一个数字都是有符号32位整数, 当然, 行数和列数都是正整数。
5、例如下面的文件说明数组是有1行, 6列, 元素依次是: 5, 6, –3, 8, –9, 2
二 设计思路
1.1将所有可能的子矩阵进行遍历
1.2第一次子矩阵为1行1列时，将所有子矩阵进行遍历，求和，比较大小，求出max[1]；第二次子矩阵为1行2列时，将所有子矩阵进行遍历，求和，比较大小，求出max[2]；第三次子矩阵为1行3列时，将所有的子矩阵进行遍历，求和，比较大小，求出max[3]；…………第j*i次子矩阵为i行j列，将所有子矩阵进行遍历，求和，比较大小，求出max[i*j]。
1.3将所有的max[]进行比较大小
1.4根据每次求取最大值得到的位置计算出最大子数组左上角的行和列，并计算出子树组所有的行数和列数
1.5过程中将数据写入文件
三 源代码
#include<iostream>
#include<time.h>
#include<conio.h>
#include<fstream>
using namespace std;
void RandIn(int RowIntNum,int ColIntNum,int A[][100])
{
int IntCont;
for(int i=0;i<RowIntNum;i++)
{
for(int j=0;j<ColIntNum;j++)
{
IntCont=-(int)rand()%201+100;
A[i][j]=IntCont;
cout<<A[i][j]<<' ';
}
cout<<endl;
}
}
int MaxArray(int array[],int Maxsize,int &Location)
{
int max=array[0];
Location=0;//最大数值下标位置初始化
for(int i=0;i<Maxsize;i++)
{
if(max<array[i])
{
max=array[i];
Location=i;
}
}
return max;
}
void DivANum(int A[][100],int RowIntNum,int ColIntNum,int SubRowNum,int SubColNum,int EveTSum[],int &Location,int Times)
{
int sum[10000];
int ArrayNum=0;
//第times次的所有子矩阵
for(int row=0;row<RowIntNum-SubRowNum+1;row++)
{
for(int col=0;col<ColIntNum-SubColNum+1;col++)
{
sum[ArrayNum]=0;
//求子矩阵的和
for(int p=row;p<row+SubRowNum;p++)
{
for(int q=col;q<col+SubColNum;q++)
{
sum[ArrayNum]+=A[p][q];
}
}
ArrayNum++;
}
}
EveTSum[Times]=MaxArray(sum,ArrayNum,Location);
}
void main()
{
ofstream out;
out.open("text.txt");
srand((unsigned)time(NULL));
int Location[100];
int A[100][100],RowIntNum,ColIntNum;
int SubRowNum,SubColNum;
int max=0,LocTimes=0;
int EveTSum[10000];
int q=0,i,j;
int Row,Col,SetRow,SetCol;
while(q==0)
{
cout<<"请输入行数:";
cin>>RowIntNum;
out<<RowIntNum<<',';
cout<<"请输入列数:";
cin>>ColIntNum;
out<<ColIntNum<<','<<'
';
cout<<"整数内容"<<endl;
RandIn(RowIntNum,ColIntNum,A);
for(i=0;i<RowIntNum;i++)
{
for(j=0;j<ColIntNum;j++)
{
out<<A[i][j]<<',';
}
out<<'
';
}
for(SubRowNum=1;SubRowNum<=RowIntNum;SubRowNum++)
{
for(SubColNum=1;SubColNum<=ColIntNum;SubColNum++)
{
DivANum(A,RowIntNum,ColIntNum,SubRowNum,SubColNum,EveTSum,Location[(SubRowNum-1)*RowIntNum+SubColNum-1],(SubRowNum-1)*RowIntNum+SubColNum-1);
}
}
cout<<"输出最大矩阵的和"<<endl;
max=MaxArray(EveTSum,(SubRowNum-1)*(SubColNum-1),LocTimes);
Location[LocTimes]++;
cout<<max<<endl;
Row=LocTimes/ColIntNum+1;
Col=LocTimes%ColIntNum+1;
SetRow=(Location[LocTimes]-1)/(ColIntNum-Col+1);
SetCol=(Location[LocTimes]-1)%(ColIntNum-Col+1);
cout<<endl;
cout<<"输出最大矩阵"<<endl;
for(i=SetRow;i<SetRow+Row;i++)
{
for(j=SetCol;j<SetCol+Col;j++)
{
cout<<A[i][j]<<" ";
out<<A[i][j]<<' ';
}
cout<<endl;
out<<'
';
}
out.close();
cout<<"是否继续测试(输入0继续)"<<endl;
cin>>q;
system("cls");
}
}
四 程序截图
五 结对照片
左侧 崔乐乐（我） 右侧 黄晓飞
六 试验总结
实验虽然完成了，但是心情并不是很好，这些代码几天前就完成了。但是，想要将它改成java程序却做不到，原因有两点，一是java基础不是很好，二是java里的引用和C++里的引用并不一样，java里引用偏向于C++里指针的概念，还不知道怎样在java里将算法里引用主函数里的参数，我会继续寻找解决的办法，博客也就先到这里，所以未完待续；至于时间复杂度的问题，介于思路的盲区，要先将一维数组的博客改过来再对二维数组进行更改;最后要感谢结对的伙伴，在有限的时间里和我进行的激烈的讨论，加快了程序的进展