算法分析与设计实验报告一

华中科技大学算法分析与设计实验报告学生姓名：庞亮系别：软件学院专业与班号：软件工程0805学号：U200818042实验时间：第二周，星期三，晚上实验房间号：软件学院五楼机房[实验名称]Strassen’s矩阵乘法和最近点对算法[实验目的]1、理解“分治法”算法设计思想及其实现步骤2、掌握分治算法效率递归分析方法3、掌握主方式求解递归式方法[实验条件]硬件：计算机软件：计算机程序语言开发平台，如C、C++、Java、Matlab。学生：至少掌握一门计算机程序设计语言，如C、C++、Java、Matlab。[实验内容及要求]1、利用计算机程序设计语言，实现教材第28.2章介绍的“Strassen’s矩阵乘法算法”，自主生成两个8×8的矩阵，检验算法的正确性并输出算法结果。2、比较Strassen’s矩阵乘法算法和数学定义的矩阵乘法算法效率之间的区别，并用直观的表达方式把两种不同矩阵乘法的效率随矩阵维数的变化趋势。3、利用计算机程序设计语言，实现教材第33.4章介绍的“最近点对算法”，在拟定的二维空间点集上检验算法的正确性并输出算法结果。[实验原理]1.Strassen’s矩阵乘法简介Strassen’s算法是将矩阵分成了如图所示的均等的四块。分后的每一块儿任然还是方阵。所以可以由大问题分解成若干子问题进行解决。为了能使子问题能够返回到原始问题。Strassen‘s算法提出了如下的计算公式，可以用矩阵的子矩阵计算出S1-S7，然后又由S1-S7合成原始矩阵。而S1-S7的计算又是方阵的乘法。由此使用分治算法便可以解决问题。2.最近点对问题(ClosestPairProblems)算法简介首先这个问题也是采用了分治的思想，将空间内的距离分成三类，分界线左边的点之间的距离，分界线右边的点之间的距离，还有分界线两边距离为D的区域内的两点间距离。[算法具体代码]1.矩阵相乘问题//Strassen.cpp:定义控制台应用程序的入口点。////********************************************************************************#includestdafx.h#includestdlib.h#defineAMCopy(A,0,0,A.v/2)#defineBMCopy(A,A.v/2,0,A.v/2)#defineCMCopy(A,0,A.v/2,A.v/2)#defineDMCopy(A,A.v/2,A.v/2,A.v/2)#defineEMCopy(B,0,0,B.v/2)#defineFMCopy(B,B.v/2,0,B.v/2)#defineGMCopy(B,0,B.v/2,B.v/2)#defineHMCopy(B,B.v/2,B.v/2,B.v/2)#defineV2//********************************************************************************//矩阵结构typedefstructmatrix{intv;intx[16][16];}Matrix;//********************************************************************************//输入输出文件FILE*fout;FILE*fin;//********************************************************************************//矩阵打印（文件）voidfPrint(MatrixA){for(intj=0;jA.v;j++){for(inti=0;iA.v;i++){fprintf(fout,%d,A.x[i][j]);}fprintf(fout,\n);}}//********************************************************************************//矩阵打印（屏幕）voidPrint(MatrixA){for(intj=0;jA.v;j++){for(inti=0;iA.v;i++){printf(%d,A.x[i][j]);}printf(\n);}}//********************************************************************************//矩阵截取MatrixCopy(MatrixX,intx,inty,intv){Matrixtemp;temp.v=v;for(inti=x;ix+v;i++){for(intj=y;jy+v;j++){temp.x[i-x][j-y]=X.x[i][j];}}returntemp;}//********************************************************************************//矩阵相减MatrixMinus(MatrixA,MatrixB){Matrixtemp;temp.v=A.v;for(intj=0;jA.v;j++){for(inti=0;iA.v;i++){temp.x[i][j]=A.x[i][j]-B.x[i][j];}}returntemp;}//********************************************************************************//矩阵相加MatrixPlus(MatrixA,MatrixB){Matrixtemp;temp.v=A.v;for(intj=0;jA.v;j++){for(inti=0;iA.v;i++){temp.x[i][j]=A.x[i][j]+B.x[i][j];}}returntemp;}//A:Copy(A,0,0,A.v/2)//B:Copy(A,A.v/2,0,A.v/2)//C:Copy(A,0,A.v/2,A.v/2)//D:Copy(A,A.v/2,A.v/2,A.v/2);//E:Copy(B,0,0,B.v/2)//F:Copy(B,B.v/2,0,B.v/2)//G:Copy(B,0,B.v/2,B.v/2)//H:Copy(B,B.v/2,B.v/2,B.v/2);//********************************************************************************//矩阵合并MatrixMerge4(MatrixA,MatrixB,MatrixC,MatrixD){Matrixtemp;temp.v=A.v*2;for(inti=0;iA.v;i++){for(intj=0;jA.v;j++){temp.x[i][j]=A.x[i][j];}}for(inti=0;iB.v;i++){for(intj=0;jB.v;j++){temp.x[i+B.v][j]=B.x[i][j];}}for(inti=0;iC.v;i++){for(intj=0;jC.v;j++){temp.x[i][j+C.v]=C.x[i][j];}}for(inti=0;iD.v;i++){for(intj=0;jD.v;j++){temp.x[i+D.v][j+D.v]=D.x[i][j];}}returntemp;}//********************************************************************************//矩阵相乘MatrixMutiply(MatrixA,MatrixB){if(A.v==1&&B.v==1){A.x[0][0]=A.x[0][0]*B.x[0][0];returnA;}Matrixs1,s2,s3,s4,s5,s6,s7;s1=Mutiply(AM,Minus(FM,HM));s2=Mutiply(Plus(AM,BM),HM);s3=Mutiply(Plus(CM,DM),EM);s4=Mutiply(DM,Minus(GM,EM));s5=Mutiply(Plus(AM,DM),Plus(EM,HM));s6=Mutiply(Minus(BM,DM),Plus(GM,HM));s7=Mutiply(Minus(AM,CM),Plus(EM,FM));fPrint(Plus(Plus(s5,s6),Minus(s4,s2)));fPrint(Plus(s1,s2));fPrint(Plus(s3,s4));fPrint(Minus(Minus(s1,s7),Minus(s3,s5)));returnMerge4(Plus(Plus(s5,s6),Minus(s4,s2)),Plus(s1,s2),Plus(s3,s4),Minus(Minus(s1,s7),Minus(s3,s5)));}//********************************************************************************//数据输入MatrixRnMatrix(intv){Matrixtemp;temp.v=v;for(intj=0;jV;j++){for(inti=0;iV;i++){fscanf(fin,%d,&temp.x[i][j]);//1;//rand()%10;}}returntemp;}//********************************************************************************//入口函数int_tmain(intargc,_TCHAR*argv[]){fout=fopen(out.txt,w);fin=fopen(in.txt,r);MatrixA,B;A.v=V;B.v=V;A=RnMatrix(V);B=RnMatrix(V);fclose(fin);Print(Mutiply(A,B));getchar();return0;}2.最近点问题//Closest_Pair_Problems.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includestdlib.htypedefstructpoint{intx;inty;}Point;FILE*fin;FILE*fout;intn;Pointp_set_x[100];Pointp_set_y[100];intCompare_x(constvoid*p1,constvoid*p2){return((Point*)p1)-x((Point*)p2)-x?1:-1;}intCompare_y(constvoid*p1,constvoid*p2){return((Point*)p1)-y((Point*)p2)-y?1:-1;}voidSort_xy(){qsort(p_set_x,n,sizeof(Point),Compare_x);qsort(p_set_y,n,sizeof(Point),Compare_y);}voiddata_from_file(){fin=fopen(in.txt,r);fscanf(fin,%d,&n);for(inti=0;in;i++){fscanf(fin,%d%d,&p_set_x[i].x,&p_set_x[i].y);p_set_y[i].x=p_set_x[i].x;p_set_y[i].y=p_set_x[i].y;}fclose(fin);}doubledistance(inta,intb){return(p_set_x[a].x-p_se