算法分析与设计课程设计实验报告求最大公约数实验报告实验（含源程序）

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

2、的最大公约数。上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）至少设计出三个版本的求最大公约数算法；所设计的3个版本分别是：连续整数检测算法、欧几里得算法和分解质因数算法。这3 个算法的流程图分别如下所示：（2） 对所设计的算法采用大o符号进行时间复杂性分析；在连续整数检测算法中，由于其最坏的情况是m与n除以t均不为0，直到t接近于0为止，此时所需时间接近m和n的较小

3、者的值；在欧几里得算法中，最坏的情况是每次所得的都比n略小一点；但此时，它的数据还是以n倍递减；在分解质因数算法中，关键是分解质因数的时间复杂度和将所得质因数相乘合并的时间复杂度；在对m和n分解质因数时，最坏的情况是m和n的质因数都还是m和n；分解m和n用的时间复杂度是： ；对于所得到的质因数求出它们的公共质因数时最坏的情况是有较多的质因数，且两组质因数之间没有公共质因数，此时时间复杂度是两组质因数数目之平方；然而，对于所得到的质因数数量极为有限，因此对于最坏情况下的m和n的分解质因数，所得到的质因数的数量就更少，此时可以把对于质因数合并得公共质因数的时间复杂度忽略不计；最坏的时间复杂度是：（

4、3） 上机实现算法，并用计数法和计时法分别测算算法的运行时间；在我的电脑测试所得到的部分数据表格：连续整数检测时间（秒）欧几里得时间（秒）分解质因数时间（秒）最大公约数673153380921974453701298.50032162139311656621917842814657010.9200.0011302111111177779777773284650.09900.016111111111777771113684845470.93400.15423137137137137133544513714.26708.8731234137137317311234567891.53504.0421

5、346546133132197454137911.45300.0616545874874654687874345354548454.199056.386287987465468998654658480.821013.7182545487434354313213556.937048.904154446846464645365534546350.7700.032564646546546546546446132544550.21200.0051544646846553356353253.932024.06155154654654235112436428.01303.86925546464664654

6、64687313212135143.06200.23135454546363369321329432738.99600.1323平均使用时间19.040625010.03更多测试数据请参见附录：数据测试清单！也可运行程序： 两个正整数最大公约数求解简易系统(32位).exe自己进行数据测试。（4） 通过分析对比，得出自己的结论。通过以上可以得知，欧几里得算法的性能最优，而分解质因数算法和连续整数检测算法的效率差不多，但是，当两个数据相差很大时，连续整数检测算法可能会比分解质因数算法占优势；当两个数所得到的最大质因数都较小时，分解质因数算法可能比连续整数检测算法占优势。三、所用仪器、材料（设备名

7、称、型号、规格等或使用软件）1台pc及visual studio 2005软件四、实验方法、步骤（或：程序代码或操作过程）/ 两个正整数最大公约数求解简易系统.cpp : 定义控制台应用程序的入口点。/*该系统是为了计算两个正整数的最大公约数*该系统是在visual studio 2005环境下编辑的，并通过visual studio 2005环境下编译与运行*该版本使用了boost函数库中的timer.hpp库函数，关于boost函数库可以参考网络上的boost社区*该程序制作人刘召*该系统创建时间是2011年10月12日*/#include stdafx.h#include#include

8、#include#include#include#include using namespace std;using namespace boost;long long smallernumber(long long i,long long j)return ij?i:j;long long cheking(long long m,long long n,long long t)if(m%t)-t;return cheking(m,n,t);if(n%t)-t;return cheking(m,n,t);return t;void gcdintegerchecking(long long m,

9、long long n,long long *p)long long t=smallernumber(n,m); *p=cheking(m,n,t);void gcdoujilide(long long m,long long n,long long *p)long long t=m,s=n;long long r=m%n;while(r!=0)m=n;n=r;r=m%n;*p=n;void zhiyinshupanduan(long long i,list& list)long long x=(long long)(i/2),j=i;for(long long g=2;g=x;g+)whil

10、e(i%g=0)list.push_back(g);i/=g;x=(long long)(i/2);if(i!=1)list.push_back(i);void gcdfenjiezhiyinshu(long long m,long long n,long long *p,list*list1,list*list2,list*plist)long long count=1;zhiyinshupanduan(m,*list1);zhiyinshupanduan(n,*list2);list:iterator it,rt,yt,gt=(*list2).begin();for(it=(*list1)

11、.begin();it!=(*list1).end();it+)long long a=1,b=1;yt=it;yt+;while(yt!=(*list1).end()&*yt=*it)yt+;a+;it+;for(rt=gt;rt!=(*list2).end();rt+)if(*it=*rt)gt=rt;gt+;while(gt!=(*list2).end()&*gt=*rt)gt+;b+;for(long long h=0;hpush_back(*it);break;*p=count;void menu1()coutendlt1用连续整数检测算法进行运算!t;cout2用欧几里得算法进行运

12、算!endl;coutt3用分解质因数算法进行运算!t;cout4结束对这两个数的运算！endl;cout$：flush;void input(long long& m,long long& n)coutendl$：;cinm;cout$：;cinn;void menu()coutendlt1进行下一对整数最大公约数运算！t;cout2退出本系统！endl;cout$：flush;void welcome()coutnttt欢迎使用求解两个正整数最大公约数的简易系统nendl;couttttt学 校：昆明理工大学endl;couttttt学 院：信息工程与自动化学院endl;couttttt专

13、 业：计算机科学与技术endl;couttttt指导老师：张晶endl;couttttt制作人：刘召endl;couttttt学 号：endl;coutttttqq 邮箱：endl;void exitsystem()coutn你已经成功退出本系统！n谢谢你的使用！再见！endl;void showzhiyinshu(long long j,list&list)if(list.size()coutendl整数j共有list.size()个质数，它们分别是：endl;elsecoutendl整数j没有质数！endl;list:iterator it;for(it=list.begin();it!=

14、list.end();it+)cout*itt;coutendl;list.clear();void showcommonnumber(long long m,long long n,list&plist)if(plist.size()coutendl整数m和n共有plist.size()个公共质数，它们分别是：endl;elsecoutendl整数m和n没有公共质数！endl;list:iterator it;for(it=plist.begin();it!=plist.end();it+)cout*itt;coutk;coutendl;list list1,list2,plist;syst

15、em(color 2b);while(k0&k4)switch(k)case 1:timecountor.restart();gcdintegerchecking(m,n,&p);cout连续整数检测算法所用时间为：timecountor.elapsed()秒(最高精确度毫秒级)endl;cout经连续整数检测算法运算所得m和n的最大公约数是：pendl;break;case 2:timecountor.restart();gcdoujilide(m,n,&p);cout欧几里得算法所用时间为：timecountor.elapsed()秒(最高精确度毫秒级)endl;cout经欧几里得算法运算

16、所得m和n的最大公约数是：pendl;break;case 3:timecountor.restart();gcdfenjiezhiyinshu(m,n,&p,&list1,&list2,&plist);cout分解质因数算法所用时间为：timecountor.elapsed()秒(最高精确度毫秒级)endl;showzhiyinshu(m,list1);showzhiyinshu(n,list2);showcommonnumber(m,n,plist);cout经分解质因数算法运算所得m和n的最大公约数是：pk;coutk;coutn你本次用时共time.elapsed()秒$：346546

17、1331321请输入你所要运算的第二个整数$：974541379 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：1连续整数检测算法所用时间为：11.453秒(最高精确度毫秒级)经连续整数检测算法运算所得3465461331321和974541379的最大公约数是：1 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：2欧几里得算法所用时间为：0秒(最高精确度毫秒级)经欧几里得算法运算所得3465461331321和9745413

18、79的最大公约数是：1 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：3分解质因数算法所用时间为：0.06秒(最高精确度毫秒级)整数3465461331321共有4个质数，它们分别是：3 11 18149 5786213整数974541379共有3个质数，它们分别是：7 43 3237679整数3465461331321和974541379没有公共质数！经分解质因数算法运算所得3465461331321和974541379的最大公约数是：1 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解

19、质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：4 1进行下一对整数最大公约数运算！ 2退出本系统！请输入你的选择$：1请输入你所要运算的第一个整数$：6731533809请输入你所要运算的第二个整数$：219744537012 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：1连续整数检测算法所用时间为：98.5秒(最高精确度毫秒级)经连续整数检测算法运算所得6731533809和219744537012的最大公约数是：3216213 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算!

20、 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：2欧几里得算法所用时间为：0秒(最高精确度毫秒级)经欧几里得算法运算所得6731533809和219744537012的最大公约数是：3216213 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：3分解质因数算法所用时间为：0秒(最高精确度毫秒级)整数6731533809共有11个质数，它们分别是：3 3 3 7 7 7 11 13 13 1723整数219744537012共有13个质数，它们分别是：2 2 3 3 3 7 7 11

21、13 1719 29 31整数6731533809和219744537012共有8个公共质数，它们分别是：3 3 3 7 7 11 13 17经分解质因数算法运算所得6731533809和219744537012的最大公约数是：3216213 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：4 1进行下一对整数最大公约数运算！ 2退出本系统！请输入你的选择$：1请输入你所要运算的第一个整数$：931165662请输入你所要运算的第二个整数$：19178428146570 1用连续整数检测算法进行运算! 2用欧几

22、里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：1连续整数检测算法所用时间为：10.92秒(最高精确度毫秒级)经连续整数检测算法运算所得931165662和19178428146570的最大公约数是：1302 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：2欧几里得算法所用时间为：0秒(最高精确度毫秒级)经欧几里得算法运算所得931165662和19178428146570的最大公约数是：1302 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解

23、质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：3分解质因数算法所用时间为：0.001秒(最高精确度毫秒级)整数931165662共有7个质数，它们分别是：2 3 7 31 73 97 101整数19178428146570共有10个质数，它们分别是：2 3 3 5 7 11 11 31 919 8831整数931165662和19178428146570共有4个公共质数，它们分别是：2 3 7 31经分解质因数算法运算所得931165662和19178428146570的最大公约数是：1302 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行

24、运算! 4结束对这两个数的运算！请输入你的选择$：4 1进行下一对整数最大公约数运算！ 2退出本系统！请输入你的选择$：1请输入你所要运算的第一个整数$：1111111777797777请输入你所要运算的第二个整数$：7328465 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：1连续整数检测算法所用时间为：0.099秒(最高精确度毫秒级)经连续整数检测算法运算所得1111111777797777和7328465的最大公约数是：1 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法

25、进行运算! 4结束对这两个数的运算！请输入你的选择$：2欧几里得算法所用时间为：0秒(最高精确度毫秒级)经欧几里得算法运算所得1111111777797777和7328465的最大公约数是：1 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：3分解质因数算法所用时间为：0.016秒(最高精确度毫秒级)整数1111111777797777共有6个质数，它们分别是：3 3 7 223 93251 848123整数7328465共有2个质数，它们分别是：5 1465693整数1111111777797777和7328

26、465没有公共质数！经分解质因数算法运算所得1111111777797777和7328465的最大公约数是：1 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：4 1进行下一对整数最大公约数运算！ 2退出本系统！请输入你的选择$：1请输入你所要运算的第一个整数$：11111111777771113请输入你所要运算的第二个整数$：68484547 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：1连续整数检测算法所用时间为：0.9

27、34秒(最高精确度毫秒级)经连续整数检测算法运算所得11111111777771113和68484547的最大公约数是：23 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：2欧几里得算法所用时间为：0秒(最高精确度毫秒级)经欧几里得算法运算所得11111111777771113和68484547的最大公约数是：23 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：3分解质因数算法所用时间为：0.154秒(最高精确度毫秒级)整数

28、11111111777771113共有4个质数，它们分别是：23 1033 20233 23113679整数68484547共有3个质数，它们分别是：23 79 37691整数11111111777771113和68484547共有1个公共质数，它们分别是：23经分解质因数算法运算所得11111111777771113和68484547的最大公约数是：23 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：4 1进行下一对整数最大公约数运算！ 2退出本系统！请输入你的选择$：1请输入你所要运算的第一个整数$：13

29、713713713713请输入你所要运算的第二个整数$：354451371 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：1连续整数检测算法所用时间为：4.267秒(最高精确度毫秒级)经连续整数检测算法运算所得13713713713713和354451371的最大公约数是：3 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：2欧几里得算法所用时间为：0秒(最高精确度毫秒级)经欧几里得算法运算所得13713713713713和3

30、54451371的最大公约数是：3 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：3分解质因数算法所用时间为：8.87秒(最高精确度毫秒级)整数13713713713713共有4个质数，它们分别是：3 13 263 1337010209整数354451371共有3个质数，它们分别是：3 5419 21803整数13713713713713和354451371共有1个公共质数，它们分别是：3经分解质因数算法运算所得13713713713713和354451371的最大公约数是：3 1用连续整数检测算法进行运算!

31、 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：4 1进行下一对整数最大公约数运算！ 2退出本系统！请输入你的选择$：1请输入你所要运算的第一个整数$：123413713731731请输入你所要运算的第二个整数$：123456789 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：1连续整数检测算法所用时间为：1.535秒(最高精确度毫秒级)经连续整数检测算法运算所得123413713731731和123456789的最大公约数是：1 1用连续整数检测算法进

32、行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：2欧几里得算法所用时间为：0秒(最高精确度毫秒级)经欧几里得算法运算所得123413713731731和123456789的最大公约数是：1 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：3分解质因数算法所用时间为：4.042秒(最高精确度毫秒级)整数123413713731731共有2个质数，它们分别是：202343 609923317整数123456789共有4个质数，它们分别是：3 3 3607

33、 3803整数123413713731731和123456789没有公共质数！经分解质因数算法运算所得123413713731731和123456789的最大公约数是：1 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：4 1进行下一对整数最大公约数运算！ 2退出本系统！请输入你的选择$：1请输入你所要运算的第一个整数$：6545874874654687874请输入你所要运算的第二个整数$：3453545484 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这

34、两个数的运算！请输入你的选择$：1连续整数检测算法所用时间为：54.199秒(最高精确度毫秒级)经连续整数检测算法运算所得6545874874654687874和3453545484的最大公约数是：2 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：2欧几里得算法所用时间为：0秒(最高精确度毫秒级)经欧几里得算法运算所得6545874874654687874和3453545484的最大公约数是：2 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！

35、请输入你的选择$：3分解质因数算法所用时间为：56.386秒(最高精确度毫秒级)整数6545874874654687874共有6个质数，它们分别是：2 23 37 41 11657 8047064651整数3453545484共有7个质数，它们分别是：2 2 3 3 3 3 10659091整数6545874874654687874和3453545484共有1个公共质数，它们分别是：2经分解质因数算法运算所得6545874874654687874和3453545484的最大公约数是：2 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的

36、运算！请输入你的选择$：4 1进行下一对整数最大公约数运算！ 2退出本系统！请输入你的选择$：1请输入你所要运算的第一个整数$：87987465468998请输入你所要运算的第二个整数$：65465848 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：1连续整数检测算法所用时间为：0.821秒(最高精确度毫秒级)经连续整数检测算法运算所得87987465468998和65465848的最大公约数是：2 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的

37、运算！请输入你的选择$：2欧几里得算法所用时间为：0秒(最高精确度毫秒级)经欧几里得算法运算所得87987465468998和65465848的最大公约数是：2 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：3分解质因数算法所用时间为：13.718秒(最高精确度毫秒级)整数87987465468998共有4个质数，它们分别是：2 43 503 2034016031整数65465848共有6个质数，它们分别是：2 2 2 7 41 28513整数87987465468998和65465848共有1个公共质数，它们分别是：2经分解质因数算法运算所得87987465468998和65465848的最大公约数是：2 1用连续整数检测算法进行运算! 2用欧几里得算法进行运算! 3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：4 1进行下一对整数最大公约数运算！ 2退出本