Python實(shí)現(xiàn)求解最大公約數(shù)的方法

先從網(wǎng)上摘錄一段算法的描述如下：

更相減損法：也叫 更相減損術(shù)，是出自《 九章算術(shù)》的一種求最大公約數(shù)的算法，它原本是為 約分而設(shè)計(jì)的，但它適用于任何需要求最大公約數(shù)的場(chǎng)合。

《九章算術(shù)》是中國(guó)古代的數(shù)學(xué)專(zhuān)著，其中的“更相減損術(shù)”可以用來(lái)求兩個(gè)數(shù)的最大公約數(shù)，即“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之。”

翻譯成現(xiàn)代語(yǔ)言如下：

第一步：任意給定兩個(gè)正整數(shù)；判斷它們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若不是則執(zhí)行第二步。

第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止。

看完上面的描述，我的第一反應(yīng)是這個(gè)描述是不是有問(wèn)題？從普適性來(lái)說(shuō)的話，應(yīng)該是有問(wèn)題的。舉例來(lái)說(shuō)，如果我求解4和4的最大公約數(shù)，可半者半之之后，結(jié)果肯定錯(cuò)了！后面的算法也不能夠進(jìn)行！

不管怎么說(shuō)，先實(shí)現(xiàn)一下上面的算法描述：

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
 # even process
 while m % 2 == 0 and n % 2 == 0:
 m = m / 2
 n = n / 2
 # exchange order when needed
 if m < n:
 m,n = n,m
 # calculate the max comm pisor
 while m - n != n:
 diff = m - n
 if diff > n:
 m = diff
 else:
 m = n
 n = diff
 return n
print(MaxCommpisor(55,120))
print(MaxCommpisor(55,77))
print(MaxCommpisor(32,64))
print(MaxCommpisor(16,128))

運(yùn)行結(jié)果：

不用說(shuō)，上面程序執(zhí)行錯(cuò)誤百出。那么該如何更正呢？

首先，除的2最終都應(yīng)該再算回去！這樣，程序修改如下：

def MaxCommpisor(m,n):
 com_factor = 1
 if m == n:
 return n
 else:
 # process for even number
 while m % 2 == 0 and n % 2 == 0:
 m = int(m / 2)
 n = int(n / 2)
 com_factor *= 2
 if m < n:
 m,n = n,m
 diff = m - n
 while n != diff:
 m = diff
 if m < n:
 m,n = n,m
 diff = m - n
 return n * com_factor
print(MaxCommpisor(55,120))
print(MaxCommpisor(55,77))
print(MaxCommpisor(32,64))
print(MaxCommpisor(16,128))

通過(guò)修改，上面程序執(zhí)行結(jié)果如下

雖說(shuō)這段程序?qū)懗鰜?lái)看著有點(diǎn)怪怪的，但是總體的算法還是實(shí)現(xiàn)了。與輾轉(zhuǎn)相除等算法相比，這個(gè)在循環(huán)的層級(jí)上有一定的概率會(huì)減小。特別是最后的兩組測(cè)試數(shù)字對(duì)兒，這種情況下的效果要好一些。但是，總體上的算法的效率，現(xiàn)在我還不能夠給個(gè)準(zhǔn)確的衡量。

相信看了本文案例你已經(jīng)掌握了方法，更多精彩請(qǐng)關(guān)注Gxl網(wǎng)其它相關(guān)文章！

推薦閱讀：

Pycharm的使用技巧總結(jié)

python如何取得二維數(shù)組局部峰值

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com