最大公约数的三种算法复杂度分析时间计算

1、昆明理工大学信息工程与自动化学院学生实验报告(20112012 学年第1学期)课程名称：算法设计与分析开课实验室：信自楼机房444 2011年10月12日年级、专业、班计科092学号5214姓名徐兴繁成绩实验项目名称求最大公约数指导教师吴晟师该同学是否了解实验原理：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及VISUAL C+软件四、实验方法、步骤(或：程序代码或

3、操作过程)实验采用三科方法求最大公约数1、连续整数检测法。2、欧几里得算法3、分解质因数算法根据实现提示写代码并分析代码的吋间复杂度：方法一:int f 1 (int m, int n)int t;i f (m>n) t=n;else ±=01；while Ct)if (iri%t=0&&n%t=0) break;e I se t二tT ;return t;根据代码考虑就坏情况他们的最大公约数是1,循环做了 t-1次，最好情况是只做了 1次，可以得出 0 (n) =n/2;a方法二：int f2(int m, int n)int r;r=m%n;whi le(r

4、 !=0)m=n;n=r;r=m%n;return n;I根据代码辗转相除得到欧几里得的0(n)= logn方法三：int f3( int m, int n)int i=2, j=0, h=0;int aN, bN, cN; whi le(i<n)if (n%i=O)j+;aj = i; n=n/i;else i+;I j+； aj=n;i=1；int u;u=j； whi le(i<=j)usetime);*10" (-6)豪秒n",i=0;start二 clock();while (i<1000000)f2 (m, n);i卄；)finish=cloc

5、k();usetime二 finish-start;printf (n 方法二用时%. f*10(-6) 豪秒n”,i=0;start二 clockO ;while (i<1000000)f3 (m, n);i+；1finish=clock();usetime二 finish-start;?printf (n 方法三用时.卅10八(-6) 豪秒n",五、实验过程原始记录(测试数据、图表、计算等)请给出各个操作步骤的截图和说明；三种算法得到结果验证结果：usetime);usetime);c"D: 编程D求最大公约数1. exe请输入nun :66 12方迭一曇大公约数

6、为：6 方柱二臺犬公约数为：6 分梅质因子2 2 32 3 11民共质因子2 3方法三最大公约数为：6计数器：我想到的是做一次循环就加一计算算法运行时间结果：在计算时间过程中因为计算机的运算速度很快，所以我利用了循环把时间精确得到毫秒用用用ke 一二三y 法菱an 方方方務6 6 6 数数数 约约约 :公公公 n大-K+八 叫曰¥<廉 A一二三 输法虐 请方方方216六. 实验结果、分析和结论(误差分析与数据处理、成果总结等。其中，绘制曲线图时必 须用计算纸或程序运行结杲、改进、收获)请结合实验的结果分析算法原理：在实验中遇到了些什么问題，如何解决：有什么收获等；在本次实验中代

7、码是独自完成的，一开始我感觉这个代码最多半小时就可以完成，但是第三个算法 的时候我分析了好久才写出来，在计算三种方法运行时间的时候，我一开始只精确到毫秒(ms),计算结 果都是零，后面我写了一个循环调试才发现是我的精确度还在不够，所以我想到了计算算法执行了 1000000次之后所用的时间，然后再求平均每次执行的时间。结果分析：从前面的复杂度0(n)的出欧几里得算法的是置优算法，连续整除法其次，最复杂的是分 解质因数算法，再从代码运行的计数器和计算的时间来看结果恰好和前面的复杂度得到的结果一致，所 以的出结论：欧几里得算法最优。从这次实验的结果我了解到了算法的优与劣的差别，虽然得到的是同样的结果，但是需要的时间和 资源却相差很大，这提示我们在