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

《算法分析与设计 实验一 求最大公约数》由会员分享，可在线阅读，更多相关《算法分析与设计 实验一 求最大公约数（7页珍藏版）》请在金锄头文库上搜索。

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

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

3、n) 。三种算法的结果是一样的，但执行时间不相同。使用 Microsoft Office Visio 画出三种算法的流程图如下：方法一：开始输入 m , nt - m i n ( m , n )x = m % t结束x = 0 t = t - 1y = n % ty = 0r e t u r n tYYNN-3-方法二：开始结束输入 m , n输出 nr = 0r - m % nm - n , n = tNY方法三：开始结束输入 m , ni - 2r - m % ii - i + 1r 为质因数存入数组r = 0i - aNYYN-4-三、所用仪器、材料（设备名称、型号、规格等或使用软件）1

4、 台 PC 及 VISUAL C+6.0 软件四、实验方法、步骤（或：程序代码或操作过程）方法一：程序代码：#include int min(int m,int n)if(m0;t-)if( m%t=0 & n%t=0 )printf(%d 和%d 的最大公约数为%d:n,m,n,t);break;方法二：程序代码：#include void main()int m,n,r;int a,b,temp;printf(method (2) n);-5-printf(请输入两个数:n);scanf(%d,%d,if(m#define N 10int aN,bN;void divide(int t,i

5、nt r)int i,j=0;for(i=2;i=t;i+)if(t%i=0)t=t/i;rj=i;j=j+1;i=i-1;void main()int m,n,i,j,k=0,p,cN;for(i=0;iN;i+)-6-ai=0;bi=0;ci=0;printf(method (3) n);printf(请输入两个数:n);scanf(%d,%d,divide(m,a);divide(n,b);for(i=0;i=N;i+)for(j=0;j=N;j+)if(ai=bj)ck=bj;bj=0;k=k+1;break;for(i=0,p=1;iN;i+)if(ci!=0)p=p*ci;prin

6、tf(%d 和%d 的最大公约数是:%dn,m,n,p);五、实验过程原始记录( 测试数据、图表、计算等)在三种方法中分别输入两个数求出最大公约数，以下为三种方法运行截图：六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）这次实验设计了三种方法来求解最大公约数，虽然三种算法的最终结果是相同的，但是它们的时间复杂度以及运行时间不相同。方法一时间复杂度为：O(n/2) ；方法二时间复杂度为：O(log n)；方法三时间复杂度为：O(n)。通-7-过这次实验，我们还对数据结构的一些知识进行了复习，对算法的时间复杂度更加熟悉，以及知道了算法的设计方法和思路的不同对算法本身的执行会有一定的影响。