求解最大公约数和最小公倍数问题

思路：

最大公约数问题也是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

代码以下：

非递归代码：

书中还引申出展转相减法，原理跟上面所述差不多。

[html] view plaincopy

   if(x < y)  
1.     return  gcd(y , x) ;    
2.    else if(y == 0)  
3.     return x ;  
4.    else  
5.     return gcd(x - y , y) ;          
6.       
7. }   

最后书中提到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,51); font-family:Arial; font-size:14px; line-height:26px"> 若x，y均为奇数，f(x,y) =f(y,x-y)

此解法结合了上述两种方法：第1种方法递归次数相当少但每次取模挺耗时（到底耗时情况如何，我没有具体了解过，但肯定比加减法耗时些），而第2种递归可能会相当多，但每次运算都是减法运算， 很快。综合二者，用2为基数，可以保证递归次数不那末多，同时运算也快。

代码以下：

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

求解最小公倍数：

从题面上看，好像我们需要求解的是两个题目，但其实就是1个题目。那就是求最大公约数？为何呢？我们可以假想这两个数m和n，假定m和n的最大公约数是a。那末我们可以这样写：

    m = b *a；

    n = c * a;

    所以m和n的最小公倍数就应当是a*b*c啊，那不就是m * n / a，其中m和n是已知的，而a就是那个需要求解的最大公约数。所以就有了下面的代码，

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!