問題： 求兩個數的最大公約數 解法一： 歐幾裡得輾轉相除法： f(x,y) = GCD(x,y), 取k = x / y, b = x % y,則：x = k*y + b; www.2cto.com 如果一個數能整除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 遞歸算法： [cpp] #include<stdio.h> //遞歸形式 int GCD(int a,int b) { if(b == 0){ return a; } else{ //a,b和b,a%b有相同的最大公約數 return GCD(b,a%b); } } int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d\n",GCD(a,b)); } #include<stdio.h> //遞歸形式 int GCD(int a,int b) { if(b == 0){ return a; } else{ //a,b和b,a%b有相同的最大公約數 return GCD(b,a%b); } } int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d\n",GCD(a,b)); } 例如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。 非遞歸算法： [cpp] #include<stdio.h> //非遞歸形式 int GCD(int a,int b) { int temp = a; while(b){ a = b; b = temp % b; } return a; } int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d\n",GCD(a,b)); } #include<stdio.h> //非遞歸形式 int GCD(int a,int b) { int temp = a; while(b){ a = b; b = temp % b; } return a; } int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d\n",GCD(a,b)); } 解法二： 在解法一中我們用到了取模運算。在大整數中取模運算（涉及到除法運算）是非常高貴的開銷。 我們想想避免用取模運算。 類似前面的分析，一個數能整除x,y則必能同時整除x - y，y。能同時整除x - y,y 則必能同時整除x，y。即x,y的公約數和x-y,y的公約數是一樣的，其最大公約數也是一樣的。 [cpp] #include<stdio.h> int GCD(int a,int b) { //如果a < b if(a < b){ return GCD(b,a); } if(b == 0){ return a; } else{ return GCD(a - b,b); } } int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d\n",GCD(a,b)); } #include<stdio.h> int GCD(int a,int b) { //如果a < b if(a < b){ return GCD(b,a); } if(b == 0){ return a; } else{ return GCD(a - b,b); } } int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d\n",GCD(a,b)); }此解法用減法而不是除法，這樣迭代的次數比除法要多，當遇到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） [cpp] #include<stdio.h> //判斷奇偶性 int IsEvenOdd(int n){ if(n % 2 == 0){ return 1; } else{ return 0; } } int GCD(int a,int b) { //如果a < b if(a < b){ return GCD(b,a); } if(b == 0){ return a; } //若x,y都為偶數 if(IsEvenOdd(a) == 1 && IsEvenOdd(b) == 1){ return 2 * GCD(a>>1,b>>1); } //若x,y都為奇數 else if(IsEvenOdd(a) == 0 && IsEvenOdd(b) == 0){ return GCD(b,a-b); } //若x是偶數y是奇數 else if(IsEvenOdd(a) == 1 && IsEvenOdd(b) == 0){ return GCD(a>>1,b); } //若x是奇數y是偶數 else{ return GCD(a,b>>1); } } int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d\n",GCD(a,b)); } #include<stdio.h> //判斷奇偶性 int IsEvenOdd(int n){ if(n % 2 == 0){ return 1; } else{ return 0; } } int GCD(int a,int b) { //如果a < b if(a < b){ return GCD(b,a); } if(b == 0){ return a; } //若x,y都為偶數 if(IsEvenOdd(a) == 1 && IsEvenOdd(b) == 1){ return 2 * GCD(a>>1,b>>1); } //若x,y都為奇數 else if(IsEvenOdd(a) == 0 && IsEvenOdd(b) == 0){ return GCD(b,a-b); } //若x是偶數y是奇數 else if(IsEvenOdd(a) == 1 && IsEvenOdd(b) == 0){ return GCD(a>>1,b); } //若x是奇數y是偶數 else{ return GCD(a,b>>1); } } int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d\n",GCD(a,b)); } 這個算法的好處就是用移位操作來代替除法操作，大大節約時間。
