首页 > 代码库 > 2.7 编程之美--最大公约数的3种解法[efficient method to solve gcd problem]

2.7 编程之美--最大公约数的3种解法[efficient method to solve gcd problem]

【本文链接】

http://www.cnblogs.com/hellogiser/p/efficient-method-to-solve-gcd-problem.html

【题目】

  求两个正整数的最大公约数Greatest Common Divisor (GCD)。如果两个正整数都很大,有什么简单的算法吗?例如,给定两个数1 100 100 210 001, 120 200 021,求出其最大公约数。

【解法】


 【1. 辗转相除法】

辗转相除法:f(x,y) = f(y , x % y)(x>y)

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

【代码】

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
/*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/7/8
*/


int gcd(int x, int y)
{
    
if(x < y)
        
return gcd(y, x);
    
if(y == 0)
        
return x;
    
else
        
return gcd(y, x % y);
}

此方法中用到了取模运算,对于大整数而言,取模运算(其中用到了除法)开销是非常昂贵的,将成为整个算法的瓶颈。


【2. 辗转相减法】

辗转相减法:f(x,y) = f(y, x-y) (x>y)

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

【代码】

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
/*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/7/8
*/


int gcd(int x, int y)
{
    
if(x < y)
        
return gcd(y, x);
    
if(y == 0)
        
return x;
    
else
        
return gcd(y, x - y);
}

这个算法免去了大整数除法的繁琐,但同样也有不足之处。最大的瓶颈是迭代的次数过多,如果出现(1 000 000 000,1)这类情况,那就相当让人郁闷了。


【3. 奇偶法】

奇偶法:

此种方法是将解法1)和解法2)结合起来,降低计算复杂度的同时也降低迭代次数。

1:若 x, y均为偶数,f (x,y) = 2 * f(x / 2, y / 2) = 2 * f(x >> 1, y >> 1)

2:若x为偶,而y为奇,f (x , y )  = f (x / 2, y) = f ( x >> 1, y)

3:若x为奇,y为偶,f ( x, y)  = f (x , y / 2) = f(x , y >> 1)

4:若x,y均为奇,f ( x, y ) = f (y , x - y)

在f(x, y) = f(y, x - y)之后,(x - y)是一个偶数,下一步一定会有除以2的操作。

因此最坏情况下时间复杂度为O(log2 (max(x,y)))。

f (42 , 30 ) = 2 * f (21,15)      

                   = 2 * f (15,6)    

                   = 2 * f (15,3)      

                   = 2 * f (3,12)  =2 * f (12,3)  

                   = 2 * f (6,3)         

                   = 2 * f (3,3)       

                   = 2 * f (3,0)         

                   = 2 * 3

                   = 6

代码】

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
/*
    version: 1.0
    author: hellogiser
    blog: http://www.cnblogs.com/hellogiser
    date: 2014/7/8
*/


bool IsEven(int x)
{
    
return (x & 0x1) == 0;
}

int gcd(int x, int y)
{
    
if(x < y)
        
return gcd(y, x);
    
if(y == 0)
        
return x;
    
else
    {
        
if(IsEven(x))
        {
            
if(IsEven(y)) //case 1,x,y均为偶数
                return 2 * gcd(x >> 1, y >> 1);
            
else  //case 2,x为偶,y为奇
                return gcd(x >> 1, y);
        }
        
else
        {
            
if(IsEven(y)) //case 3,x为奇,y为偶
                return gcd(x, y >> 1);
            
else  //case 4,x,y均为奇
                return gcd(y, x - y);
        }
    }
}

【参考】

http://blog.csdn.net/ajioy/article/details/7478008

http://blog.csdn.net/rein07/article/details/6739688

【本文链接】

http://www.cnblogs.com/hellogiser/p/efficient-method-to-solve-gcd-problem.html