輾轉(zhuǎn)相除法是求最大公約數(shù)的一種方法。它的具體做法是：用較小數(shù)除較大數(shù)，再用出現(xiàn)的余數(shù)（第一余數(shù)）去除除數(shù)，再用出現(xiàn)的余數(shù)（第二余數(shù)）去除第一余數(shù)，如此反復，直到最后余數(shù)是0為止。如果是求兩個數(shù)的最大公約數(shù)，那么最后的除數(shù)就是這兩個數(shù)的最大公約數(shù)。這個和更相減損術(shù)有著異曲同工之處。

原理：

首先介紹下更相減損術(shù)的原理，假設(shè)有兩個數(shù)161和63，我們要求這兩個數(shù)的最大公因數(shù)，不妨假定這個最大公因數(shù)為m，我們可以將較大的數(shù)161看成63+98，63與98的和161可以被m整除，其中63也可以被m整除，自然98可以被m整除；
所以這個問題就轉(zhuǎn)換為求98和63的最大公因數(shù)m（和上面m相等）
將98看成63+35，其中63可以被m整除，和98也能被m整除，故35也可以被m整除；
所以問題進一步轉(zhuǎn)換為求35和63的最大公因數(shù)m（和上面m相等）
同理轉(zhuǎn)換為求 (63-35)=>28和35 的最大公因數(shù)
然后轉(zhuǎn)換為求28和7的最大公因數(shù)
…（一直減呀減）
后來轉(zhuǎn)換為求7和7的最大公因數(shù)
最后轉(zhuǎn)換為求7和0的最大公因數(shù)
輸出第一個數(shù)字即可；這就是相減損術(shù)的原理
我們發(fā)現(xiàn)求28和7的最大公約數(shù)，一直減7，一直減7…減到不能減為止。這個不斷減7的過程就是除7求余數(shù)（即%7）
這樣我們可以將相減損術(shù)優(yōu)化成輾轉(zhuǎn)相除法，上面給出了思考過程，有興趣可以百度嚴謹?shù)淖C明過程。

c語言代碼如下：

#include<stdio.h> int gcd(int a, int b) {int t;while(b!=0) {t=a%b;a=b;b=t;}return a; } int main() {int a,b;scanf("%d%d",&a,&b);printf("gcd=%d\n",gcd(a,b));return 0; }

同理計算最小公倍數(shù)：只要用這兩個數(shù)的乘積除以最大公因數(shù)即可
printf(“l(fā)cm=%d\n”,a*b/gcd(a,b)）

總結(jié)

以上是生活随笔為你收集整理的辗转相除法的原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。