《算法分析与设计课程设计实验报告-求最大公约数实验报告实验（含源程序）》由会员分享，可在线阅读，更多相关《算法分析与设计课程设计实验报告-求最大公约数实验报告实验（含源程序）（73页珍藏版）》请在金锄头文库上搜索。
1、-1-昆明理工大学信息工程与自动化学院学生实验报告（ 2011 2012 学年 第 1 学期 ）课程名称：算法分析与设计 开课实验室：信自楼机房 445 2011 年 10月 12 日年级、专业、班计科 092 学号 1 姓名 刘召 成绩实验项目名称 求最大公约数 指导教师 张晶教师评语该同学是否了解实验原理： A.了解 B.基本了解 C.不了解该同学的实验能力： A.强 B.中等 C.差 该同学的实验是否达到要求： A.达到 B.基本达到 C.未达到实验报告是否规范： A.规范 B.基本规范 C.不规范实验过程是否详细记录： A.详细 B.一般 C.没有 教师签名：年 月 日一、上机目的及内
2、容上机内容求两个自然数 m和 n的最大公约数。上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）至少设计出三个版本的求最大公约数算法；所设计的 3个版本分别是：连续整数检测算法、欧几里得算法和分解质因数算法。这 3 个算法的流程图分别如下所示：-2-4-5-6-（2）对所设计的算法采用大 O符号进行时间复杂性分析；在连续整数检测算法中，由于其最坏的情况是 m与 n除以
3、t均不为 0，直到 t接近于 0为止，此时所需时间接近 m和 n的较小者的值； (,)i,在欧几里得算法中，最坏的情况是每次 %所得的 r都比 n略小一点；但此时，它的数据还是以n倍递减； (,)lgO在分解质因数算法中，关键是分解质因数的时间复杂度和将所得质因数相乘合并的时间复杂度；在对 m和 n分解质因数时，最坏的情况是 m和 n的质因数都还是 m和 n；分解 m和 n用的时间复杂度是：2；对于所得到的质因数求出它们的公共质因数时最坏的情况是有较多的质因数，且两组质因数之间没有公共质因数，此时时间复杂度是两组质因数数目之平方；然而，对于所得到的质因数数量极为有限，因此对于最坏情况下的 m和
4、 n的分解质因数，所得到的质因数的数量就更少，此时可以把对于质因数合并得公共质因数的时间复杂度忽略不计；最坏的时间复杂度是： 2n（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；在我的电脑测试所得到的部分数据表格：mn连续整数检测时间（秒）欧几里得时间（秒）分解质因数时间（秒）最大公约数2 98.5 0 0570 10.92 0 0.001 130297777 0.099 0 0.016 10.934 0 0.154 23713 4.267 0 8.87 31731 1.535 0 4.042 121 11.453 0 0.06 154.199 0 56.386 2998 0.8
5、21 0 13.718 26.937 0 48.904 10.77 0 0.032 50.212 0 0.005 13.932 0 24.061 528.013 0 3.869 243.062 0 0.23 1369 38.996 0 0.132 3平均使用时间 19. 0 10.03更多测试数据请参见附录：数据测试清单！也可运行程序： 两个正整数最大公约数求解简易系统(32位).exe 自己进行数据测试。-7-（4）通过分析对比，得出自己的结论。通过以上可以得知，欧几里得算法的性能最优，而分解质因数算法和连续整数检测算法的效率差不多，但是，当两个数据相差很大时，连续整数检测算法可能会比分解质
6、因数算法占优势；当两个数所得到的最大质因数都较小时，分解质因数算法可能比连续整数检测算法占优势。三、所用仪器、材料（设备名称、型号、规格等或使用软件）1 台 PC 及 Visual Studio 2005 软件四、实验方法、步骤（或：程序代码或操作过程）/ 两个正整数最大公约数求解简易系统.cpp : 定义控制台应用程序的入口点。/*该系统是为了计算两个正整数的最大公约数*该系统是在Visual Studio 2005环境下编辑的，并通过Visual Studio 2005环境下编译与运行*该版本使用了Boost函数库中的timer.hpp库函数，关于boost函数库可以参考网络上的boost
7、社区*该程序制作人刘召*该系统创建时间是2011年10月12日*/#include stdafx.h#include#include#include#include#include#include using namespace std;using namespace boost;long long smallerNumber(long long i,long long j)return i& List)long long x=(long long)(i/2),j=i;for(long long g=2;g*List1,list*List2,list*plist)long long count
8、=1;zhiYinShuPanDuan(m,*List1);zhiYinShuPanDuan(n,*List2);list:iterator it,rt,yt,gt=(*List2).begin();for(it=(*List1).begin();it!=(*List1).end();it+)long long a=1,b=1;yt=it;yt+;while(yt!=(*List1).end()&*yt=*it)yt+;a+;it+;-9-for(rt=gt;rt!=(*List2).end();rt+)if(*it=*rt)gt=rt;gt+;while(gt!=(*List2).end()
9、&*gt=*rt)gt+;b+;for(long long h=0;hpush_back(*it);break;*p=count;void menu1()cout$：$： ;cinm;cout$：;cinn;void menu()cout$ ：&List)if(List.size()cout:iterator it;for(it=List.begin();it!=List.end();it+)cout&plist)if(plist.size()cout:iterator it;for(it=plist.begin();it!=plist.end();it+)coutk;cout List1,L
10、ist2,plist;system(color 2b);while(k0&kk;coutk;cout$：21请输入你所要运算的第二个整数$：-17-1用连续整数检测算法进行运算! 2用欧几里得算法进行运算!3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：1连续整数检测算法所用时间为：11.453 秒(最高精确度毫秒级)经连续整数检测算法运算所得 21 和的最大公约数是：11用连续整数检测算法进行运算! 2用欧几里得算法进行运算!3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：2欧几里得算法所用时间为：0 秒(最高精确度毫秒级)经欧几里得算法运算所
11、得 21 和的最大公约数是：11用连续整数检测算法进行运算! 2用欧几里得算法进行运算!3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：3分解质因数算法所用时间为：0.06 秒(最高精确度毫秒级)整数 21 共有 4 个质数，它们分别是：3 11 18149 整数共有 3 个质数，它们分别是：7 43 整数 21 和没有公共质数！经分解质因数算法运算所得 21 和的最大公约数是：11用连续整数检测算法进行运算! 2用欧几里得算法进行运算!3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：4-18-1进行下一对整数最大公约数运算！ 2退出本系统！请输
12、入你的选择$：1请输入你所要运算的第一个整数$：请输入你所要运算的第二个整数$：21用连续整数检测算法进行运算! 2用欧几里得算法进行运算!3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：1连续整数检测算法所用时间为：98.5 秒(最高精确度毫秒级)经连续整数检测算法运算所得和 2 的最大公约数是：1用连续整数检测算法进行运算! 2用欧几里得算法进行运算!3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：2欧几里得算法所用时间为：0 秒(最高精确度毫秒级)经欧几里得算法运算所得和 2 的最大公约数是：1用连续整数检测算法进行运算! 2用欧几里得算法
13、进行运算!3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：3分解质因数算法所用时间为：0 秒(最高精确度毫秒级)整数共有 11 个质数，它们分别是：3 3 3 7 7 7 11 13 13 1723整数 2 共有 13 个质数，它们分别是：2 2 3 3 3 7 7 11 13 17-19-19 29 31整数和 2 共有 8 个公共质数，它们分别是：3 3 3 7 7 11 13 17经分解质因数算法运算所得和 2 的最大公约数是：1用连续整数检测算法进行运算! 2用欧几里得算法进行运算!3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：41进行
14、下一对整数最大公约数运算！ 2退出本系统！请输入你的选择$：1请输入你所要运算的第一个整数$：请输入你所要运算的第二个整数$：5701用连续整数检测算法进行运算! 2用欧几里得算法进行运算!3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：1连续整数检测算法所用时间为：10.92 秒(最高精确度毫秒级)经连续整数检测算法运算所得和 570 的最大公约数是：13021用连续整数检测算法进行运算! 2用欧几里得算法进行运算!3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：2欧几里得算法所用时间为：0 秒(最高精确度毫秒级)经欧几里得算法运算所得和 570 的最大公约数是：13021用连续整数检测算法进行运算! 2用欧几里得算法进行运算!-20-3用分解质因数算法进行运算! 4结束对这两个数的运算！请输入你的选择$：3分解质因数算法所用时间为：
