资源描述：
《算法实验1-求最大公约数实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、精品文档可修改昆明理工大学信息工程与自动化学院学生实验报告（2011—2012学年第1学期）课程名称：算法分析与设计开课实验室：信自楼机房4442011年10月12日年级、专业、班学号姓名成绩实验项目名称求最大公约数指导教师教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名
2、：年月日一、上机目的及内容上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。上机内容求两个自然数m和n的最大公约数。二、实验原理及基本技术路线图（方框原理图或程序流程图）实验原理（1）至少设计出三个版本的求最大公约数算法；（2）对所设计的算法采用大O符号进行时间复杂性分析；（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；（4）通
3、过分析对比，得出自己的结论。流程图三、所用仪器、材料（设备名称、型号、规格等或使用软件）设备：1台PC及VISUALC++6.0软件。四、实验方法、步骤（或：程序代码或操作过程）源程序：#include#include#includeintmax(intm,intn){intr;if(m>n)r=n;elser=m;returnr;}voidMenu(){inta;voidalgorithmone();voidalgorithmtwo();voidalg
4、orithmthree();printf("请选择算法:");printf("1.算法一");printf("2.算法二");printf("3.算法三");scanf("%d",&a);getchar();switch(a){case1:algorithmone();break;case2:algorithmtwo();break;case3:algorithmthree();break;default:printf("请输入1,2,3中的一个!");}}voidalgorithmon
5、e()//算法一{clock_tstart,finish;intm,n,r;charkey;printf("求两个数的最大公约数，请输入这两个数：");scanf("%d%d",&m,&n);getchar();start=clock();r=max(m,n);while(r>0){if(m%r==0){if(n%r==0){printf("算法一求出的最大公约数为%d",r);finish=clock();break;}elser=r-1;}elser=r-1;}printf("算法一所需的时间是:%
6、ld秒",(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!");}}voidalgorithmtwo()//算法二{clock_tstart,finish;intm,n,r;charkey;printf("求两个数的最大公约数，请输入
7、这两个数：");scanf("%d%d",&m,&n);start=clock();while((r=m%n)!=0){m=n;n=r;r=m%n;if(r==0){printf("算法二求出的最大公约数为%d",n);finish=clock();break;}}printf("算法二所需的时间是:%ld秒",(finish-start));getchar();printf("是否返回主菜单?(y/n):");key=getchar();switch(key){case'y':Menu();bre
8、ak;case'Y':Menu();break;case'n':break;case'N':break;default:printf("error!");}}voidcommonzhishu(intarraym[],intarrayn[])//提取公共质数{inti,j,k=0,common[3],d=0;for(i=0;i<3;i++)for(j=0;j<3;j++)if(arraym[i]==arrayn
