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

实验报告实验项目: 求最大公约数姓名: 刘春迪学号: 11081602071. 实验题目: 求两个自然数的最大公约数2. 实验目的: (1) 复习数据结构课程相关知识,实现课程之间的平滑过渡;(2) 掌握并应用算法的数学分析和后验分析方法;(3) 理解:不同算法能够解决相同问题,这些算法解题思路不同,复杂程度不同,解题效率也不同.3. 实验要求: (1) 至少设计出三个版本的求最大公约数算法;(2) 对所设计的算法采用大O符号进行时间复杂度分析(3) 上机实现算法,并用计数法和计时法分别测算算法的运行时间(4) 通过对比分析得出自己的结论.4. 算法描述:(1) 扫描算法(蛮力)temp = min(m,n);while(temp)if(m%temp=0%n%temp=0)/公约数定义break;temp-;方法直观,但是效率较低.时间复杂度为O(n) (2) 辗转相除法Int gcd(m,n)m=max(m,n)n=min(m,n)if(m%n=0)return nelsereturn gcd(m,m%n)时间复杂度为 O(log n)(3) 因式分解法int gcd(m,n)while(in)if(n%i=0)j+;aj=i;n=n/i;else i+;j+while(i=j) i+;i=2;j=0; while(im)if(m%i=0)j+;bj=i;m=m/i;else i+;j+;while(i=j) i+;int k=1;for(i=1;i=j;i+)for(k=1;k1)k=k*ch*ch-1;h=h-2;if(h=1)k=k*c1;return k;else return k;时间复杂度为O(n2)5. 实验结果与结论: 在时间性能上,辗转相除法在大多数情况下明显优于其他两种算法,尤其是在两个输入的自然数比较大的时候,如图所示对于扫描法和分解因式法,扫描法比较适合两个自然数本身有倍数关系的,而当两个自然数都比较大的时候分解因式法要比搜索法效率高出很多.附录:代码清单#include#include#includeusing namespace std;/-int count=0;clock_t GCD_start,GCD_end;/-int GreatestCommonDivisor_M(int a,int b)count=0;int temp;if(ab)temp=b;else temp=a;while(temp)count+;if(a%temp=0&b%temp=0)break;else temp=temp-1;return temp;int GreatestCommonDivisor_Z(int a,int b)count=0;int r;r=a%b;while(r!=0)a=b; b=r; r=a%b;count+;return b;int GreatestCommonDivisor_F(int m,int n)count=0;int i=2,j=0,h=0;int a100,b100,c100;while(in)if(n%i=0)j+;aj=i;n=n/i;count+;elsei+;count+;j+;aj=n;i=1;int u;u=j;while(i=j) i+; count+;i=2;j=0; while(im)if(m%i=0)count+;j+;bj=i;m=m/i;elsecount+;i+;j+;bj=m;i=1;while(i=j) count+; i+;int k=1;for(i=1;i=j;i+)for(k=1;k1)count+;k=k*ch*ch-1;h=h-2;if(h=1)k=k*c1;return k;else return k;void main()int a,b,i=0,result;cout-求最大公约数的三种算法对比-endl;coutab;GCD_start = clock();for(i=0;i100000;i+)GreatestCommonDivisor_M(a,b);GCD_end = clock();cout-搜索法-endl;cout运行次数:count运行时间:GCD_end-GCD_starte-6endl;cout最大公约数:GreatestCommonDivisor_M(a,b)endl;cout-endl;GCD_start = clock();for(i=0;i100000;i+)GreatestCommonDivisor_Z(a,b);GCD_end = clock();cout-辗转相除-endl;cout运行次数:count运行时间:GCD_end-GCD_starte-6endl;cout最大公约数:GreatestCommonDivisor_Z(a,b)endl;cout-endl;GCD_start = clock();for(i=0;i100000;i+)GreatestCommonDivisor_F(a,b);GCD_end = clock();cout-分解因式-endl