更相減損術

更相減損術是出自《九章算術》的一種求最大公約數的算法,它原本是為約分而設計的,但它適用於任何需要求最大公約數的場合。

基本介紹

  • 中文名:更相減損術
  • 類型:數學算術
  • 出處:《九章算術》
  • 用途:求最大公約數
  • 原用途:分數的約分
  • 作用:適用任何需要求最大公約數的場合
思想,使用步驟,實例,證明,比較,Stein算法,“可半者半之”,電腦,Basic,C語言,C++,

思想

九章算術》是中國古代的數學專著,其中的“更相減損術”可以用來求兩個數的最大公約數,原文是:
可半者半之,不可半者,副置分母、子之數,以少減多,更相減損,求其等也。以等數約之。
白話文譯文:
(如果需要對分數進行約分,那么)可以折半的話,就折半(也就是用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<y,所以有k1<k2,所以y'=y-x=(k2-k1)*d。所以應證k1⊥(k2-k1)。
用反證法。
令k3=k2-k1。
假設k1,k3存在公約數m(m>1),即k2=p2*m,k3=k2-k1=p3*m=(p2-p1)*m。
所以:k1=p1*m,k2=p2*m=(p3+p1)*m且p1⊥(p3+p1)。
要使k1⊥k2,所以m=1,與假設矛盾,所以k1⊥(k2-k1)。
所以原命題得證。
綜上,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算法:操作
甲數
乙數
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<n THEN
r=m
m=n
n=r
END IF
m=m-n
LOOP UNTIL m=0
PRINT “m、n的最大公約數為”;n*2ˆi
END
(黑體部分可以省略,因為,不進行約簡,一樣可以求出)

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;      }

相關詞條

熱門詞條

聯絡我們