求最大公约数.doc

《求最大公约数.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、昆明理工大学信息工程与自动化学院学生实验报告（2011—2012学年第1学期）课程名称：算法设计与分析开课实验室：信自楼机房4442011年10月12日年级、专业、班学号姓名成绩实验项目名称求最大公约数指导教师教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日一、上机目的及内容1.上机内容求两个自然数m和n的

2、最大公约数。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）至少设计出三个版本的求最大公约数算法；（2）对所设计的算法采用大O符号进行时间复杂性分析；（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；（4）通过分析对比，得出自己的结论。三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUA

3、LC++6.0软件四、实验方法、步骤（或：程序代码或操作过程）-6-(1)连续整数检测算法开始输入m和nt=min{m,n}m%t=0&&n%t=0YNt=t-1输出t结束#includeintminnumber(inta,intb){if(a>b)returnb;elsereturna;}voidmain(){intm,n,t;printf("***连续整数检测***");printf("请输入两个数并按Enter：");scanf("%d%d",&m,&n);for(;;){if((m%t==0)&&(n%t==0)){

4、printf("%d和%d的最大公约数是：%d.",m,n,t);-6-break;}t--;}}(2)欧几里得算法YN开始输入m和nr=m%nr=0m=nn=r输出n结束#includevoidmain(){intm,n,r;printf("***欧几里得算法***");printf("请输入两个数并按Enter：");scanf("%d%d",&m,&n);-6-r=m%n;while(r!=0){m=n;n=r;r=m%n;}printf("这两个数的最大公约数是：%d.",n);}(3)分解质因数1.将m分解

5、质因数；2.将n分解质因数；3.提取m和n中的公共质因数；4.将m和n中的公共质因数相乘，乘积作为结果输出。#includevoidmain(){intn,m,a,i,s=1;printf("***分解质因数***");printf("请输入两个数:");scanf("%d%d",&n,&m);a=m;if(n>m)a=n;printf("%d,%d共同质因数为:",n,m);for(i=2;i<=a;i++){while(a>=i){if(n%i==0&&m%i==0){printf("%d",i);n=n/i;m=m/i;s

6、=s*i;}elsebreak;}}printf("最大公约数为%d",s);}-6-五、实验过程原始记录(测试数据、图表、计算等)请给出各个操作步骤的截图和说明；连续整数检测算法：它是三个算法中执行效率较高的。时间复杂度：T（n）=O(n)；基本语句执行次数C(n)=n。欧几里得算法（辗转相除法）：它是三个算法中执行效率最高的，是计算两个数最大公约数的传统算法，它无论从理论还是从效率上都是很好的。但它有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。辗转相除法的运算速度为O(n2)其中n为输入数值的位数。共质因数相乘算法：-6-它是

7、三种算法执行速度最慢的。六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）请结合实验的结果分析算法原理；在实验中遇到了些什么问题，如何解决；有什么收获等；1、刚开始时曾忽略了一些变量参数的标识“&”，使程序调试时费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。2、没有彻底了解算法，导致编程出错。3、在编写分解质因数算法的过程中感觉比较困难。注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。-6-