四种算法实现最大公约数并机计算运行时间
一、题目：求一组数的最大公约数
题目要求：
分别采用 ：
<1>辗转相除法 （非递归和递归），
<2>穷举法，
<3>更相减损法，
<4>Stein算法（非递归和递归）
计算一组数据求得最大公约数，并对各种算法的运行时间进行比较。
首先需要知道：假设两个数A、B的最大公约数为k，那么（A-B）、（A%B）的值也肯定是k的倍数。
二、算法分析
<1>、辗转相除法
辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理：
两个正整数a、b (a>b)，它们的最大公约数等于 a 除以 b 的余数 c 和 b 之间的最大公约数。
其算法过程为：
前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数
1、大数放a中、小数放b中；
2、求a/b的余数；
3、若temp=0则b为最大公约数；
4、如果temp!=0则把b的值给a、temp的值给a；
5、返回第二步；
<2>、穷举法（利用数学定义）
穷举法（也叫枚举法）穷举法求两个正整数的最大公约数的解题步骤：
从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 。
①定义1：对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
②定义2：对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除，则该和数即为所求的最小公倍数。
<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 )；
（3）、x奇y偶 gcd( x,y ) = gcd( x,y/2 )；
（4）、x偶y奇 gcd( x,y ) = gcd( x/2,y ) 或 gcd( x,y )=gcd( y,x/2 )；
现在已经有了递归式，还需要再找出一个退化情况。注意到 gcd( x,x ) = x ，就用这个。
在这里插入代码片
#include<stdio.h>
#incl
ude<math.h>
#include<time.h>
#include<windows.h>
int num[1000][2], grop=20, out[6][1000];
//out[6][1000]存储组大公约数，6表示6个算法函数。grop表示有20组数据。num[1000][2]存放20组数据。
//辗转相除法
int divisor1(int a,int b) //自定义函数求两数的最大公约数
{
int temp ;
if( a < b ) //使得a必须大于b
{
temp = b ；
b = a ;
a = temp ;
}
while(b!=0)
{
temp = a % b ;
a = b ;
b = temp ;
}
return ( a ) ; //返回最大公约数
}
int gcd ( int a, int b ) //辗转相除法的函数递归调用
{
if ( a % b == 0 )
return b ;
else
return gcd ( 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 )
break ;
temp--;
}
return (temp);
}
int gcd1 ( int m, int n ) //更相减损法
{
int i = 0, temp, x ;
while ( m % 2 == 0 && n % 2 == 0 )
{
m / = 2 ;
n / = 2 ;
i + = 1 ;
}
if ( m < n )
{
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 ) //函数非递归调用
{
int factor=0,temp;
if ( x < y )
{
temp = x ;
x = y ;
y = temp ;
}
if ( y == 0 )
return x ；
while ( x != y )
{
if( x & 0x 1)
{
if( y & 0x1)
{
y = ( x -y ) >> 1 ;
x -=y ;
}
else
{
y >>= 1 ;
}
}
else
{
if( y & 0x1 )
{
x >>= 1 ;
if ( x < y )
{
temp = x ;
x = y ;
y = temp ;
}
}
else
{
x >>= 1 ;
y >>= 1 ;
factor ++ ;
}
}
}
return (x<<factor);
}
int gcd2( int u, int v) //函数递归调用
{
if ( u == 0 ) return v ;
if ( v == 0) return u ;
if ( ~u & 1)
{
if ( v & 1)
return gcd2 ( u >> 1, v ) ;
else
return gcd2 ( u >> 1, v >> 1 ) << 1 ;
}
if ( ~v & 1)
return gcd2 ( u, v >> 1) ;
if ( u > v )
return gcd2 ( ( u - v ) >> 1 , v ) ;
return gcd2 ( ( v - u ) >> 1, u) ;
}
int Create() //产生20组随机正整数
{
int h=10,t=100 ;
for( int i = 0; i < grop; i++ )
{
for(int j=0; j<2;j++)
{
srand ( time ( NULL ) ) ;
num[i][j] = rand() % ( t-h+1 ) + h ;
h += 30 ; t += 50 ;
}
h += 100 ; t += 100 ;
}
return 0;
}
void show()
{ int option, k=0;
clock_t start, finish;
double TheTimes;
printf("-----------------------\n");
printf(" 1、辗转相除法 \n");
printf(" 2、穷举法 \n");
printf(" 3、更相减损法 \n");
printf(" 4、Stein算法 \n");
printf("-----------------------\n");
for( int j = 0; j < 6; j ++ )
{
start = clock () ;
k=0;
for(int i=0; i<grop; i++)
{
switch(j+1)
{
case 1 :
out[0][k]= divisor1 (num[i][0],num[i][1]);
break;
case 2 :
out[1][k]= gcd (num[i][0],num[i][1]);
break;
case 3 :
out[2][k]= divisor2 (num[i][0],num[i][1]);
break;
case 4 :
out[3][k]= gcd1(num[i][0],num[i][1]);
break;
case 5 :
out[4][k]= Stein (num[i][0],num[i][1]);
break;
case 6 :
out[5][k]= gcd2 (num[i][0],num[i][1]);
break;
}
printf("第%d组数据的最大公约数: %d ",i+1,out[j][k]);
if((i+1)%2==0)
printf("\n");
k++;
}
finish = clock();
TheTimes = static_cast<double>(finish-start)/CLOCKS_PER_SEC; //计算时间
printf("第%d种算法所用时间：%lf s\n\n\n\n\n",j+1,TheTimes);
}
}
int main()
{ Create () ;
for( int i=0; i<grop; i++)
printf( "%d %d\n", num[i][0], num[i][1] );
show () ;
return 0;
}
四、经验归纳遇到的问题：
start=clock();
······
finish = clock();
TheTimes = static_cast((finish-start)/CLOCKS_PER_SEC);
输出的 TheTime 总是 0.0000000 s
解决方案：去掉一对括号，
使成为：TheTimes = static_cast(finish-start)/CLOCKS_PER_SEC;
原因：括号改变了运算的优先级
clock()返回类型为clock_t类型；
clock_t实际为long类型，typedef long clock_t;
CLOCKS_PER_SEC：表示一秒钟会有多少个时钟计时单元，也就是硬件滴答数。