编程之美2.7 最大公约数
方法一： 辗转相除法
x = k * y + b （k = x / y , b = x % y）
若一个数能够被x和y同时整除，则必然也能够被y和b同时整除。故可以建立一个递归方程式
gcd(x , y) = gcd(y , x % y)
代码如下：
int gcd(int x , int y)
{
return (y == 0 )?x :gcd(y , x % y) ;
}
方法二：两数相减法
若一个整数能够同时被x ,y整除，则必然也能够被x-y,y整除。
因为取余操作消耗时间比较多，所以采取想减操作来计算。
int gcd2(int x , int y)
{
if(x < y)
return gcd2(y , x) ;
else if(y == 0)
return x ;
else
return gcd2(x - y , y) ;
}
方法三： 综合利用上述两种解法
主要的目的是既想减少取余操作的复杂度，又想进一步减少辗转想减法的迭代次数。
首先我们注意，若有y = k * y1 ,且 x = k * x1。
则gcd(x , y) = k * gcd(y1 , x1)
(2)若有 x = p * x1 ,且p是一个素数，且y % p != 0
则有f(x , y) = f(x1 , y)
我们主要考虑2这个素数，分析如下：
若x和y均是偶数则 f(x , y) =2 * f(x>>1 , y>>1)
若x为偶数，y为奇数，则f(x,y) = f(x>>1 , y)
若x为奇数，y为偶数，则f(x,y) = f(x , y>>1)
若x为奇数，y为奇数，则f(x,y) = f(x-y , y) ,则必有x-y为偶数。
int gcd3(int x , int y)
{
if(x < y)
return gcd3(y , x) ;
if(y == 0)
return x ;
if(isEven(x)) //x为奇数
{
if(isEven(y)) //y为奇数
return gcd3(x - y , y) ;
else //y为偶数
return gcd3(x , y >>1) ;
}
else //x为偶数
{
if(isEven(y)) //y为奇数
return gcd3(x >> 1 , y) ;
else //y为偶数
return 2 * gcd3(x >> 1, y >> 1) ;
}
}