複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/更相減損術/449183
複製
複製成功

更相減損術

鎖定
更相減損術是出自《九章算術》的一種求最大公約數的算法，它原本是為約分而設計的，但它適用於任何需要求最大公約數的場合。
中文名
更相減損術
別    名
中華更相減損術
類    型
數學算術
出    處
《九章算術》
用    途
求最大公約數
原用途
分數的約分
作    用
適用任何需要求最大公約數的場合

目錄

  1. 1 思想
  2. 2 使用步驟
  3. 3 實例
  4. 4 證明
  1. 5 比較
  2. 6 Stein算法
  3. 7 “可半者半之”
  4. 8 電腦
  1. ▪ Basic
  2. ▪ python
  3. ▪ C語言
  4. ▪ C++
  5. ▪ Java

更相減損術思想

《九章算術》是中國古代的數學專著，其中的“更相減損術”可以用來求兩個數的最大公約數，原文是：
可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。
白話文譯文：
（如果需要對分數進行約分，那麼）可以折半的話，就折半（也就是用2來約分）。如果不可以折半的話，那麼就比較分母和分子的大小，用大數減去小數，互相減來減去，一直到減數與差相等為止，用這個相等的數字來約分。

更相減損術使用步驟

第一步：任意給定兩個正整數；判斷它們是否都是偶數。若是，則用2約簡；若不是則執行第二步。
第二步：以較大的數減較小的數，接着把所得的差與較小的數比較，並以大數減小數。繼續這個操作，直到所得的減數和差相等為止。
則第一步中約掉的若干個2的積與第二步中等數的乘積就是所求的最大公約數。
其中所説的“等數”，就是公約數。求“等數”的辦法是“更相減損”法。

更相減損術實例

例1、用更相減損術求98與63的最大公約數。
解：由於63不是偶數，把98和63以大數減小數，並輾轉相減：
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以，98和63的最大公約數等於7。
例2、用更相減損術求260和104的最大公約數。
解：由於260和104均為偶數，首先用2約簡得到130和52，再用2約簡得到65和26。
此時65是奇數而26不是奇數，故把65和26輾轉相減：
65-26=39
39-26=13
26-13=13
所以，260與104的最大公約數等於13乘以第一步中約掉的兩個2，即13*2*2=52。

更相減損術證明

設gcd(x,y)=d，則滿足x=k1*d，y=k2*d，易得k1與k2互質。
情況1：x=y。顯然，gcd(x,y)=x=gcd(x,0)=gcd(x,y-x)。
情況2：不妨令x
用反證法。
假設k1,(k2 - k1)不互質，
令gcd(k1.k2-k1) = m(m為正整數且m＞1);
k1 = m*a,k2 - k1 = m*b
k2 = (a+b)m
即k1,k2有公約數m，與k1,k2互質矛盾
所以假設不成立
即k1,(k2 - k1)互質
所以gcd（x,x-y）= d = gcd(x,y)
綜上，gcd(x,y)=gcd(x,y-x)。
命題得證
當然，此結論可用數學歸納法推廣到一般，該性質對多個整數都成立。
即：gcd(x,y,z,...)=gcd(x,y-x,z-y,...)。
直觀證明：
對於gcd(x,y,z)=gcd(x,y-x,z-y)：
gcd(x,y,z)=gcd(x,gcd(y,z))=gcd(x,gcd(y,z-y))=gcd(x,y,z-y)=gcd(gcd(x,y),z-y)=gcd(gcd(x,y-x),z-y)=gcd(x,y-x,z-y)。
更多項依次類推。

更相減損術比較

輾轉相除法也可以用來求兩個數的最大公約數。
更相減損術和輾轉相除法的主要區別在於前者所使用的運算是“減”，後者是“除”。從算法思想上看，兩者並沒有本質上的區別，但是在計算過程中，如果遇到一個數很大，另一個數比較小的情況，可能要進行很多次減法才能達到一次除法的效果，從而使得算法的時間複雜度退化為O(N)，其中N是原先的兩個數中較大的一個。相比之下，輾轉相除法的時間複雜度穩定於O(logN)。

更相減損術Stein算法

更相減損法有點類似於求最大公約數的Stein算法。在更相減損法中，若兩個是偶數則同除以2，結果乘以2。如果增加一個判斷，若為一奇一偶則偶數除以2，結果不變，若為兩個奇數才相減，這樣就變成了計算大整數最大公約數的非常好的一個算法，Stein算法。
在上面的實例中，下面是更相減損法與Stein算法的比較，從中可以發現兩種算法的相似性。
Stein 算法與更相減損術的操作流程
更相減損法：操作
甲數
乙數
Stein算法：操作
甲數
乙數
-
98
63
-
98
63
98-63=35
63
35
98是偶數，除以2
49
63
63-35=28
35
28
都是奇數，63-49=14
49
14
35-28=7
28
7
14是偶數，除以2
49
7
28-7=21
7
21
49-7=42
42
7
21-7=14
7
14
42是偶數，除以2
21
7
14-7=7
7
7
21-7=14
14
7
7-7=0
7
0
14是偶數，除以2
7
7
-
-
-
7-7=0
7
0

更相減損術“可半者半之”

通常認為，算法描述中的第一步“可半者半之”是指分子分母皆為偶數的時候，首先用2約簡。因為更相減損術原先是專用來約分，所以並不用考慮最後計算結果時，要把第一步中約掉的若干個2再乘回去。加入這一步的原因可能是，分母、分子皆為偶數是在分數加減運算的結果中比較容易遇到的一種情況，用這種方法有可能減少數字的位數，簡化計算。
當然，省略這個以2約簡的步驟，也能得到正確的答案。

更相減損術電腦

更相減損術Basic

INPUT "m,n=";m,n
i=0
WHILE m MOD 2=0 AND n MOD 2=0
m=m/2
n=n/2
i=i+1
WEND
DO
IF m
r=m
m=n
n=r
END IF
m=m-n
LOOP UNTIL m=0
PRINT “m、n的最大公約數為”;n*2ˆi
END
（i=i+1部分可以省略，因為，不進行約簡，一樣可以求出）

更相減損術python

# 更相減損法,求最大公約數
def gcf(a, b):
    # 減少倍數
    reduction = 1
    while True:
        # 可半者半之
        if a % 2 == 0 and b % 2 == 0:
            a //= 2
            b //= 2
            reduction *= 2
        else:
            # 不可半者
            break
    
    while True:
        # 副置分母、子之數，以少減多，更相減損，求其等也
        big = max(a, b)
        small = min(a, b)
        if small * 2 == big:
            return small * reduction
        else:
            a, b = small, big - small

更相減損術C語言

#include <stdio.h>
int main()
{　
    int a,b;
　scanf("%d%d",&a,&b);
　while(a != b)
　{　if(a > b)a -= b;
         else　b -= a;　
    }
    printf("m、n的最大公約數為%d",a);
    return 0;
}

更相減損術C++

//非遞歸形式：
#include <iostream>
using namespace std;
int main()
{　
    int a,b;　
    cin>>a>>b;　
    while(a != b)　
    {　
        if(a > b)　
            a -= b;　
        else　
            b -= a;　
     }　
     cout<<a<<endl;　
     return 0;　
}



//遞歸形式：
#include <iostream>
using namespace std;
//下面這個gcd函數在正int型內完全通用，返回a,b的最大公因數。
//但是當a,b之間差距較大時（如100000倍）會導致錯誤（棧過深）
int gcd(int a,int b){
    if(a==b)return a;
    else if(a>b)a-=b;
    else b-=a;
    return gcd(a,b);
}
int main(){
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b)<<endl;
    return 0;
}

更相減損術Java

/**
 * 更相減損術
 *
 * @param max 大值
 * @param min 小值
 * @return 最大公約數
 */
public static int getGreatestCommonDivisor(int max, int min) {
  if (max == min) {
    return max;
  }
  if (max < min) {
    max = max ^ min;
    min = max ^ min;
    max = max ^ min;
  }
  return getGreatestCommonDivisorByDivideBySubtract(max - min, min);
}
/**
 * Stein算法
 *
 * @param max 大值
 * @param min 小值
 * @return 最大公約數
 */
public static int getGreatestCommonDivisor(int max, int min) {
  if (max == min) {
    return max;
  }
  if ((max & 1) == 0 && (min & 1) == 0) {
    return getGreatestCommonDivisor(max >> 1, min >> 1);
  } else if ((max & 1) == 0 && (min & 1) != 0) {
    return getGreatestCommonDivisor(max >> 1, min);
  } else if ((max & 1) != 0 && (min & 1) == 0) {
    return getGreatestCommonDivisor(max, min >> 1);
  } else {
    if (max < min) {
      max = max ^ min;
      min = max ^ min;
      max = max ^ min;
    }
    return getGreatestCommonDivisor(max - min, min);
  }
}