1、昆明理工大学 算法 实验一 求最大公约数昆明理工大学信息工程与自动化学院学生实验报告( 2011 2012 学年 第 1 学期 )课程名称:算法分析与设计 开课实验室:信自楼机房445 2011 年10月 12日年级、专业、班计科093学号200910405310姓名孙浩川成绩实验项目名称求最大公约数指导教师 张晶教师评语该同学是否了解实验原理: A.了解 B.基本了解 C.不了解该同学的实验能力: A.强 B.中等 C.差 该同学的实验是否达到要求: A.达到 B.基本达到 C.未达到实验报告是否规范: A.规范 B.基本规范 C.不规范实验过程是否详细记录: A.详细 B.一般 C.没有
2、教师签名: 年 月 日一、上机目的及内容上机内容求两个自然数m和n的最大公约数。上机目的(1)复习数据结构课程的相关知识,实现课程间的平滑过渡;(2)掌握并应用算法的数学分析和后验分析方法;(3)理解这样一个观点:不同的算法能够解决相同的问题,这些算法的解题思路不同,复杂程度不同,解题效率也不同。二、实验原理及基本技术路线图(方框原理图或程序流程图)(1)至少设计出三个版本的求最大公约数算法;(2)对所设计的算法采用大O符号进行时间复杂性分析;(3)上机实现算法,并用计数法和计时法分别测算算法的运行时间;(4)通过分析对比,得出自己的结论。三、所用仪器、材料(设备名称、型号、规格等或使用软件)
3、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-; else t-; void main() int m,n; coutInput m and n:mn) coutOutput:endl; coutgcd(m,n)endl; 2.欧几里得算法#include/欧几里德算法int gcd(int m,int n) int r; while( n
4、!=0) r = m%n; m=n; n=r; return m;void main() int m,n; coutInput m and n:mn) coutOutput:endl; coutgcd(m,n)endl; 3.分解质因数#include/分解质因数法int FJ(int m,int n) if(m=1|n=1) cout最大公约数为:1endl; int a10,b10,s,t=2,i=0,all,m1,n1,i1,i2; m1=m; n1=n; coutm=; while(1) s=m1%t; /求m1除以t(t为2)的余数s if(s=0) m1=m1/t; ai=t; /
5、把t摆在数组a中 coutt; i+; t=2; all=1; for(i1=0;i1i;i1+) all=all*ai1; if(m=all) break; /判断该整数的质因数是否全部求出 cout*; else t+; i=0; /把i重置为0,进行整数n的求质因数 coutendl; coutn=; while(1) s=n1%t; if(s=0) n1=n1/t; bi=t; coutt; i+; t=2; all=1; for(i2=0;i2i;i2+) all=all*bi2; if(n=all) break; cout*; else t+; coutendl; all=1; f
6、or(int s1=0;s1i1;s1+) /利用循环,求出公共质因数 for(int s2=0;s2i2;s2+) if(as1=bs2) all=all*as1; bs2=0; break; cout最大公约数为:allendl; return 0;void main() int m,n; char c; cout请分别输入两个整数mn; FJ(m,n);3.计数法和计时法分别测算算法的运行时间#include #includeiostream.h#includestdio.h#includestdlib.h#includetime.h#define N 100int w1,w2,w3;/
7、用于计数int f1(int m,int n) /连续整数检测 int t=mn ? n:m; while(true) if(m%t=0) if(n%t=0) return t; else t-; w1+; else t-;w1+; int f2(int m,int n) /欧几里德算法 int r; while( n!=0) r = m%n; m=n; n=r; w2+; return m;int f3(int m,int n) /分解质因数法 if(m=1|n=1) cout最大公约数为:1; int a10,b10,s,t=2,i=0,all,m1,n1,i1,i2; m1=m; n1=
8、n; /coutm=; 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; w3+; for(i1=0;i1i;i1+) all=all*ai1; if(m=all) break; /判断该整数的质因数是否全部求出 /cout*; else t+;w3+; i=0; /把i重置为0,进行整数n的求质因数 /coutendl; /coutn=; while(1) s=n1%t; if(s=0) n1=n1/t; bi=t; /coutt; i+; t=2; all=1
9、;w3+; for(i2=0;i2i;i2+) all=all*bi2; if(n=all) break; /cout*; else t+;w3+; /coutendl; all=1; for(int s1=0;s1i1;s1+) /利用循环,求出公共质因数 for(int s2=0;s2i2;s2+) if(as1=bs2) all=all*as1; bs2=0;w3+; break; /cout最大公约数为:allendl; return all;void main() int m,n; coutInput m and n:mn; int k; k=f1(m,n); printf(方法一最
10、大公约数为: %dn,k); k=f2(m,n); printf(方法二最大公约数为: %dn,k); k=f3(m,n); printf(方法三最大公约数为: %dn,k); printf(n计数器显示结果:nnn); printf(方法一: %d n,w1); printf(方法二: %d n,w2); printf(方法三: %d n,w3); printf(n-n); float a,i; clock_t start,finish; double usetime; i=0; start= clock(); while (i100000) f1(m,n); i+; finish=cloc
11、k(); usetime= finish-start; printf(方法一用时%.f*10(-6) 豪秒n, usetime); i=0; start= clock(); while (i100000) f2(m,n); i+; finish=clock(); usetime= finish-start; printf(方法二用时%.f*10(-6) 豪秒n, usetime); i=0; start= clock(); while (i100000) f3(m,n); i+; finish=clock(); usetime= finish-start; printf(方法三用时%.f*10
12、(-6) 豪秒n, usetime); 五、实验过程原始记录( 测试数据、图表、计算等) 1.连续整数检测2.欧几里得算法3.分解质因数4.计数法和计时法分别测算算法的运行时间六、实验结果、分析和结论(误差分析与数据处理、成果总结等。其中,绘制曲线图时必须用计算纸或程序运行结果、改进、收获)第一种,连续整数检测法。根据代买考虑最坏情况他们的最大公约数是1,循环做了t-1次,最好情况是只做一次,所以O(n)=n/2。第二种,欧几里得算法。根据代码辗转相除得到欧几里得的O(n)=log n。第三种,分解质因数法。根据代码分解质成因子算法O(n)=n2+n/2。结果分析:从前面的复杂度O(n)的出欧几里得算法的是最优算法,连续整除法其次,最复杂的是分解质因数算法,再从代码运行的计数器和计算的时间来看结果恰好和前面的复杂度得到的结果一致,所以的出结论:欧几里得算法最优。通过对三种计算最大公约数方法的比较,了解了算法设计的初步概念,并对求公约数问题有了更深的认识。了解到了算法的优与劣的差别,虽然得到的是同样的结果,但是需要的时间和资源却相差很大,这提示我们在以后写算法的时候要找出最优算法。也告诉了我们,算法对于一个程序的重要性,我们要对这门课产生足够的重视。注:教师必须按照上述各项内容严格要求,认真批改和评定学生成绩。
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2