北京联合大学硕士研究生
算法设计与分析实验报告
实 验 项 目： 求最大公约数 姓 名： 周 成 学 号： 13083511 指 导 教 师： 王育坚 编 制 日 期： 2014-03-11
-1-
1 实验项目
求两个自然数m和n的最大公约数。
2 实验目的
（1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法；
（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 3 实验要求
（1）至少设计出三个版本的求最大公约数算法；
（2）对所设计的算法采用大O符号进行时间复杂性分析；
（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。
4 算法设计与实现
（1）实验环境：Microsoft Visual Studio2010
1、连续整数检测法。 2、欧几里得算法 3、分解质因数算法
根据实现提示写代码并分析代码的时间复杂度： 方法一：
int f1(int m,int n) { int t; if(m>n)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; }
-2-
}
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 while(i -3- } { //printf(\ i++; } int k=1; for(i=1;i<=j;i++) { for(k=1;k<=u;k++) { if(b[i]==a[k]) { h++; c[h]=a[k];//printf(\ 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]; return k; } else return k; 2 根据代码分解质因子算法O(n)=n +n/2 为了计算每种算法运行的次数所用的时间，我将代码稍加改动添加代码如下： 其中计数器采用的是没做一次循环就加1； 计时器是记住开始时间和结束时间，用结束时间减开始时间。 #include\#include\#include\#include\#define N 100 -4- int w,w2,w3;//用于计数 int f1(int m,int n) { int t; if(m>n)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; -5-