求最大公约数的5种算法
一、题目要求
运行最大公约数的常用算法，并进行程序的调式与测试（至少比较4种GCD算法在给定不同规模测试数据的情况下的平均运行时间），要求程序设计风格良好，并添加异常处理模块（如输入非法等）。
二、设计思路
利用随机函数rand()生成两个一维数组（20个数），然后用户可以选择自己想要用的方法的序号，进行运算，然后利用计时函数计算出算法运行的时间。
三、算法流程图
1.辗转相除法（嵌套调用）
其算法过程为： 前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数
1、大数放a中、小数放b中；
2、求a/b的余数；
3、若temp=0则b为最大公约数；
4、如果temp!=0则把b的值给a、temp的值给a；
5、返回第二步；
递归调用的流程图如下：
2.穷举法
穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。
定义：对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
流程图如下：
3.更相减损法
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。
算法流程图如下：
4.Stein法
整理一下，对两个正整数 x>y ：
1.均为偶数 gcd( x,y ) =2gcd( x/2,y/2 )；
2.均为奇数 gcd( x,y ) = gcd( (x+y)/2,(x-y)/2 )；
2.x奇y偶 gcd( x,y ) = gcd( x,y/2 )；
3.x偶y奇 gcd( x,y ) = gcd( x/2,y ) 或 gcd( x,y )=gcd( y,x/2 )；
现在已经有了递归式，还需要再找出一个退化情况。注意到 gcd( x,x ) = x ，就用这个。
流程图如下：
四、算法实现
在这里插入代码片
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<windows.h>
#include<iostream.h>
//辗转相除法
//函数嵌套调用
int divisor1 (int a,int b) /*自定义函数求两数的最大公约数*/
{
int temp; /*定义整型变量*/
if(a<b) /*通过比较求出两个数中的最大值和最小值*/
{
temp=a;
a=b;
b=temp;
} /*设置中间变量进行两数交换*/
while(b!=0) /*通过循环求两数的余数，直到余数为0*/
{
temp=a%b;
a=b; /*变量数值交换*/
b=temp;
}
return (a); /*返回最大公约数到调用函数处*/
}
//函数递归调用
int gcd1(int a,int b)
{
if(a%b==0)
return b;
else
return gcd1(b,a%b);
}
//穷举法
int divisor2 (int a,int b) /*自定义函数求两数的最大公约数*/
{
int temp; /*定义义整型变量*/
temp=(a>b)?b:a; /*采种条件运算表达式求出两个数中的最小值*/
while(temp>0)
{
if (a%temp==0&&b%temp==0) /*只要找到一个数能同时被a,b所整除，则中止循环*/
break;
temp--; /*如不满足if条件则变量自减，直到能被a,b所整除*/
}
return (temp); /*返回满足条件的数到主调函数处*/
}
//更相减损法
int gcd2(int m,int n)
{
int i=0,temp,x;
while(m%2==0 && n%2==0) //判断m和n能被多少个2整除
{
m/=2;
n/=2;
i+=1;
}
if(m<n) //m保存大的值
{
temp=m;
m=n;
n=temp;
}
while(x)
{
x=m-n;
m=(n>x)?n:x;
n=(n<x)?n:x;
if(n==(m-n))
break;
}
if(i==0)//代表前面的代码没有运行，无最大公约数
return n;
else
return (int )pow(2,i)*n;
}
//Stein算法
//非递归调用
int Stein( unsigned int x, unsigned int y )
/* return the greatest common divisor of x and y */
{
int factor = 0;
int temp;
if ( x < y )
{
temp = x;
x = y;
y = temp;
}
if ( 0 == y )
{
return 0;
}
while ( x != y )
{
if ( x & 0x1 )
{/* when x is odd */
if ( y & 0x1 )
{/* when x and y are both odd */
y = ( x - y ) >> 1;
x -= y;
}
else
{/* when x is odd and y is even */
y >>= 1;
}
}
else
{/* when x is even */
if ( y & 0x1 )
{/* when x is even and y is odd */
x >>= 1;
if ( x < y )
{
temp = x;
x = y;
y = temp;
}
}
else
{/* when x and y are both even */
x >>= 1;
y >>= 1;
++factor;
}
}
}
return ( x << factor );
}
int main()
{
int k,flag;
clock_t start,stop;
//利用随机函数生成二十个数
srand((int)time(NULL));//利用时间函数time()，产生每次不同的随机数种子
int a1[10],a2[10],i;
for(i=0; i<10;i++)
{
a1[i]=rand()%100+1; //rand()%100用于产生0-100之间的随机数
}
for(i=0; i<10;i++)
{
a2[i]=rand()%100+1; //rand()%100用于产生0-100之间的随机数
}
cout<<"以下是随机产生的两个一维数组"<<endl;
for(i=0; i<10;i++)
{
printf("%d\t",a1[i]);
}
printf("\n");
for(i=0; i<10;i++)
{
printf("%d\t",a2[i]);
}
printf("\n");
//菜单选择（选择你想用的方法）
cout<<"****** 1.辗转相除法(嵌套调用)******"<<endl;
cout<<"****** 2.辗转相除法(递归调用) ******"<<endl;
cout<<"****** 3.穷举法 ******"<<endl;
cout<<"****** 4.更相减损法(等值算法) ******"<<endl;
cout<<"****** 5.Stein算法(非递归调用) ******"<<endl;
cout<<"****** 请输入你的选择******"<<endl;
cin>>k;
//计算5种算法的平均运行时间
while(k<6)
{
switch(k)
{
case 1:
start = clock(); //计时函数：clock()
for(i=0; i<10;i++)
{
cout<<"最大公约数为："<<divisor1(a1[i],a2[i])<<endl;
}
stop=clock();
cout<<"计算第"<<k<<"种算法的执行时间为："<<((double)(stop-start))/CLOCKS_PER_SEC<<"秒"<<endl;
break;
case 2:
start = clock(); //计时函数：clock()
for(i=0; i<10;i++)
{
cout<<"最大公约数为："<<gcd1(a1[i],a2[i])<<endl;
}
stop=clock();
cout<<"计算第"<<k<<"种算法的执行时间为："<<((double)(stop-start))/CLOCKS_PER_SEC<<"秒"<<endl;
break;
case 3:
start = clock(); //计时函数：clock()
for(i=0; i<10;i++)
{
cout<<"最大公约数为："<<divisor2(a1[i],a2[i])<<endl;
}
stop=clock();
cout<<"计算第"<<k<<"种算法的执行时间为："<<((double)(stop-start))/CLOCKS_PER_SEC<<"秒"<<endl;
break;
case 4:
start = clock(); //计时函数：clock()
for(i=0; i<10;i++)
{
cout<<"最大公约数为："<<gcd2(a1[i],a2[i])<<endl;
}
stop=clock();
cout<<"计算第"<<k<<"种算法的执行时间为："<<((double)(stop-start))/CLOCKS_PER_SEC<<"秒"<<endl;
break;
case 5:
start = clock(); //计时函数：clock()
for(i=0; i<10;i++)
{
cout<<"最大公约数为："<<Stein(a1[i],a2[i])<<endl;
}
stop=clock();
cout<<"计算第"<<k<<"种算法的执行时间为："<<((double)(stop-start))/CLOCKS_PER_SEC<<"秒"<<endl;
break;
default:cout<<"输入有误"<<endl;
}
cout<<"是否想继续，退出按0"<<endl;
cin>>flag;
if(flag==0)
break;
else k=flag;
}
return 0;
}
五、调试
对各五算法求取最大公约数功能一一取值调试验证。
（一）辗转相除法（嵌套）
由主函数传递参数到该算法函数的两个整数为31和68
程序运行后返回的值a为1，符合预期结果。
（二）辗转相除法（递归）
由主函数传递参数到该算法函数的两个整数为100和54
100和54的最大公约数为2
程序运行返回的值为2，符合预期结果。
（三）穷举法
由主函数传递参数到该算法函数的两个整数为87和39
87和39的最大公约数为3
程序运行返回的值为3，符合预期结果。
（四）更相减损法
由主函数传递参数到该算法函数的两个整数为20和51
20和51的最大公约数为1
程序运行返回的值为1，符合预期结果。
（五）Stein算法（非递归）
由主函数传递参数到该算法函数的两个整数为95和20
95和20的最大公约数为5
程序运行返回的值为5，符合预期结果。
六、测试
1、针对5种算法各自功能的测试，首先测试每种算法求最大公约数的正确性。为了直观的得出结论，利用随机函数生成10组数来判断。结果如下：
方法1.
方法2.
方法3.
方法4.
方法5.
经检验，这5种算法的10组数据的最大公约数输出结果不仅完全相同，并且符合预期结果。
2、下面我们来比较这5种算法运行时间
在10组数据下，5种算法的运行时间顺序是Stein>更相减损法=穷举法辗转相除法（递归）>辗转相除法（嵌套）；
在50组数据下的运行时间如下：
5种算法的运行时间顺序：Stein>更相减损法>穷举法>辗转相除法（递归）>辗转相除法（嵌套）；
在100组数据下的运行时间如下：
5种算法的运行时间顺序：
辗转相除法（嵌套）>辗转相除法（递归）=穷举法>Stein>更相减损法
在150组数据下的运行时间如下：
5种算法的运行时间顺序：穷举法>辗转相除法（嵌套）>辗转相除法（递归）>Stein>更相减损法;
七、实验心得
在该程序的设计中，大体思路是这样的：
（1）利用随机函数rand()随机生成1~100的数，可以用两个一维数组来存放这些数据。
（2）利用菜单功能形式，给用户提供选，用户根据提供的6种算法选择输入算法的
号即可执行该算法；
（4）在计算程序运行时间，会利用time库函数的函数clock()函数来获取执行该步骤的时间，即可计算出该算法执行的时间。（利用ctime库的函数clock()获取执行某算法步骤的时间，利用start和end变量求取时间，利用时间差即可得出执行时间。clock()函数的返回值是毫秒，返回值类型为浮点型；想要把它换成秒，直接除以CLOCKS_PER_SEC（宏定义为 1000）。）
通过这次的学习，掌握了时间函数，随机函数以及5种求最大公约数的方法，对以后编写程序有很大的帮助。