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

《最大公约数的三种算法 复杂度分析 时间计算.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、昆明理工大学信息工程与自动化学院学生实验报告（2011—2012学年第1学期）课程名称：算法设计与分析开课实验室：信自楼机房4442011年10月12日年级、专业、班计科092学号200910405214姓名徐兴繁成绩实验项目名称求最大公约数指导教师吴晟教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日一、上机目的及内容1.上机内容求两

2、个自然数m和n的最大公约数。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）至少设计出三个版本的求最大公约数算法；（2）对所设计的算法采用大O符号进行时间复杂性分析；（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；（4）通过分析对比，得出自己的结论。三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALC++6.

3、0软件四、实验方法、步骤（或：程序代码或操作过程）实验采用三种方法求最大公约数-10-1、连续整数检测法。2、欧几里得算法3、分解质因数算法根据实现提示写代码并分析代码的时间复杂度：方法一：intf1(intm,intn){intt;if(m>n)t=n;elset=m;while(t){if(m%t==0&&n%t==0)break;elset=t-1;}returnt;}根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2;方法二：intf2(intm,intn){intr;r=m%n;while(r!=0){m=n;n

4、=r;r=m%n;}returnn;}根据代码辗转相除得到欧几里得的O(n)=logn方法三：intf3(intm,intn){inti=2,j=0,h=0;inta[N],b[N],c[N];while(i

5、j){//printf("%d",b[i]);i++;}intk=1;for(i=1;i<=j;i++){for(k=1;k<=u;k++){if(b[i]==a[k]){h++;-10-c[h]=a[k];//printf("%d",c[h]);a[k]=a[k+1];break;}}}k=1;while(h>1){k=k*c[h]*c[h-1];h=h-2;}if(h==1){k=k*c[1];returnk;}elsereturnk;}根据代码分解质因子算法O(n)=n2+n/2为了计算每种算法运行的次数所用的时间，我将代码稍加改动添加代码如下：其中计数器采用的是没做一次

6、循环就加1；计时器是记住开始时间和结束时间，用结束时间减开始时间。#include"iostream.h"#include"stdio.h"#include"stdlib.h"#include"time.h"#defineN100intw,w2,w3;//用于计数intf1(intm,intn){intt;if(m>n)t=n;elset=m;while(t){if(m%t==0&&n%t==0)break;elset=t-1;w++;}returnt;}-10-intf2(intm,intn){intr;r=m%n;w2=1;while(r!=0){m=n;n=r;r=m%n

7、;w2++;}returnn;}intf3(intm,intn){inti=2,j=0,h=0;inta[N],b[N],c[N];while(i