欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    算法分析与设计实验报告一(共12页).docx

    • 资源ID:14372664       资源大小:90.04KB        全文页数:11页
    • 资源格式: DOCX        下载积分:20金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要20金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    算法分析与设计实验报告一(共12页).docx

    精选优质文档-倾情为你奉上华中科技大学 算法分析与设计实验报告学生姓名:庞 亮 系别:软件学院 专业与班号:软件工程0805学号:U实验时间:第 二 周,星期三 ,晚上 实验房间号:软件学院五楼机房实验名称Strassens 矩阵乘法和最近点对算法实验目的1、理解“分治法”算法设计思想及其实现步骤2、掌握分治算法效率递归分析方法3、掌握主方式求解递归式方法实验条件硬件:计算机软件:计算机程序语言开发平台,如C、C+、Java、Matlab。学生:至少掌握一门计算机程序设计语言,如C、C+、Java、Matlab。实验内容及要求1、利用计算机程序设计语言,实现教材第28.2 章介绍的“Strassens 矩阵乘法算法”,自主生成两个8×8 的矩阵,检验算法的正确性并输出算法结果。2、比较 Strassens 矩阵乘法算法和数学定义的矩阵乘法算法效率之间的区别,并用直观的表达方式把两种不同矩阵乘法的效率随矩阵维数的变化趋势。3、利用计算机程序设计语言,实现教材第33.4 章介绍的“最近点对算法”,在拟定的二维空间点集上检验算法的正确性并输出算法结果。实验原理1. Strassens矩阵乘法简介Strassens算法是将矩阵分成了如图所示的均等的四块。分后的每一块儿任然还是方阵。所以可以由大问题分解成若干子问题进行解决。为了能使子问题能够返回到原始问题。 Strassens算法提出了如下的计算公式,可以用矩阵的子矩阵计算出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 matrixint v;int x1616;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.xij);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.xij);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.xi-xj-y=X.xij;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.xij=A.xij-B.xij;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.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 temp;temp.v=A.v*2;for(int i=0;i<A.v;i+)for(int j=0;j<A.v;j+)temp.xij=A.xij;for(int i=0;i<B.v;i+)for(int j=0;j<B.v;j+)temp.xi+B.vj=B.xij;for(int i=0;i<C.v;i+)for(int j=0;j<C.v;j+)temp.xij+C.v=C.xij;for(int i=0;i<D.v;i+)for(int j=0;j<D.v;j+)temp.xi+D.vj+D.v=D.xij;return temp;/*/矩阵相乘Matrix Mutiply(Matrix A,Matrix B)if(A.v=1 && B.v=1)A.x00=A.x00*B.x00;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);return Merge4(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.xij);/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 : 定义控制台应用程序的入口点。/#include "stdafx.h"#include "stdlib.h"typedef struct pointint x;int y;Point;FILE * fin;FILE * fout;int n;Point p_set_x100;Point p_set_y100;int Compare_x(const void * p1,const void * p2)return (Point *)p1)->x > (Point *)p2)->x ? 1 : -1;int Compare_y(const void * p1,const void * p2)return (Point *)p1)->y > (Point *)p2)->y ? 1 : -1;void Sort_xy()qsort(p_set_x,n,sizeof(Point),Compare_x);qsort(p_set_y,n,sizeof(Point),Compare_y);void data_from_file()fin=fopen("in.txt","r");fscanf(fin,"%d",&n);for(int i=0;i<n;i+)fscanf(fin,"%d %d",&p_set_xi.x,&p_set_xi.y);p_set_yi.x=p_set_xi.x;p_set_yi.y=p_set_xi.y;fclose(fin);double distance(int a,int b)return (p_set_xa.x-p_set_xb.x)*(p_set_xa.x-p_set_xb.x)+(p_set_xa.y-p_set_xb.y)*(p_set_xa.y-p_set_xb.y);double ClosestOf3(int s,int e)double min=65536e10;for(int i=s;i<=e;i+)for(int j=i+1;j<=e;j+)if(min>distance(i,j)min=distance(i,j);return min;double FindClosest(int s,int e)double dis1=65536e10,dis2=65536e10,dis;if(e-s+1<=3)return ClosestOf3(s,e);elseif(s<(s+e)/2)dis1=FindClosest(s,(s+e)/2);if(e>(s+e)/2)dis2=FindClosest(s+e)/2+1,e);dis=dis1>dis2 ? dis2:dis1;if(dis<0)printf("%d %d",s,e);int p,q;p=(s+e)/2;q=(s+e)/2;while(p_set_x(s+e)/2.x-p_set_xp.x<dis) if(p>s)p-;elsebreak;while(p_set_xq.x-p_set_x(s+e)/2.x<dis) if(q<e)q+;elsebreak;dis1=ClosestOf3(p,q);if(dis1<0)printf("%d %d",s,e);return dis1>dis ? dis:dis1;void ShowOut()for(int i=0;i<n;i+)printf("%d %d n",p_set_xi.x,p_set_xi.y);printf("%lf",FindClosest(0,n-1);int _tmain(int argc, _TCHAR* argv)data_from_file();Sort_xy();ShowOut();getchar();return 0;思考题1、 分治法算法设计思想的三个基本步骤是什么?如何证明分治算法的正确性?三个基本步骤:分解、解决、合并。用数学归纳发可以证明分治算法的正确性。2、 利用主方式求解 Strassens 矩阵乘法和最近点对算法效率的递归分析结果。Strassens矩阵乘法的递归式为Tn=7Tn2+(n2)主定理的公式为:所以由主定理得Tn=nlg73、解释怎样修改 Strassens 矩阵乘法算法,使得它也可以用于大小不必为2 的幂的矩阵?假设矩阵的大小为N,找一个2M使它是大于N的最小M值,此时将矩阵其他的部分填充0,使其变为一个2M大小的矩阵,然后就可以利用Strassens矩阵算法了。计算的结果取左上角的N的大小的矩阵,那就是矩阵乘法的结果。实验体会首先,说说Strassens矩阵乘法,在数学理论上,这个算法是十分优秀的,计算出来的界限明显比一般的靠定义计算要简单的多。但是,有一个问题,我想只要是写了这个程序的同学都知道,也就是这个程序如果计算很大的矩阵栈会溢出,这个我暂时无法解决。而且在计算小矩阵的使用由于用到了递归的方式,导致这个算法还没有定义法时间优秀。不过我想如果能计算很大的矩阵,当超过一定数值时,Strassens算法一定会比定义快。然后就是最近点对的算法,在刚刚看到这个题目的时候,大部分同学都会不由自主的选择比较任意两点的O(n2)复杂度的算法,但是如果仔细想一下会发现有许多点我们是不需要考虑的。于是我们会有O(nlgn)的算法。最近点对利用了分治的思想,将问题分而治之,不仅简化了问题的规模,而且也大大的减小了问题的复杂度。专心-专注-专业

    注意事项

    本文(算法分析与设计实验报告一(共12页).docx)为本站会员(飞****2)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开