华中科技大学算法分析与设计实验报告学生姓名：庞亮系别：软件学院专业与班号：软件工程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.最近点对问题(Closest Pair Problems)算法简介首先这个问题也是采用了分治的思想，将空间内的距离分成三类，分界线左边的点之间的距离，分界线右边的点之间的距离，还有分界线两边距离为D 的区域内的两点间距离。

[算法具体代码]1.矩阵相乘问题// Strassen.cpp : 定义控制台应用程序的入口点。

////********************************************************************************#include"stdafx.h"#include"stdlib.h"#define AM Copy(A,0,0,A.v/2)#define BM Copy(A,A.v/2,0,A.v/2)#define CM Copy(A,0,A.v/2,A.v/2)#define DM Copy(A,A.v/2,A.v/2,A.v/2)#define EM Copy(B,0,0,B.v/2)#define FM Copy(B,B.v/2,0,B.v/2)#define GM Copy(B,0,B.v/2,B.v/2)#define HM Copy(B,B.v/2,B.v/2,B.v/2)#define V 2//********************************************************************************//矩阵结构typedef struct matrix{int v;int x[16][16];}Matrix;//******************************************************************************** //输入输出文件FILE *fout;FILE *fin;//******************************************************************************** //矩阵打印（文件）void fPrint(Matrix A){for(int j=0;j<A.v;j++){for(int i=0;i<A.v;i++){fprintf(fout,"%d ",A.x[i][j]);}fprintf(fout,"\n");}}//******************************************************************************** //矩阵打印（屏幕）void Print(Matrix A){for(int j=0;j<A.v;j++){for(int i=0;i<A.v;i++){printf("%d ",A.x[i][j]);}printf("\n");}}//******************************************************************************** //矩阵截取Matrix Copy(Matrix X,int x,int y,int v){Matrix temp;temp.v=v;for(int i=x;i<x+v;i++){for(int j=y;j<y+v;j++){temp.x[i-x][j-y]=X.x[i][j];}}return temp;}//******************************************************************************** //矩阵相减Matrix Minus(Matrix A,Matrix B){Matrix temp;temp.v=A.v;for(int j=0;j<A.v;j++){for(int i=0;i<A.v;i++){temp.x[i][j]=A.x[i][j]-B.x[i][j];}}return temp;}//******************************************************************************** //矩阵相加Matrix Plus(Matrix A,Matrix B){Matrix temp;temp.v=A.v;for(int j=0;j<A.v;j++){for(int i=0;i<A.v;i++){temp.x[i][j]=A.x[i][j]+B.x[i][j];}}return temp;}//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);//******************************************************************************** //矩阵合并Matrix Merge4(Matrix A,Matrix B,Matrix C,Matrix D){Matrix temp;temp.v=A.v*2;for(int i=0;i<A.v;i++){for(int j=0;j<A.v;j++){temp.x[i][j]=A.x[i][j];}}for(int i=0;i<B.v;i++){for(int j=0;j<B.v;j++){temp.x[i+B.v][j]=B.x[i][j];}}for(int i=0;i<C.v;i++){for(int j=0;j<C.v;j++){temp.x[i][j+C.v]=C.x[i][j];}}for(int i=0;i<D.v;i++){for(int j=0;j<D.v;j++){temp.x[i+D.v][j+D.v]=D.x[i][j];}}return temp;}//******************************************************************************** //矩阵相乘Matrix Mutiply(Matrix A,Matrix B){if(A.v==1 && B.v==1){A.x[0][0]=A.x[0][0]*B.x[0][0];return A;}Matrix s1,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 )));}//********************************************************************************//数据输入Matrix RnMatrix(int v){Matrix temp;temp.v=v;for(int j=0;j<V;j++){for(int i=0;i<V;i++){fscanf(fin,"%d",&temp.x[i][j]);//1;//rand()%10;}}return temp;}//********************************************************************************//入口函数int _tmain(int argc, _TCHAR* argv[])fout=fopen("out.txt","w");fin=fopen("in.txt","r");Matrix A,B;A.v=V;B.v=V;A=RnMatrix(V);B=RnMatrix(V);fclose(fin);Print(Mutiply(A,B));getchar();return 0;}2.最近点问题// Closest_Pair_Problems.cpp : 定义控制台应用程序的入口点。