算法分析求最大公约数-软件工程-13083511-周成

北京联合大学硕士研究生

算法设计与分析实验报告

实 验 项 目： 求最大公约数 姓 名： 周 成 学 号： 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-

}

int f3(int m,int n) { int i=2,j=0,h=0; int a[N],b[N],c[N]; while(i

} else { i++; w3++; }

} j++; a[j]=n; i=1; int u; u=j; while(i<=j)

{

-6-

//printf(\ i++; w3++; }

//printf(\i=2; j=0;

while(i

} else { i++; w3++; }

} j++; b[j]=m; i=1; while(i<=j) {

-7-

//printf(\ i++; w3++; } int k=1; for(i=1;i<=j;i++) { for(k=1;k<=u;k++) {

if(b[i]==a[k]) { w3++; h++;

c[h]=a[k];//printf(\ for(k=1;k

} }

} k=1; while(h>1) { k=k*c[h]*c[h-1]; h=h-2;

w3++;

-8-

} if(h==1) { k=k*c[1]; return k;

}

else return k;

}

int main(void) { int m,n;

printf(\请输入m,n :\ scanf(\ int k; k=f1(m,n);

printf(\方法一最大公约数为： %d\\n\ k=f2(m,n);

printf(\方法二最大公约数为： %d\\n\ k=f3(m,n);

printf(\方法三最大公约数为： %d\\n\ printf(\

printf(\计数器显示结果：\\n\\n\\n\

printf(\方法一： %d \\n\ printf(\方法二： %d \\n\ printf(\方法三： %d \\n\ printf(\

float a,i;

-9-

clock_t start,finish; double usetime;

i=0;

start= clock(); while (i<1000000) { f1(m,n); i++;

}

finish=clock(); usetime= finish-start;

printf(\方法一用时%.f*10^(-6)

i=0;

start= clock(); while (i<1000000) { f2(m,n); i++;

}

finish=clock(); usetime= finish-start;

printf(\方法二用时%.f*10^(-6)

i=0;

start= clock(); while (i<1000000) {

f3(m,n);

豪秒\\n\豪秒\\n\

usetime); usetime); -10-

}

i++;

finish=clock(); usetime= finish-start;

printf(\方法三用时%.f*10^(-6) 豪秒\\n\ usetime);

}}五、实验过程原始记录( 测试数据、图表、计算等)

三种算法得到结果验证结果：

计数器：做一次循环就加一

计算算法运行时间结果：在计算时间过程中因为计算机的运算速度很快，所以利用了循环把时间精确得到10毫秒

-6

六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）

在本次实验中代码是独自完成的，一开始我感觉这个代码最多半小时就可以完成，但是第三个算法

-11-

的时候我分析了好久才写出来，在计算三种方法运行时间的时候，我一开始只精确到毫秒（ms），计算结果都是零，后面我写了一个循环调试才发现是我的精确度还在不够，所以我想到了计算算法执行了1000000次之后所用的时间，然后再求平均每次执行的时间。

结果分析：从前面的复杂度O(n)的出欧几里得算法的是最优算法，连续整除法其次，最复杂的是分解质因数算法，再从代码运行的计数器和计算的时间来看结果恰好和前面的复杂度得到的结果一致，所以的出结论：欧几里得算法最优。

从这次实验的结果我了解到了算法的优与劣的差别，虽然得到的是同样的结果，但是需要的时间和资源却相差很大，这提示我们在以后写算法的时候要找出最优算法。可见算法分析与设计课程的对计编程的人来说是多么的重要，在以后写程序过程中要时刻提醒自己找最优算法，当然得先学会O(n)的分析。

-12-

本文来源：https://www.bwwdw.com/article/xrv3.html