輾轉相除的原理是，C語言輾轉相除法

1樓：企鵝呆

輾轉相除法的證明

設兩數為a、b(b＜a)，求它們最大公約數的步驟如下：用b除a，得a＝bq＋r（0≤r＜b）（q是這個除法的商）。若r=0,則b是a和b的最大公約數。若r≠0,則繼續考慮。

首先，應該明白的一點是任何 a 和 b 的公約數都是 r 的公約數。要想證明這一點，就要考慮把 r 寫成 r=a-bq。現在，如果 a 和 b 有一個公約數 d，而且設 a=sd , b=td, 那麼 r = sd-tdq = (s-tq)d。

因為這個式子中，所有的數（包括 s-tq )都為整數，所以 r 可以被 d 整除。

對於所有的 d 的值，這都是正確的；所以 a 和 b 的最大公約數也是 b 和 r 的最大公約數。因此我們可以繼續對 b 和 r 進行上述取餘的運算。這個過程在有限的重複後，可以最終得到 r=0 的結果，我們也就得到了 a 和 b 的最大公約數。

或

2樓：第六天の魔王

~~~上課沒有認真聽吧~~~~

3樓：耿齊勵新

假若整數a>=b

a=xb+c,其中c是餘數,c為0時,a是b整數倍,如果有因式q可以被a和b整除,

那麼q一定能被c整除,

也就是b,c和a,b有一樣的最大公約數,

所以可以輾轉相除

c語言輾轉相除法

4樓：匿名使用者

# include

void simplify( const int *p1,const int *p2);

void main()

void simplify( const int *p1,const int *p2)

int x = *p1/min;

int y = *p2/min;

printf ("%d/%d",x,y);}

5樓：

int fun(int a,int b)

return a;}

c語言輾轉相除法

輾轉相除法求最大公約數的原理是什麼？

6樓：杜泰華

無論怎樣除，若有一個數是被除數和除數的公約數，則餘數一定也含有這個公約數。（被除數≥除數）