輾轉(zhuǎn)相除法簡(jiǎn)介：

輾轉(zhuǎn)相除法， 又名歐幾里德算法（Euclidean algorithm），是求最大公約數(shù)的一種方法。它的具體做法是：用較大數(shù)除以較小數(shù)，再用出現(xiàn)的余數(shù)（第一余數(shù)）去除除數(shù)，再用出現(xiàn)的余數(shù)（第二余數(shù)）去除第一余數(shù)，如此反復(fù)，直到最后余數(shù)是0為止。如果是求兩個(gè)數(shù)的最大公約數(shù)，那么最后的除數(shù)就是這兩個(gè)數(shù)的最大公約數(shù)。

另一種求兩數(shù)的最大公約數(shù)的方法是更相減損法。

輾轉(zhuǎn)相除法舉例：

求 10 ，25的最大公約數(shù)：
25 / 10 = 2 ······5
10 / 5 ? = 2 ······0
所以10，25的最大公約數(shù)為5

輾轉(zhuǎn)相除法代碼實(shí)現(xiàn)：

int gcd(a, b) { return b == 0 ? a : gcd(b, a % b); } //當(dāng)余數(shù)為0時(shí)，最大公約數(shù)就是a，否則繼續(xù)往下遞歸

利用到的原理：(a, b)與(b, a % b)的最大公約數(shù)相同。

歐幾里德算法知識(shí)點(diǎn)：

1、gcd函數(shù)的遞歸層數(shù)不會(huì)超過(guò)4.785lgN + 1.6723, 其中N == max{ a，b }，所以不會(huì)導(dǎo)致棧溢出。

2、gcd函數(shù)不僅可以求解(a, b)的最大公約數(shù)，還可以求解小公倍數(shù)，lcm(a, b) 代表(a, b)的最小公倍數(shù)
那么有l(wèi)cm(a, b) * gcd(a, b) = a * b
所以：lcm(a,b) = a * b / gcd(a, b) 但是最好寫成：lcm(a,b) = a? / gcd(a, b) * b? 這樣一定程度可以避免 a * b 爆long long .

? ??

? ??

證明：

總結(jié)

以上是生活随笔為你收集整理的欧几里得算法原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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