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

v1.0 可编辑可修改 昆明理工大学信息工程与自动化学院学生实验报告 （ 2011 —2012 学年 第 1 学期 ）

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

1.上机内容

求两个自然数m和n的最大公约数。 2.上机目的

（1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法；

（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。

二、实验原理及基本技术路线图（方框原理图或程序流程图）

（1）至少设计出三个版本的求最大公约数算法； （2）对所设计的算法采用大O符号进行时间复杂性分析；

（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。

1-1-

v1.0 可编辑可修改 三、所用仪器、材料（设备名称、型号、规格等或使用软件）

1台PC及VISUAL C++软件

四、实验方法、步骤（或：程序代码或操作过程）

实验采用三种方法求最大公约数

1、连续整数检测法。 2、欧几里得算法 3、分解质因数算法

根据实现提示写代码并分析代码的时间复杂度： 方法一：

int f1(int m,int n) { }

根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2;

方法二：int f2(int m,int n) {

2-2-

int t; if(m>n)t=n; else t=m; while(t) { } return t;

if(m%t==0&&n%t==0)break; else t=t-1;

v1.0 可编辑可修改 }

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 a[N],b[N],c[N]; while(i

3-3-

if(n%i==0) { } else i++;

j++; a[j]=i; n=n/i;