算法-最大公约数的三种算法

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

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

3、四、实验方法、步骤(或：程序代码或操作过程)实验采用三种方法求最大公约数源代码#include#include #include #include #include int xiangchu(int m,int n);int xiangjian(int m,int n);int qiongju(int m,int n);int duanchu(int m,int n);void main()double t1,t2,t3,t4,t5,t6;int m,n;int i=0;double usetime1,usetime2,usetime3;time_t start, end;printf(请输入

4、两个数:);scanf(%d%d,&m,&n);printf(相除法求最大公约数：dn,xiangchu(m,n);t1=clock();while(i1000000)(xiangchu(m,n);i+；)t2=clock();usetimel = t2-t1;printf(It takes %.f*10A(-6)n,usetime1);printf(相减法求最大公约数：dn,xiangjian(m,n);t3=clock();while(i1000000)(xiangchu(m,n);i+;)t4=clock();usetime2 = t4-t3;printf(It takes %.f*10

5、A(-6)n,usetime2);printf(短除法求最大公约数:%dn,duanchu(m,n);t5=clock();while(in)m-=n;elsen-=m;)return n;)int duanchu(int m,int n)/ 短除法 (int i,factor=1;for(i=2;i=m & i=n;i+)(while (m%i=0 & n%i=0)(factor=factor*i;m=m/i;n=n/i;)return factor;五、实验过程原始记录（测试数据、图表、计算等）” ,D:Mkr05oft Vrsual Stu di MMy Project 认篝法分忻2 Debug、算法分析2 ,匕乂 史fi青输入两金数:12 25It takes 156*10心目减法求最大公约数岂11 takes 0*10AC-6恒除法求最大公约数;1It takes 0*10AC-6ppess any key to continue六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）该次实验让我知道了求最大公约的不同种算法，除了以上三种，还有分解质因法和连续整数检测法