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

昆明理工大学信息工程与自动化学院学生实验报告（ 2011 2012 学年 第 1 学期 ）课程名称：算法设计与分析 开课实验室：信自楼机房444 2011 年10月 12日年级、专业、班计科092学号200910405214姓名徐兴繁成绩实验项目名称求最大公约数指导教师 吴晟教师评语该同学是否了解实验原理：A.了解B.基本了解C.不了解该同学的实验能力：A.强 B.中等 C.差 该同学的实验是否达到要求：A.达到B.基本达到C.未达到实验报告是否规范：A.规范B.基本规范C.不规范实验过程是否详细记录：A.详细B.一般 C.没有 教师签名： 年 月 日一、上机目的及内容1.上机内容求两个自然数m和n的最大公约数。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）至少设计出三个版本的求最大公约数算法；（2）对所设计的算法采用大O符号进行时间复杂性分析；（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；（4）通过分析对比，得出自己的结论。三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUAL C+6.0软件四、实验方法、步骤（或：程序代码或操作过程）实验采用三种方法求最大公约数1、连续整数检测法。2、欧几里得算法3、分解质因数算法根据实现提示写代码并分析代码的时间复杂度：方法一：int f1(int m,int n)int t;if(mn)t=n;else t=m;while(t) if(m%t=0&n%t=0)break;else t=t-1;return t;根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2;方法二：int f2(int m,int n)int r;r=m%n;while(r!=0)m=n; n=r; r=m%n;return n;根据代码辗转相除得到欧几里得的O(n)= log n方法三：int f3(int m,int n)int i=2,j=0,h=0;int aN,bN,cN;while(in)if(n%i=0)j+;aj=i;n=n/i;else i+;j+;aj=n;i=1;int u;u=j;while(i=j) /printf(%d ,ai); i+;i=2;j=0; while(im)if(m%i=0)j+;bj=i;m=m/i;else i+;j+;bj=m;i=1;while(i=j) /printf(%d ,bi); i+;int k=1;for(i=1;i=j;i+)for(k=1;k1)k=k*ch*ch-1;h=h-2;if(h=1)k=k*c1;return k;else return k;根据代码分解质因子算法O(n)=n2+n/2为了计算每种算法运行的次数所用的时间，我将代码稍加改动添加代码如下：其中计数器采用的是没做一次循环就加1；计时器是记住开始时间和结束时间，用结束时间减开始时间。#includeiostream.h#includestdio.h#includestdlib.h#includetime.h#define N 100int w,w2,w3;/用于计数int f1(int m,int n)int t;if(mn)t=n;else t=m;while(t) if(m%t=0&n%t=0)break;else t=t-1;w+;return t;int f2(int m,int n)int r;r=m%n;w2=1;while(r!=0)m=n; n=r; r=m%n;w2+;return n;int f3(int m,int n)int i=2,j=0,h=0;int aN,bN,cN;while(in)if(n%i=0)j+;aj=i;n=n/i;w3+;else i+;w3+;j+;aj=n;i=1;int u;u=j;while(i=j) /printf(%d ,ai); i+; w3+;/printf(n);i=2;j=0; while(im)if(m%i=0)j+;bj=i;m=m/i;w3+;else i+;w3+;j+;bj=m;i=1;while(i=j) /printf(%d ,bi); i+; w3+;int k=1;for(i=1;i=j;i+)for(k=1;k1)k=k*ch*ch-1;h=h-2;w3+;if(h=1)k=k*c1;return k;else return k;int main(void) int m,n;printf( 请输入m,n :n);scanf(%d%d,&m,&n);int k;k=f1(m,n); printf( 方法一最大公约数为： %dn,k);k=f2(m,n);printf( 方法二最大公约数为： %dn,k);k=f3(m,n);printf( 方法三最大公约数为： %dn,k);printf(n-n);printf(n计数器显示结果：nnn); printf(方法一： %d n,w2); printf(方法二： %d n,w); printf(方法三： %d n,w3);printf(n-n);float a,i; clock_t start,finish; double usetime;i=0; start= clock(); while (i1000000)f1(m,n);i+;finish=clock(); usetime= finish-start; printf( 方法一用时%.f*10(-6) 豪秒n, usetime);i=0; start= clock(); while (i1000000)f2(m,n);i+;finish=clock(); usetime= finish-start; printf( 方法二用时%.f*10(-6) 豪秒n, usetime); i=0; start= clock(); while (i1000000)f3(m,n);i+;finish=clock(); usetime= finish-start; printf( 方法三用时%.f*10(-6) 豪秒n, usetime); 五、实验过程原始记录( 测试数据、图表、计算等)请给出各个操作步骤的截图和说明；三种算法得到结果验证结果：计数器：我想到的是做一次循环就加一计算算法运行时间结果：在计算时间过程中因为计算机的运算速度很快，所以我利用了循环把时间精确得到10-6毫秒 六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）请结合实验的结果分析算法原理；在实验中遇到了些什么问题，如何解决；有什么收获等；在本次实验中代码是独自完成的，一开始我感觉这个代码最多半小时就可以完成，但是第三个算法的时候我分析了好久才写出来，在计算三种方法运行时间的时候，我一开始只精确到毫秒（ms），计算结果都是零，后面我写了一个循环调试才发现是我的精确度还在不够，所以我想到了计算算法执行了1000000次之后所用的时间，然后再求平均每次执行的时间。结果分析：从前面的复杂度O(n)的出欧几里得算法的是最优算法，连续整除法其次，最复杂的是分解质因数算法，再从代码运行的计数器和计算的时间来看结果恰好和前面的复杂度得到的结果一致，所以的出结论：欧几里得算法最优。