編程之美2.7 最大公約數(shù)
方法一： 輾轉(zhuǎn)相除法
x = k * y + b （k = x / y , b = x % y）
若一個數(shù)能夠被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) ;
}
方法二：兩數(shù)相減法
若一個整數(shù)能夠同時被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) ;
}
方法三： 綜合利用上述兩種解法
主要的目的是既想減少取余操作的復(fù)雜度，又想進一步減少輾轉(zhuǎn)想減法的迭代次數(shù)。
首先我們注意，若有y = k * y1 ,且 x = k * x1。
則gcd(x , y) = k * gcd(y1 , x1)
(2)若有 x = p * x1 ,且p是一個素數(shù)，且y % p != 0
則有f(x , y) = f(x1 , y)
我們主要考慮2這個素數(shù)，分析如下：
若x和y均是偶數(shù)則 f(x , y) =2 * f(x>>1 , y>>1)
若x為偶數(shù)，y為奇數(shù)，則f(x,y) = f(x>>1 , y)
若x為奇數(shù)，y為偶數(shù)，則f(x,y) = f(x , y>>1)
若x為奇數(shù)，y為奇數(shù)，則f(x,y) = f(x-y , y) ,則必有x-y為偶數(shù)。
int gcd3(int x , int y)
{
if(x < y)
return gcd3(y , x) ;
if(y == 0)
return x ;
if(isEven(x)) //x為奇數(shù)
{
if(isEven(y)) //y為奇數(shù)
return gcd3(x - y , y) ;
else //y為偶數(shù)
return gcd3(x , y >>1) ;
}
else //x為偶數(shù)
{
if(isEven(y)) //y為奇數(shù)
return gcd3(x >> 1 , y) ;
else //y為偶數(shù)
return 2 * gcd3(x >> 1, y >> 1) ;
}
}