求解最大公約數(shù)和最小公倍數(shù)問題

思路：

最大公約數(shù)問題也是1個非常典型的遞歸算法的利用。每次遞歸使得原來求兩個大數(shù)之間的公約數(shù)轉(zhuǎn)變成求兩個略微小點的數(shù)之間的公約數(shù)，要求轉(zhuǎn)換的進(jìn)程要保證不會改變公約數(shù)的值。這就要看其中轉(zhuǎn)換的原理了。

原理從《幾何本來》中得出--展轉(zhuǎn)相除。假定f(x, y) 表示x,y的最大公約數(shù)是g，而k = x/y,b= x%y，則g必能整出b。由于x = ky + b，b = x - ky，b/g = (x-ky)/g1定為整數(shù)，所以必有g(shù)整除b。

以下所示：

f(42, 30) = f(30, 12) = f(12, 6)= f(6, 0) = 6

代碼以下：

非遞歸代碼：

書中還引申出展轉(zhuǎn)相減法，原理跟上面所述差不多。

代碼以下：

非遞歸代碼：

最后書中提到1種相除和相減相結(jié)合的方法，保證了不做過量冗余的步驟。這就是把2當(dāng)作每次轉(zhuǎn)換的數(shù)量級。

若x，y均為偶數(shù)，f(x,y) = 2*f(x/2,y/2) = 2*f(x>>1,y>>1)

若x為偶數(shù)，y為奇數(shù)，f(x,y) = f(x/2,y) = f(x>>1,y)

若x為奇數(shù)，y為偶數(shù)，f(x,y) = f(x,y/2) = f(x,y>>1)

若x，y均為奇數(shù)，f(x,y) =f(y,x-y)

此解法結(jié)合了上述兩種方法：第1種方法遞歸次數(shù)相當(dāng)少但每次取模挺耗時（到底耗時情況如何，我沒有具體了解過，但肯定比加減法耗時些），而第2種遞歸可能會相當(dāng)多，但每次運(yùn)算都是減法運(yùn)算， 很快。綜合二者，用2為基數(shù)，可以保證遞歸次數(shù)不那末多，同時運(yùn)算也快。

代碼以下：

1. int gcd(int x , int y)  
2. {  
3.   if(x < y)  
4.      return gcd(y , x) ;  
5.   if(y == 0)  
6.      return x ;  
7.    if(isEven(x)) //x為奇  
8.    {  
9.      if(isEven(y)) //y為奇             
10.         return gcd(x - y, y) ;           
11.      else         //y為偶  
12.         return gcd(x , y >>1) ;              
13.    }      
14.    else         //x為偶  
15.    {  
16.       if(isEven(y)) //y為奇數(shù)              
17.         return gcd(x >> 1, y) ;           
18.      else         //y為偶  
19.         return 2 * gcd(x >> 1, y >> 1) ;        
20.            
21.    }  
22.       
23. }  

求解最小公倍數(shù)：

從題面上看，好像我們需要求解的是兩個題目，但其實就是1個題目。那就是求最大公約數(shù)？為何呢？我們可以假想這兩個數(shù)m和n，假定m和n的最大公約數(shù)是a。那末我們可以這樣寫：

    m = b *a；

    n = c * a;

    所以m和n的最小公倍數(shù)就應(yīng)當(dāng)是a*b*c啊，那不就是m * n / a，其中m和n是已知的，而a就是那個需要求解的最大公約數(shù)。所以就有了下面的代碼，

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈