閱讀795 返回首頁    go 微軟 go windows

編程之美之2.7 最大公約數問題

問題：

求兩個數的最大公約數

解法一：

歐幾裏得輾轉相除法：

f(x,y) = GCD(x,y), 取k = x / y, b = x % y,則：x = k*y + b;
如果一個數能整除x,y,則它也能整除b,y； 而且能整除b,y的數必能整除x,y，即x,y和b,y的公約數是相同的，其最大公約數也是相同的，即f(x,y) = f(y ,x % y) (x>=y>0)


例如，計算a = 1071和b = 462的最大公約數的過程如下：從1071中不斷減去462直到小於462（可以減2次，即商q0 = 2），餘數是147：
1071 = 2 × 462 + 147.
然後從462中不斷減去147直到小於147（可以減3次，即q1 = 3），餘數是21：
462 = 3 × 147 + 21.
再從147中不斷減去21直到小於21（可以減7次，即q2 = 7），沒有餘數：
147 = 7 × 21 + 0.
此時，餘數是0，所以1071和462的最大公約數是21

遞歸算法：

  1. #include<stdio.h>   
  2.   
  3. //遞歸形式   
  4. int GCD(int a,int b)  
  5. {   
  6.     if(b == 0){  
  7.         return a;  
  8.     }  
  9.     else{  
  10.         //a,b和b,a%b有相同的最大公約數  
  11.         return GCD(b,a%b);  
  12.     }  
  13.   
  14. }   
  15.   
  16. int main(){  
  17.     int a,b;  
  18.     scanf("%d %d",&a,&b);  
  19.     printf("%d\n",GCD(a,b));  
  20. }  

例如GCD(1071, 462)的計算過程是：

函數的第一次調用計算GCD(462, 1071 mod 462) = GCD(462, 147)；

下一次調用計算           GCD(147, 462 mod 147) = GCD(147, 21)，

在接下來是                   GCD(21, 147 mod 21) = GCD(21, 0) = 21。

非遞歸算法：

  1. #include<stdio.h>   
  2.   
  3. //非遞歸形式   
  4. int GCD(int a,int b)  
  5. {   
  6.     int temp = a;  
  7.     while(b){  
  8.         a = b;  
  9.         b = temp % b;  
  10.     }  
  11.     return a;  
  12. }   
  13.   
  14. int main(){  
  15.     int a,b;  
  16.     scanf("%d %d",&a,&b);  
  17.     printf("%d\n",GCD(a,b));  
  18. }  

解法二：

在解法一中我們用到了取模運算。在大整數中取模運算（涉及到除法運算）是非常高貴的開銷。

我們想想避免用取模運算。

類似前麵的分析，一個數能整除x,y則必能同時整除x - y，y。能同時整除x - y,y 則必能同時整除x，y。即x,y的公約數和x-y,y的公約數是一樣的，其最大公約數也是一樣的。

  1. #include<stdio.h>   
  2.   
  3. int GCD(int a,int b)  
  4. {   
  5.     //如果a < b  
  6.     if(a < b){  
  7.         return GCD(b,a);  
  8.     }  
  9.     if(b == 0){  
  10.         return a;  
  11.     }  
  12.     else{  
  13.         return GCD(a - b,b);  
  14.     }  
  15. }   
  16.   
  17. int main(){  
  18.     int a,b;  
  19.     scanf("%d %d",&a,&b);  
  20.     printf("%d\n",GCD(a,b));  
  21. }  
此解法用減法而不是除法，這樣迭代的次數比除法要多，當遇到f(10000000,1)的情況時這不是一個好方法。


解法三：

分析：

對於x,y,如果y = k * y1,x = k * x1,則f(y,x) = K*f(x1,y1)；

如果x = p * x1, 假設p是素數，且 y % p != 0 ,即y不能被p整除，則f(x,y) = f(x1,y).

可以利用上麵兩點進行改進。因為2是素數，同時對於二進製表示的大整數而言可以很容易的將除以2和乘以2的算法轉換為移位運算，從而避免大整數除法。

可以充分利用2進行分析：
若x,y都為偶數（2肯定是公約數），則f(x,y) = 2*f(x / 2,y / 2) = 2*f(x>>1,y>>1);
若x為偶數，y為奇數(2肯定不是公約數),則f(x,y) = f(x / 2, y / 2) = f(x>>1, y)
若x為奇數，y為偶數2肯定不是公約數)，則f(x,y)= f(x, y / 2) = f(x, y>>1)
若x,y都為奇數（2肯定不是公約數），則f(x,y) = f(y, x-y)    (x-y肯定為偶數) = f（y, (x-y)/2）

  1. #include<stdio.h>   
  2. //判斷奇偶性  
  3. int IsEvenOdd(int n){  
  4.     if(n % 2 == 0){  
  5.         return 1;  
  6.     }  
  7.     else{  
  8.         return 0;  
  9.     }  
  10. }  
  11.   
  12. int GCD(int a,int b)  
  13. {   
  14.     //如果a < b  
  15.     if(a < b){  
  16.         return GCD(b,a);  
  17.     }  
  18.     if(b == 0){  
  19.         return a;  
  20.     }  
  21.     //若x,y都為偶數  
  22.     if(IsEvenOdd(a) == 1 && IsEvenOdd(b) == 1){  
  23.         return 2 * GCD(a>>1,b>>1);  
  24.     }  
  25.     //若x,y都為奇數  
  26.     else if(IsEvenOdd(a) == 0 && IsEvenOdd(b) == 0){  
  27.         return GCD(b,a-b);  
  28.     }  
  29.     //若x是偶數y是奇數  
  30.     else if(IsEvenOdd(a) == 1 && IsEvenOdd(b) == 0){  
  31.         return GCD(a>>1,b);  
  32.     }  
  33.     //若x是奇數y是偶數  
  34.     else{  
  35.         return GCD(a,b>>1);  
  36.     }  
  37. }   
  38.   
  39. int main(){  
  40.     int a,b;  
  41.     scanf("%d %d",&a,&b);  
  42.     printf("%d\n",GCD(a,b));  
  43. }  

這個算法的好處就是用移位操作來代替除法操作，大大節約時間。



最後更新：2017-04-03 08:26:12

  上一篇：go ObjectArx學習筆記-畫線並修改顏色
  下一篇：go ObjectArx學習筆記-畫線並修改顏色改進寫法