The greatest common divisor gcd（最大公約數）

文章某些部分有借鑒大神處，共勉之。

說到最大公約數的算法，最熟悉的還是輾轉相除法，又名歐幾裡德算法（Euclidean algorithm）。在求最大公數的時候，輾轉相除法是利用以下性質來确定兩個正整數 a 和 b 的最大公因子的：

1. 若 r 是 a ÷ b 的餘數， 則gcd(a,b) = gcd(b,r)

2. a 和其倍數之最大公因子為 a。

另一種寫法是：

1. a ÷ b，令r為所得餘數（0≤r＜b），若 r = 0，算法結束；b 即為答案。

2. 互換：置 a←b，b←r，并傳回第一步。

第一種寫法是利用遞歸實作，第二種可以更清楚的看出其輾轉過程。實作代碼如下：

int gcd(int m,int n)   //遞歸 
{
    if(n==0)   
      return  m;
    else 
      return  gcd(n,m%n);
}
//調用：  n=gcd(a,b);
           

int gcd(int m,int n)   //遞歸 
{
    if(n==0)   
      return  m;
    else 
      return  gcd(n,m%n);
}
//調用：  n=gcd(a,b);
           

今天第一次了解另一種求最大公約數算法——更相減損法（等值算法），其實個人認為也可了解為輾轉相減法。。。

此處借用百科解釋一下其原理：《九章算術》是中國古代的數學專著，其中的“更相減損術”可以用來求兩個數的最大公約數，即“可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。”

翻譯成現代語言如下： 

第一步：任意給定兩個正整數，判斷它們是否都是偶數。若是，用2約簡；若不是執行第二步；

第二步：以較大的數減較小的數，接着把所得的差與較小的數比較，并以大數減小數。循環執行這個操作，直到所得的減數和差相等為止。

則第一步中約掉的若幹個2與第二步中等數的乘積就是所求的最大公約數。

其中所說的“等數”，就是最大公約數。求“等數”的辦法是“更相減損”法。

代碼如下：

int gcd(int m,int n)   //更相減損法 
{
    while(m!=n)     //輾轉相減
    {
      if(m>n)
        m-=n;
       else
         n-=m; 
    } 
    return m;
} 
           

實作代碼如下，由于本人屬于小水一名，簡單的東西容易忘記，代碼中附加了幾種變量交換方式 ，共勉之。

#include <stdio.h>
#include <iostream>
using namespace std;

int gcd(int m,int n)   //遞歸 
{
    if(n==0)   
      return  m;
    else 
      return  gcd(n,m%n);
}

/*
int gcd(int m,int n)   //輾轉相除法 
{
    int p;
    while(n)
    {
      p=m%n;
      m=n;
      n=p;
    }
    return m;
}

int gcd(int m,int n)   //更相減損法 
{
    while(m!=n)
    {
      if(m>n)
        m-=n;
       else
         n-=m; 
    } 
    return m;
} 
 */

void swap(int &m,int &n)   //引用 ，交換變量 (無傳回值)
{
     int temp;
     temp=m;
     m=n;
     n=temp;     
 } 

/*void swap(int *m,int *n)  //指針，交換變量 
{
     int temp;
     temp=*m;
     *m=*n;
     *n=temp;
 } 
 調用：swap(&m,&n); 
 
 int swap(int &m,int &n)    //不用輔助變量，交換 (此兩種方法指針通用)
 {
     m=m+n;
     n=m-n;
     m=m-n; 
 } 
 調用：swap(m,n);
  
 int swap(int &m,int &n)
 {
     m=m^n;
     n=n^m;
     m=m^n;
 } 
 調用：swap(m,n);
 */
 
int main()
{
     int a,b;
     
     while(1)
     { 
     printf("please enter the two positive integers: ");
     scanf("%d%d",&a,&b);
     if(a<b)
       swap(a,b); 
     printf("the greatest common divisor gcd: %d\n\n",gcd(a,b));
     }
     
     system("pause");
     return 0; 
}