輾轉相除法(歐幾里得算法)

輾轉相除法

歐幾里得算法一般指本詞條

輾轉相除法, 又名歐幾里德算法(Euclidean algorithm),是求最大公約數的一種方法。它的具體做法是:用較大數除以較小數,再用出現的餘數(第一餘數)去除除數,再用出現的餘數(第二餘數)去除第一餘數,如此反覆,直到最後餘數是0為止。如果是求兩個數的最大公約數,那么最後的除數就是這兩個數的最大公約數。

另一種求兩數的最大公約數的方法是更相減損法

基本介紹

  • 中文名:輾轉相除法
  • 外文名:Euclidean algorithm
  • 別稱:歐幾里德算法
  • 用途:求最大公約數
  • 歸屬學科:數學
  • 出現書目:《幾何原本
基本原理,證明,算法描述,示例,例1,例2,代碼實現,c語言,C++語言實現,C#語言實現,Basic實現,Pascal實現,Java 實現,Python實現,

基本原理

兩個數的最大公約數是指能同時整除它們的最大正整數。
設兩數為a、b(a≥b),求a和b最大公約數
的步驟如下:
(1)用a除以b(a≥b),得
(2)若
,則
(3)若
,則再用b除以
,得
.
(4)若
,則
;若
,則繼續用
除以
,......,如此下去,直到能整除為止。
其最後一個餘數為0的除數即為
的最大公約數。

證明

設兩數為a、b(a>b),用
表示a,b的最大公約數,r=a (mod b) 為a除以b的餘數,k為a除以b的商,即
。輾轉相除法即是要證明
第一步:令
,則設
第二步:根據前提可知
第三步:根據第二步結果可知,
也是
的因數
第四步:可以斷定
互質(這裡用反證法進行證明:設
,則
,則
,則a與b的一個公約數
,故c非a與b的最大公約數,與前面結論矛盾,因此c也是b與r的最大公約數)從而可知
,繼而
證畢
註:以上步驟的操作是建立在剛開始時
的基礎之上的,即m與n亦互質。

算法描述

用輾轉相除法確定兩個正整數 a 和 b(a≥b) 的最大公因數
時,
;否則
遞歸或循環運算得出結果。
算法流程圖如下:
輾轉相除法
偽代碼描述如下:
function gcd(a,b) {if b< >0        return gcd(b,a mod b);else        return a;}

示例

例1

123456 和 7890 的最大公因數是 6,這可由下列步驟(其中,“a mod b”是指取 a ÷ b 的餘數)看出:
a
b
a mod b
123456
7890
5106
7890
5106
2784
5106
2784
2322
2784
2322
462
2322
462
12
462
12
6
12
6
0

例2

已知不定方程為
,利用輾轉相除法求出一組整數解
解:求
的算式為:
所以
所以
所以
是不定方程
的一組解。

代碼實現

c語言

int GCD(int a,int b){    return b==0?a:GCD(b,a%b);}

C++語言實現

#include<iostream>using namespace std;int a , b , a1 , b2 , l;int gcd(int x , int y){    if(!y)       return x;else         return gcd(y , x%y); }int main(){cout << "請輸入兩個正整數,計算它們的最大公約數" << endl ;int a , b , ans;cin >> a >> b;if(a > b)ans = gcd(a , b);else     ans = gcd(b , a);cout << ans;return 0;}

C#語言實現

static int sucDivison(int m, int n) /*除法*/{ int remainder = 0; if (m % n == 0)     { return n; } else     {         do         {             remainder = m % n;             m = n;             n = remainder;         } while (remainder > 0); } if (n == 0) { return m; } return n; }

Basic實現

INPUT m,n DO r=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND

Pascal實現

function gcd(a,b:integer):integer;begin    if b=0 then         gcd:=a    else         gcd:=gcd(b,a mod b);end;

Java 實現

public static int gcd(int m, int n) {    while (true)     {    if ((m = m % n) == 0)        return n;        if ((n = n % m) == 0)            return m;}}

Python實現

#遞歸解決最大公約數問題def gcd(x , y):       if y == 0         return x     else gcd(y, x%y)   x = int(input('請輸入第一個數字:'))y = int(input('請輸入第二個數字:'))print('%d 和 %d 的最大公約數為:' %(x,y),gcd(x,y))#非遞歸def gcd(x, y):    while y:            x, y = y, x%y    return x

相關詞條

熱門詞條

聯絡我們