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

我們提供的服務有：成都網站制作、成都網站建設、微信公眾號開發、網站優化、網站認證、通渭ssl等。為1000多家企事業單位解決了網站和推廣的問題。提供周到的售前咨詢和貼心的售后服務，是有科學管理、有技術的通渭網站制作公司

先從網上摘錄一段算法的描述如下：

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

《九章算術》是中國古代的數學專著，其中的“更相減損術”可以用來求兩個數的大公約數，即“可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。”

翻譯成現代語言如下：

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

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

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

不管怎么說，先實現一下上面的算法描述：

# -*- 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))

網站名稱：Python基于更相減損術實現求解最大公約數的方法-創新互聯
鏈接分享：http://vcdvsql.cn/article22/didicc.html

成都網站建設公司_創新互聯，為您提供網站收錄、外貿建站、自適應網站、網站排名、小程序開發、電子商務

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯