算法分析与设计实验报告一(共12页).docx
《算法分析与设计实验报告一(共12页).docx》由会员分享,可在线阅读,更多相关《算法分析与设计实验报告一(共12页).docx(11页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上华中科技大学 算法分析与设计实验报告学生姓名:庞 亮 系别:软件学院 专业与班号:软件工程0805学号:U实验时间:第 二 周,星期三 ,晚上 实验房间号:软件学院五楼机房实验名称Strassens 矩阵乘法和最近点对算法实验目的1、理解“分治法”算法设计思想及其实现步骤2、掌握分治算法效率递归分析方法3、掌握主方式求解递归式方法实验条件硬件:计算机软件:计算机程序语言开发平台,如C、C+、Java、Matlab。学生:至少掌握一门计算机程序设计语言,如C、C+、Java、Matlab。实验内容及要求1、利用计算机程序设计语言,实现教材第28.2 章介绍的“Stras
2、sens 矩阵乘法算法”,自主生成两个88 的矩阵,检验算法的正确性并输出算法结果。2、比较 Strassens 矩阵乘法算法和数学定义的矩阵乘法算法效率之间的区别,并用直观的表达方式把两种不同矩阵乘法的效率随矩阵维数的变化趋势。3、利用计算机程序设计语言,实现教材第33.4 章介绍的“最近点对算法”,在拟定的二维空间点集上检验算法的正确性并输出算法结果。实验原理1. Strassens矩阵乘法简介Strassens算法是将矩阵分成了如图所示的均等的四块。分后的每一块儿任然还是方阵。所以可以由大问题分解成若干子问题进行解决。为了能使子问题能够返回到原始问题。 Strassens算法提出了如下的
3、计算公式,可以用矩阵的子矩阵计算出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)#defin
4、e 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 matrixint v;int x1616;Matrix; /*/输入输出文件FILE *
5、fout;FILE *fin;/*/矩阵打印(文件)void fPrint(Matrix A)for(int j=0;jA.v;j+)for(int i=0;iA.v;i+)fprintf(fout,%d ,A.xij);fprintf(fout,n);/*/矩阵打印(屏幕)void Print(Matrix A)for(int j=0;jA.v;j+)for(int i=0;iA.v;i+)printf(%d ,A.xij);printf(n);/*/矩阵截取Matrix Copy(Matrix X,int x,int y,int v)Matrix temp;temp.v=v;for(int
6、 i=x;ix+v;i+)for(int j=y;jy+v;j+)temp.xi-xj-y=X.xij;return temp;/*/矩阵相减Matrix Minus(Matrix A,Matrix B)Matrix temp;temp.v=A.v;for(int j=0;jA.v;j+)for(int i=0;iA.v;i+)temp.xij=A.xij-B.xij;return temp;/*/矩阵相加Matrix Plus(Matrix A,Matrix B)Matrix temp;temp.v=A.v;for(int j=0;jA.v;j+)for(int i=0;iA.v;i+)te
7、mp.xij=A.xij+B.xij;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 tem
8、p;temp.v=A.v*2;for(int i=0;iA.v;i+)for(int j=0;jA.v;j+)temp.xij=A.xij;for(int i=0;iB.v;i+)for(int j=0;jB.v;j+)temp.xi+B.vj=B.xij;for(int i=0;iC.v;i+)for(int j=0;jC.v;j+)temp.xij+C.v=C.xij;for(int i=0;iD.v;i+)for(int j=0;jD.v;j+)temp.xi+D.vj+D.v=D.xij;return temp;/*/矩阵相乘Matrix Mutiply(Matrix A,Matrix
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 设计 实验 报告 12
限制150内