本文實例講述了Python基于更相減損術(shù)實現(xiàn)求解最大公約數(shù)的方法。分享給大家供大家參考，具體如下：

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

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

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

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

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

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

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

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

# -*- coding:utf-8 -*-
#! python2
def MaxCommDivisor(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 divisor
  while m - n != n:
    diff = m - n
    if diff > n:
      m = diff
    else:
      m = n
      n = diff
  return n
print(MaxCommDivisor(55,120))
print(MaxCommDivisor(55,77))
print(MaxCommDivisor(32,64))
print(MaxCommDivisor(16,128))

運行結(jié)果：

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

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

def MaxCommDivisor(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(MaxCommDivisor(55,120))
print(MaxCommDivisor(55,77))
print(MaxCommDivisor(32,64))
print(MaxCommDivisor(16,128))

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

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

PS：這里再為大家推薦幾款計算工具供大家進一步參考借鑒：

在線一元函數(shù)（方程）求解計算工具：
http://tools.jb51.net/jisuanqi/equ_jisuanqi

科學(xué)計算器在線使用_高級計算器在線計算：
http://tools.jb51.net/jisuanqi/jsqkexue

在線計算器_標(biāo)準(zhǔn)計算器：
http://tools.jb51.net/jisuanqi/jsq

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)學(xué)運算技巧總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》

希望本文所述對大家Python程序設(shè)計有所幫助。

最新評論