算法分析与设计实验一求最大公约数

《算法分析与设计实验一求最大公约数》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、（201—201学年第1学期）课程名称：算法设计与分析开课实验室：年月日年级、专业、班学号姓名成绩实验项目名称求最大公约数指导教师教该同学是否了解实验原理：A.了解口B.基本了解口C.不了解口师该同学的实验能力：A.强口B.中等□C.差□该同学的实验是否达到要求：A.达到口B.基本达到口0.未达到口评实验报告是否规范：A.规范口B.基木规范口C.不规范口实验过程是否详细记录：A.详细口B.一般□C.没有口语教师签名：年月日一、上机目的及内容1.上机内容求两个自然数m和n的最大公约数。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）

2、掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同,复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）至少设计出三个版本的求最大公约数算法；（2）对所设计的算法采用大0符号进行时间复杂性分析;(3)上机实现算法，并用计数法和计时法分别测算算法的运行时间；(4)通过分析对比，得出自己的结论。本次实验求最大公约数设计了三种算法，方法一时间复杂度为：O(n/2)；方法二时间复杂度为：O(logn)；方法三吋间复杂度为：O(n)。三种算法的结果是一样的，但执行

3、I］寸间不相同。使用MicrosoftOfficeVisio画出三种算法的流程图如下：方法一：方法二Vx=m%t◄Y▼y=n%treturnt结束结束方法三:三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALC++6.0软件四、实验方法、步骤(或：程序代码或操作过程)方法一：程序代码：#includeintmin(intm,intn){if(m

4、canf("%d,%d",&m,&n);t=min(m,n);for(;t>0;t-){if(m%t==0&&n%t==0){printf(H%d和％d的最大公约数为%d:n,m,n,t);break;}}}方法二程序代码：#includevoidmain(){intm,n,r;inta,b,temp;printf(Hmethod(2)H);printf(”请输入两个数:”);scanf(n%d,%dH,&m,&n);if(m

5、n;n=r;r=m%n;}printf(H%d和％d的最大公约数为%d:”,a,b,n);}方法三：程序代码：#include#defineN10inta[N],b[N];voiddivide(intt,intr[]){inti,j=0;for(i=2;i<=t;i++){if(t%i==O){t=t/i;r[jl=i；j=j+l；i=i-l;voidmain()intm,n,i,j,k=0,p,c[N];for(i=0;i

6、f(”请输入两个数:“);scanf(”％d,%d”,&m,&n);divide(m,a);divide(n,b);for(i=0;i<=N;i++){for(j=0;j<=N;j++){if(a[i]==b[j]){c[k]=b[j];bUl=O；k=k+l;break;}}}for(i=0,p=l;i

7、果、分析和结论(误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获)这次实验设计了三种方法来求解最大公约数，虽然三种算法的最终结果是相同的，但是它们的时间复杂度以及运行时间不相同。方法一时间复杂度为：O(n/2)；方法二时间复杂度为：O(logn)；方法三时间复杂度为：O(n)。通过这次实验，我们还对数据结构的一些知识进行了复习，对算法的时间复杂度更加熟悉，以及知道了算法的设计方法和思路的不同对算法本身的执行会有一定的影响。