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

我們提供的服務(wù)有：成都網(wǎng)站制作、成都網(wǎng)站建設(shè)、微信公眾號(hào)開(kāi)發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、通渭ssl等。為1000多家企事業(yè)單位解決了網(wǎng)站和推廣的問(wèn)題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的通渭網(wǎng)站制作公司

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

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

《九章算術(shù)》是中國(guó)古代的數(shù)學(xué)專著，其中的“更相減損術(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 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))

網(wǎng)站名稱：Python基于更相減損術(shù)實(shí)現(xiàn)求解最大公約數(shù)的方法-創(chuàng)新互聯(lián)
鏈接分享：http://www.chinadenli.net/article22/didicc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、外貿(mào)建站、自適應(yīng)網(wǎng)站、網(wǎng)站排名、小程序開(kāi)發(fā)、電子商務(wù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)