求解最大公約數和最小公倍數問題

思路：

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

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

以下所示：

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

代碼以下：

非遞歸代碼：

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

代碼以下：

非遞歸代碼：

最后書中提到1種相除和相減相結合的方法，保證了不做過量冗余的步驟。這就是把2當作每次轉換的數量級。

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

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

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

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

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

代碼以下：

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為奇數              
17.         return gcd(x >> 1, y) ;           
18.      else         //y為偶  
19.         return 2 * gcd(x >> 1, y >> 1) ;        
20.            
21.    }  
22.       
23. }  

求解最小公倍數：

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

    m = b *a；

    n = c * a;

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

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈