公约数

admin管理员组

文章数量:1794759

公约数

四种算法求最大公约数及运行时间的比较

1.问题描述

运行最大公约数的常用算法，并进行程序的调试与测试，要求程序性设计风格良好。

2.解题思路

首先清楚求最大公约数的4种常用算法：辗转相除法、穷举法、更相减损法、Stein算法及其实现步骤。然后将每种算法单独写出，进行编译运行，改正错误，尤其注意头文件是否需要增加。最后，将4种算法合并，构成4个成员函数和1个main( )函数。注意4个函数的返回值。运行无误后添加计算平均运行时间函数，多组数据输入语句。

3.算法构造

辗转相除法流程图：

穷举法流程图：

更相减损法流程图：

Stein算法流程图：

4.算法实现

 #include<iostream>#include<conio.h>#include<math.h> //更相减损法的return值中的pow需要该头文件#include<time.h> //时间的计算需要time头文件using namespace std;int divisor1 (int a,int b)  //辗转相除法求最大公约数{int temp;if(a<b)  {int t;t=a;a=b;b=t;}temp=a%b;while(temp==0)//当a/b的最大公约数为breturn b ;while(temp!=0) {a=b;b=temp;temp=a%b;} return b;

}

int divisor2(int a,int b)  //穷举法求最大公约数

{

   int temp;temp=(a>b)?b:a;while(temp>0){if(a%temp==0&&b%temp==0)break;temp--;}return temp;

}

int gcd(int a,int b)  //更相减损法求最大公约数

{

   int i=0;int temp,x;while(a%2==0 && b%2==0){a/=2;b/=2;i+=1;}if(a<b){temp=a;a=b;b=temp;}while(x){x=a-b;a=(b>x)?b:x;b=(b<x)?b:x;if(b==(a-b))break;}if(i==0)return b;elsereturn (int)pow(2,i)*b;

}

int stein(int a,int b)  //stein算法求最大公约数

{

   int factor=0;int temp;if(a<b){temp=a;a=b;b=temp;}if(0==b)return 0;while(a!=b){if(a&0x1) //当x是偶数{if(b&0x1) //当x、y都是偶数{b=(a-b)>>1;a-=b;}else //当x是偶数，y是奇数b>>=1;}else //当x是奇数{if(b&0x1) //x是奇数，y是偶数{a>>=1;if(a<b){temp=a;a=b;b=temp;}}else //x、y都是奇数{a>>=1;b>>=1;++factor;}}}return(a<<factor); //a左移一位，相当于a乘2

}

int main()

{

   int a,b;int c,m,x;int w;int i;clock_t start,finish; //clock_t是clock函数的返回类型double totaltime;srand(time(0));//用来设置rand()产生随机数时的随机数种子，time(0)是返回现在的系统时间，并将它转换成内部格式时间//输入多组数据int array1[25];int array2[25];cout<<"请输入a: ";for(i=0;i<25;i++){array1[i]=rand()%500;cout<<array1[i]<<"    ";}cout<<endl;cout<<"请输入b: ";for(i=0;i<25;i++){array2[i]=rand()%500;cout<<array2[i]<<"    ";}cout<<endl;//循环4次确保4个算法是在相同数据下运行的for(int q=1;q<5;q++){cout<<"请输入数字选择算法: ";cin>>w;switch (w){case 1: start=clock(); //开始计时cout<<"辗转相除法求最大公约数: "<<endl; int divisor1(int,int); for(i=0;i<25;i++){a=array1[i];b=array2[i];c=divisor1(a,b); cout<<"最大公约数是: "<<c<<endl;}//程序运行时间的计算finish=clock();totaltime=(double)(finish-start)/CLOCKS_PER_SEC;//计算总时间多长cout<<"该算法运行时间为"<<totaltime<<"秒! "<<endl;break;case  2: start=clock(); //开始计时cout<<"穷举法求最大公约数: "<<endl;int divisor2 (int,int) ;for(i=0;i<25;i++){a=array1[i];b=array2[i];b=divisor2(a,b);cout<<"最大公约数是: "<<b<<endl;}finish=clock();totaltime=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"该算法运行时间为"<<totaltime<<"秒! "<<endl;break;case 3: start=clock(); //开始计时cout<<"更相减损法求最大公约数: "<<endl; int gcd(int,int);for(i=0;i<25;i++){a=array1[i];b=array2[i];m=gcd(a,b);cout<<"最大公约数是: "<<m<<endl;}finish=clock();totaltime=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"该算法运行时间为"<<totaltime<<"秒! "<<endl;break;case 4: start=clock(); //开始计时cout<<"stein算法求最大公约数: "<<endl; int stein(int,int);for(i=0;i<25;i++){a=array1[i];b=array2[i];x=stein(a,b);cout<<"最大公约数是: "<<x<<endl;}finish=clock();totaltime=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"该算法运行时间为"<<totaltime<<"秒! "<<endl;break;default: cout<<"请重新输入!"<<endl; break;}}return 0;

}

5.程序测试及运行结果

（1）.辗转相除法

     #include<iostream>using namespace std;int divisor1(int a,int b)  //辗转相除法求最大公约数{int temp;if(a<b) {int t;t=a;a=b;b=t;}temp=a%b;while(temp==0)//当a/b的最大公约数为breturn b;while(temp!=0) {a=b;b=temp;temp=a%b;} return b;

}

int main()

{

   int a,b;cout<<"请输入a: ";cin>>a;cout<<"请输入b: ";cin>>b;int divisor1(int,int);a=divisor1(a,b);cout<<"最大公约数是: "<<a<<endl;return 0;

}

（2）.穷举法

     #include<iostream>using namespace std;int divisor2(int a,int b)  //穷举法求最大公约数{int temp;temp=(a>b)?b:a;while(temp>0){if(a%temp==0&&b%temp==0)break;temp--;}return temp;

}

int main()

{

   int a,b;cout<<"请输入a: ";cin>>a;cout<<"请输入b: ";cin>>b;int divisor2(int,int);a=divisor2(a,b);cout<<"最大公约数是: "<<a<<endl;return 0;

}

（3）.更相减损法

     #include<iostream>#include<math.h>using namespace std;int gcd(int a,int b) //更相减损法求最大公约数{int i=0;int temp,x;while(a%2==0&& b%2==0){a/=2;b/=2;i+=1;}if(a<b){temp=a;a=b;b=temp;}while(x){x=a-b;a=(b>x)?b:x;b=(b<x)?b:x;if(b==(a-b))break;}if(i==0)return b;elsereturn (int)pow(2,i)*b;

}

int main()

{

   int a,b;cout<<"请输入a: ";cin>>a;cout<<"请输入b: ";cin>>b;int gcd(int,int);a=gcd(a,b);cout<<"最大公约数是: "<<a<<endl;return 0;

}

（4）.Stein算法

    #include<iostream>using namespace std;int stein(int a,int b) //stein算法求最大公约数{int actor=0;int temp;if(a<b){temp=a;a=b;b=temp;}if(0==b)return 0;while(a!=b){if(a&0x1){if(b&0x1){b=(a-b)>>1;a-=b;}elseb>>=1;}else{if(b&0x1){a>>=1;if(a<b){temp=a;a=b;b=temp;}}else{a>>=1;b>>=1;++factor;}}}return(a<<factor);

}

int main()

{

   int a,b;cout<<"请输入a: ";cin>>a;cout<<"请输入b: ";cin>>b;int Stein(int,int);a=Stein(a,b);cout<<"最大公约数是: "<<a<<endl;return 0;

}

（5）.最终程序运行结果

用srand( )函数随机给出一系列数据，依次选择4种算法，发现最大公约数相同，每个算法后面都有相应的运行时间，辗转相除法是0.082秒，穷举法是0.199秒，更相减损法是0.192秒，Stein算法是0.18秒。在此组数据测试下，辗转相除法运行时间最短。

6.经验归纳

此次程序是4种算法求最大公约数，编写后有以下总结：

1 4种算法，更相减损法和Stein算法的解题步骤誊写了已有的代码，之后仔细看，Stein算法中主要使用了移位和加减法，理解过程很困难，还需要再看看有关移位的知识。

2.srand()伪随机种子的使用。输入多组数据是一开始的想法，但后来发现手动输入数据有限而且麻烦，就选择使用了srand()作为随机数种子设置rand()函数产生随机数。这样一来，每次运行数据都不同，不能比较各算法运行时间。 因此，需要一次运行可以同时选择4个算法计算，即在switch语句（用来选择一种算法）的基础上加上for至少可以进行4次循环，从而选择4次不同的算法。实现一次运行，同组数据，4种算法计算所有的最大公约数，然后输出4个时间。

3.学习添加计时函数clock()函数计算程序运行时间。首先需要一个头文件：time.h 其次确定计时和结束时间的位置，start=clock()放在选择算法几的地方，finish=clock()放在输出最大公约数语句后。明白clock_t是clock（）函数的返回类型。
最后是总时间totaltime语句totaltime=(double)(finish-start)/CLOCKS_PER_SEC;CLOCKS_PER_SEC表示每一秒有多少个时钟计时单元。

4.在srand()种子中需要一个time(0),表示返回现在系统的时间并转换为内部格式时间。不加上的话会显示一个函数参数数量或类型不匹配之类的错误。

本文标签： 公约数