昆明理工大学 算法 实验一 求最大公约数Word格式文档下载.docx

1、 A.达到 B.基本达到 C.未达到实验报告是否规范： A.规范 B.基本规范 C.不规范实验过程是否详细记录： A.详细 B.一般 C.没有 教师签名： 年 月 日一、上机目的及内容上机内容求两个自然数m和n的最大公约数。上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）至少设计出三个版本的求最大公约数算法；（2）对所设计的算法采用大O符号进行时间复杂性分析；（3）上

2、机实现算法，并用计数法和计时法分别测算算法的运行时间；（4）通过分析对比，得出自己的结论。三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUAL C+6.0软件四、实验方法、步骤（或：程序代码或操作过程） 1.连续整数检测#include /连续整数检测int gcd（int m,int n） int t=mn ? n:m; while（true） if（m%t=0） if（n%t=0） return t; else t-; void main（） int m,n; coutmn）Output:gcd（m,n）2.欧几里得算法#include/欧几里德算法 int r;

3、while（ n!=0） r = m%n; m=n; n=r; return m;3.分解质因数/分解质因数法int FJ（int m,int n） if（m=1|n=1） 最大公约数为：1 int a10,b10,s,t=2,i=0,all,m1,n1,i1,i2; m1=m; n1=n;m=; while（1） s=m1%t; /求m1除以t（t为2）的余数s if（s=0） m1=m1/t; ai=t; /把t摆在数组a中 coutt; i+; t=2; all=1; for（i1=0;i1i;i1+） all=all*ai1; if（m=all） break; /判断该整数的质因数是否

4、全部求出* else t+; i=0; /把i重置为0，进行整数n的求质因数n s=n1%t; n1=n1/t; bi=t; for（i2=0;i2i2+） all=all*bi2; if（n=all） break; all=1; for（int s1=0;s1i1;s1+） /利用循环，求出公共质因数 for（int s2=0;s2i2;s2+） if（as1=bs2） all=all*as1; bs2=0; break;alln; FJ（m,n）;3.计数法和计时法分别测算算法的运行时间#includeiostream.hstdio.hstdlib.htime.h#define N 100

5、int w1,w2,w3;/用于计数int f1（int m,int n） /连续整数检测 w1+;w1+;int f2（int m,int n） /欧几里德算法 w2+;int f3（int m,int n） /分解质因数法 /cout /cout w3+;w3+; return all; int k; k=f1（m,n）; printf（方法一最大公约数为： %dn,k）; k=f2（m,n）;方法二最大公约数为： k=f3（m,n）;方法三最大公约数为：n计数器显示结果：nnn）;方法一： %d n,w1）;方法二：,w2）;方法三：,w3）;n-n float a,i; clock_t

6、 start,finish; double usetime; start= clock（）; while （i100000） f1（m,n）; i+; finish=clock（）; usetime= finish-start;方法一用时%.f*10（-6） 豪秒n, usetime）; f2（m,n）;方法二用时%.f*10（-6） 豪秒n f3（m,n）;方法三用时%.f*10（-6） 豪秒n五、实验过程原始记录（ 测试数据、图表、计算等） 1.连续整数检测4.计数法和计时法分别测算算法的运行时间六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序

7、运行结果、改进、收获）第一种，连续整数检测法。根据代买考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做一次，所以O（n）=n/2。第二种，欧几里得算法。根据代码辗转相除得到欧几里得的O（n）=log n。第三种，分解质因数法。根据代码分解质成因子算法O（n）=n2+n/2。结果分析：从前面的复杂度O（n）的出欧几里得算法的是最优算法，连续整除法其次，最复杂的是分解质因数算法，再从代码运行的计数器和计算的时间来看结果恰好和前面的复杂度得到的结果一致，所以的出结论：欧几里得算法最优。通过对三种计算最大公约数方法的比较，了解了算法设计的初步概念，并对求公约数问题有了更深的认识。了解到了算法的优与劣的差别，虽然得到的是同样的结果，但是需要的时间和资源却相差很大，这提示我们在以后写算法的时候要找出最优算法。也告诉了我们，算法对于一个程序的重要性，我们要对这门课产生足够的重视。注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。