三种方法求最大公约数200910405429

《三种方法求最大公约数200910405429》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、昆明理工大学信息工程与自动化学院学生实验报告（2011—2012学年第1学期）课程名称：算法设计与分析开课实验室：信自楼应用、网络机房4452011年10月19日年级、专业、班计科094学号200910405429姓名徐章林成绩实验项目名称求最大公约数指导教师吴霖教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程

2、是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日一、上机目的及内容1.上机内容求两个自然数m和n的最大公约数。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALC++6.0软件三、实验原理及基本技术路线图（方框原理图或程序流程图）-6-（1

3、）分解质因数法的流程分析如下图：（2）连续整数检测法流程分析如下图：-6-（1）殴几里德流程分析如下图：四、实验方法、步骤（或：程序代码或操作过程）/*--------------------用多种方法计算两个数的最大公约数----------------------*//*-----------------作者：200910405429--------开发环境：DEVC++----------------*/#include"stdio.h"#include"conio.h"#include"

4、time.h"/*------------------------以下是分解质因数法--------------------------------*/intgcd_factor(inta,intb){intk=1,i,temp;{temp=a;a=b;b=temp;}if(a%b==0){returnb;}else{for(i=2;i

5、nk;}}/*-----------------------------以下是更相减损术-----------------------------*/intgcd_reduction(inta,intb){inttemp;if(a

6、-----*/intgcd_continuous(inta,intb)/**/{inti,k,temp;temp=a

7、ntb){if(!b)returna;elsereturngcd_Euclidean(b,a%b);}/*---------------------------------主函数-----------------------------------*/main()-6-{inta,b,i=1000;doublestart=0,end=0,time[4];printf("输入两个整数:");scanf("%d%d",&a,&b);while(1){start=clock();/*以下测算gcd_f

8、actor(a,b)的时间*/while(i>0){gcd_factor(a,b);i--;}end=clock();time[0]=(end-start);end=0;start=clock();/*以下测算gcd_Euclidean(a,b)的时间*/while(i>0){gcd_Euclidean(a,b);i--;}end=clock();time[1]=(end-start);start=clock();/*以下测算gcd_continuous(a,b)的时间*/while(i>0){