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