算法实验1-求最大公约数实验报告

-1-精品文档可修改昆明理工大学信息工程与自动化学院学生实验报告（2011—2012学年第1学期）课程名称：算法分析与设计开课实验室：信自楼机房4442011年10月12日年级、专业、班学号姓名成绩实验项目名称求最大公约数指导教师教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日一、上机目的及内容上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。上机内容求两个自然数m和n的最大公约数。二、实验原理及基本技术路线图（方框原理图或程序流程图）实验原理（1）至少设计出三个版本的求最大公约数算法；（2）对所设计的算法采用大O符号进行时间复杂性分析；-2-（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；（4）通过分析对比，得出自己的结论。流程图-3-开始菜单选择算法算法二算法一算法三输入两个数m和n输入两个数输入两个数比较两个数的大小r=maxm%r=0且n%r=0是输出最大公约数r否r=r-1返回主菜单是否结束(r=m%n)=0输出最大公约数n否m=nn=r将两个数分解提取公共质数最大公约数为Common[0]*common[1]*common[2]返回主菜单返回主菜单否是是否-4-三、所用仪器、材料（设备名称、型号、规格等或使用软件）设备：1台PC及VISUALC++6.0软件。四、实验方法、步骤（或：程序代码或操作过程）源程序：#includestdio.h#includetime.h#includestdlib.hintmax(intm,intn){intr;if(mn)r=n;elser=m;returnr;}voidMenu(){inta;voidalgorithmone();voidalgorithmtwo();voidalgorithmthree();printf(请选择算法:\n);printf(1.算法一\n);printf(2.算法二\n);printf(3.算法三\n);scanf(%d,&a);getchar();switch(a){case1:algorithmone();break;case2:algorithmtwo();break;case3:algorithmthree();break;default:printf(请输入1,2,3中的一个!\n);}}voidalgorithmone()//算法一{clock_tstart,finish;intm,n,r;-5-charkey;printf(求两个数的最大公约数，请输入这两个数：);scanf(%d%d,&m,&n);getchar();start=clock();r=max(m,n);while(r0){if(m%r==0){if(n%r==0){printf(算法一求出的最大公约数为%d\n,r);finish=clock();break;}elser=r-1;}elser=r-1;}printf(算法一所需的时间是:%ld秒\n,(finish-start));printf(是否返回主菜单?(y/n):);key=getchar();switch(key){case'y':Menu();break;case'Y':Menu();break;case'n':break;case'N':break;default:printf(error!\n);}}voidalgorithmtwo()//算法二{clock_tstart,finish;intm,n,r;charkey;printf(求两个数的最大公约数，请输入这两个数：);scanf(%d%d,&m,&n);start=clock();while((r=m%n)!=0){m=n;-6-n=r;r=m%n;if(r==0){printf(算法二求出的最大公约数为%d\n,n);finish=clock();break;}}printf(算法二所需的时间是:%ld秒\n,(finish-start));getchar();printf(是否返回主菜单?(y/n):);key=getchar();switch(key){case'y':Menu();break;case'Y':Menu();break;case'n':break;case'N':break;default:printf(error!\n);}}voidcommonzhishu(intarraym[],intarrayn[])//提取公共质数{inti,j,k=0,common[3],d=0;for(i=0;i3;i++)for(j=0;j3;j++)if(arraym[i]==arrayn[j]){common[k]=arraym[i];k=k+1;}for(k=0;k3;k++)for(d=k+1;d3;d++)if(common[k]==common[d])common[d]=1;printf(算法三结果%d\n,common[0]*common[1]*common[2]);}voidalgorithmthree()//算法三{clock_tstart,finish;intm,n,mr,nr,i;floatcount;charkey;mr=2;-7-nr=2;printf(求两个数的最大公约数，请输入这两个数：);scanf(%d%d,&m,&n);intarraym[3],arrayn[3];i=0;start=clock();while(m!=1)//将两数分解{if((count=(float)(m%mr))==0.0){arraym[i]=mr;i++;m=m/mr;}elsemr++;}for(i=0;i3;i++)printf(%d,arraym[i]);printf(\n);i=0;while(n!=1){if((count=(float)(n%nr))==0.0){arrayn[i]=nr;i++;n=n/nr;}elsenr++;}for(i=0;i3;i++)printf(%d,arrayn[i]);printf(\n);commonzhishu(arraym,arrayn);finish=clock();printf(算法三所需的时间是:%ld秒\n,(finish-start));getchar();printf(是否返回主菜单?(y/n):);key=getchar();switch(key){case'y':Menu();break;case'Y':Menu();break;-8-case'n':break;case'N':break;default:printf(error!\n);}}voidmain(){inta;printf(请选择算法:\n);printf(1.算法一\n);printf(2.算法二\n);printf(3.算法三\n);scanf(%d,&a);getchar();switch(a){case1:algorithmone();break;case2:algorithmtwo();break;case3:algorithmthree();break;default:printf(请输入1,2,3中的一个!\n);}}五、实验过程原始记录(测试数据、图表、计算等)-9-六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）结果改进：首先选择你所想用的算法，然后再输入自己想求的两个数，回车结束，即可看到该算法求出的最大公约数和所需运行时间。在本次实验中前两个代码稍微简单一些，算法三中，输入的两个数在分解质因数时只能是分解出三个质因数，否则出错，有待该进。分析结论：复杂度：欧几里得算法的是最优算法，连续整除法其次，最复杂的是分解质因数算法，再从代码运行的计数器和计算的时间来看所得结果一致，所以得出结论：欧几里得算法最优。实验收获：从这次实验的结果我了解到了算法的优与劣的差别，虽然得到的是同样的结果，但是需要的时间和资源却相差很大，这提示我们在以后写算法的时候要找出最优算法。可见算法分析与设计课程的对计编程的人来说是多么的重要，在以后写程序过程中要时刻提醒自己找最优算法，当然得先学会O(n)的分析。注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。