《最大公约数的三种算法_复杂度分析_时间计算》由会员分享，可在线阅读，更多相关《最大公约数的三种算法_复杂度分析_时间计算（12页珍藏版）》请在金锄头文库上搜索。
1、昆明理工大学信息工程与自动化学院学生实验报告（20112012学年第1学期）课程名称：算法设计与分析开课实验室：信自楼机房4442011年10月12B年级、专业、班计科092学号200910405214姓名徐兴繁成绩实验项目名称求最大公约数指导教师吴晟教师评语该同学是否了解实验原理：A.了解口B.基本了解口C.不了解口该同学的实验能力：A.强口B.中等C-差该同学的实验是否达到要求：A.达到口B.基本达到口C.未达到口实验报告是否规范：A.规范口B.基本规范口C.不规范口实验过程是否详细记录：A.详细口B.一般口C.没有口教师签名：年月日一、上机目的及内容1. 上机内容求两个自然数m和n的最大
2、公约数。2. 上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）至少设计出三个版本的求最大公约数算法；（2）对所设计的算法采用大0符号进行时间复杂性分析；（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间;（4）通过分析对比，得出自己的结论。三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALC卄6.0软件四、实验方法、步骤（或：程序代
3、码或操作过程）实验采用三种方法求最大公约数1、连续整数检测法。2、欧儿里得算法3、分解质因数算法根据实现提示写代码并分析代码的时间复杂度：方法一：intfl(intm.intn)intt;if(nin)t=n;elset=m;while(t)if(m%t=O&n%t=O)break;elset=t-l;returnt;根据代码考虑最坏情况他们的最大公约数是1，循环做了M次，最好情况是只做了1次，可以得出O(n)=n/2;方法二：intf2(intm,intn)intr;r=m%n;while(r!=O)m=n;n=r;r=m%n;returnn;根据代码辗转相除得到欧几里得的0(n)=logn
4、方法三：intf3(intm.intn)inti=2j=0,h=0;intaN,bN,cN;while(in)if(n%i=O)J卄；aD=i；n=n/i;elsei+;J卄；aD=n；1=1；intu;u=j；while(i=j)pnntf(”d”,ai);卄；i=2;J=0；while(im)if(m%i=O)J卄；bD=i；m=m/i;elsei+;J卄；bD=m；i=l；while(i=j)pnntfC%d役bi);卄；intk=l;for(i=l;i=j;i+)for(k=l;kl)k=k*ch*ch-l;h=h-2;if(h=l)k=k*cl;returnk;elsereturnk
5、;根据代码分解质因子算法O(n)=n2+n/2为了计算每种算法运行的次数所用的时间，我将代码稍加改动添加代码如下:其中计数器采用的是没做一次循环就加1；计时器是记住开始时间和结束时间，用结束时间减开始时间。#includeniostream.hn#iiicludeflstdio.hn#include,stdlib.hH#includentime.hH#defineN100mtw,w2,w3;用于计数mtfl(mtmailtn)mtt;if(mn)t=n;elset=m;wlule(t)if(m%t=O&11%t=0)break;elset=t-l;w+;retiunt;)mtf2(intmai
6、ltn)fimtr;r=m%ii;w2=l;wlnle(r!=O)fIm=n;n=r;w2+;retimin;)mtf3(mtmailtn)fimti=2j=0Ji=0;mtaN,bN,cN;wlule(in)if(n%i=O)卄aj=i；11=11/1;w3+;else/ii+；w3卄；J卄；agi；i=l；mtu;U=J；wlule(ij)fi/pmitf(n%dfai);1卄；w3+;/pnntf(,ir,);1=2;J=0；wlule(im)J卄;111=111/1;w3卄；i+；w3卄;J卄；bj=m；1=1;wlule(i=g)pnntfC%dbi);1卄；w3+;)mtk=l;f
7、br(i=l;i=;i+)ifor(k=l;kl)k=k*ch*cli-l;h=h-2;w3+；if(h=l)k=k*cl;returnk;)elseretunik;)mtmam(void)iimt11141;pniitf(u请输入ill,nscanf(”d%d”,&m,&11);mtk;k=fl(mji);方法一最大公约数为：%dirk);k=f2(m,n);pnntf(n方法二最大公约数为：%dirk);k=f3(m,n);pnntf(n方法三最大公约数为：%dirk);pinitf(nii计数器显示结果：iiiiir1);pmitf(n方法一:%diifw2);pniitf(u方法二：%
8、dn”,w);pmi(f(”方法三：%dn”,w3);pnntf(nniin);floata,i;clocktstart,finish;doubleusetime;1=0;start=clock();while(K1000000)fl(ill,11);1+;I)finish=clock();usetmie=fiiush-start;方法一用时f*10A(6)豪秒1T；1=0;start=clock();while(K1000000)fIf2(ni4i);1+;fiiusli=clock();usetmie=fiiusli-start;pinitf(u方法二用时%.f*10A(-6)豪秒n”,1
9、=0;start=clock();while(K1000000)fIf3(ni4i);1+;fiiusli=clock();usetmie=fiiusli-start;pinitf(u方法三用时%.f*10A(-6)豪秒n”,usetmie);usetmie);usetmie);五、实验过程原始记录（测试数据.图表、计算等）请给出各个操作步骤的截图和说明;三种算法得到结果验证结果:计数器：我想到的是做一次循环就加一计算算法运行时间结果：在计算时间过程中因为计算机的运算速度很快，所以我利用了循环把时间精确得到10毫秒尿*D:程DEtmg量大公exe*数数数约约约:公公公n亠仝矣g曰誓誓車A一二三
10、输法法法请方方方2166计数器显示结果:1E：；万祛二23篆秒方迭二用时2砒対方祛二用Br-63*10-6)方法三用时石00*10气-Pressanykytocontinue六、实验结果、分析和结论(误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获)请结合实验的结果分析算法原理；在实验中遇到了些什么问题，如何解决；有什么收获等；在本次实验中代码是独自完成的，一开始我感觉这个代码最多半小时就可以完成，但是第三个算法的时候我分析了好久才写出来，在计算三种方法运行时间的时候，我一开始只精确到毫秒(ms),计算结果都是零，后面我写了一个循环调试才发现是我的精确度
11、还在不够，所以我想到了计算算法执行了1000000次之后所用的时间，然后再求平均每次执行的时间。结果分析：从前面的复杂度O(n)的岀欧儿里得算法的是最优算法，连续整除法其次，最复杂的是分解质因数算法，再从代码运行的计数器和计算的时间来看结果恰好和前面的复杂度得到的结果一致，所以的出结论：欧儿里得算法最优。从这次实验的结果我了解到了算法的优与劣的差别，虽然得到的是同样的结果，但是需要的时间和资源却相差很大，这提示我们在以后写算法的时候要找出最优算法。可见算法分析与设讣课程的对计编程的人来说是多么的重要，在以后写程序过程中要时刻提醒自己找最优算法，当然得先学会O(n)的分析。注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。
