算法设计最大公约数扫描辗转因式分解

算法设计最大公约数扫描辗转因式分解

ID:42676245

大小:143.68 KB

页数:9页

时间:2019-09-19

算法设计最大公约数扫描辗转因式分解_第1页
算法设计最大公约数扫描辗转因式分解_第2页
算法设计最大公约数扫描辗转因式分解_第3页
算法设计最大公约数扫描辗转因式分解_第4页
算法设计最大公约数扫描辗转因式分解_第5页
资源描述:

《算法设计最大公约数扫描辗转因式分解》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、实验报告实验项目:求最大公约数姓名:刘春迪学号:11081602071.实验题目:求两个自然数的最大公约数2.实验目的:(1)复习数据结构课程相关知识,实现课程之间的平滑过渡;(2)掌握并应用算法的数学分析和后验分析方法;(3)理解:不同算法能够解决相同问题,这些算法解题思路不同,复杂程度不同,解题效率也不同.3.实验要求:(1)至少设计出三个版本的求最大公约数算法;(2)对所设计的算法采用大O符号进行时间复杂度分析(3)上机实现算法,并用计数法和计时法分别测算算法的运行时间(4)通过对比分析得出自己的结论.4.算法描述:(1)扫描算法(蛮力)te

2、mp=min(m,n);while(temp){if(m%temp==0%%n%temp==0)//公约数定义{break;}temp--;}方法直观,但是效率较低.时间复杂度为O(n)(1)辗转相除法Intgcd(m,n){m=max(m,n)n=min(m,n)if(m%n==0)returnnelsereturngcd(m,m%n)}时间复杂度为O(logn)(2)因式分解法intgcd(m,n){while(i

3、j=0;while(i1){k=k*c[h]*c[h-1];h=h-2;}if(h==1){k=k*c[1];returnk;}elsereturnk;}时间复杂度为O(n2)5

4、.实验结果与结论:在时间性能上,辗转相除法在大多数情况下明显优于其他两种算法,尤其是在两个输入的自然数比较大的时候,如图所示对于扫描法和分解因式法,扫描法比较适合两个自然数本身有倍数关系的,而当两个自然数都比较大的时候分解因式法要比搜索法效率高出很多.附录:代码清单#include#include#includeusingnamespacestd;//---------------intcount=0;clock_tGCD_start,GCD_end;//---------------intGr

5、eatestCommonDivisor_M(inta,intb){count=0;inttemp;if(a>b)temp=b;elsetemp=a;while(temp){count++;if(a%temp==0&&b%temp==0)break;elsetemp=temp-1;}returntemp;}intGreatestCommonDivisor_Z(inta,intb){count=0;intr;r=a%b;while(r!=0){a=b;b=r;r=a%b;count++;}returnb;}intGreatestCommonDiviso

6、r_F(intm,intn){count=0;inti=2,j=0,h=0;inta[100],b[100],c[100];while(i

7、j){count++;i++;}intk=1;for(i=1;i<=j;i++){for(k=1;k<=u;k++){if(b[i]==a[k]){count++;h++;c[h]=a[k];a[k]=a[k+1];break;}}}k=1;while(h>1){count++;k=k*c[h]*c[h-1];h=h-2;}if(h==1){k=k*c[1];returnk;}elsereturnk;}voidmain(){inta,b,i=0,result;cout<<"----------------求最大公约数的三种算法对比---------

8、-----"<>a>>b;GCD_start=clock();fo

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。