熱線電話：13121318867

登錄
首頁精彩閱讀Python基于更相減損術實現求解最大公約數的方法
Python基于更相減損術實現求解最大公約數的方法
2018-04-18
收藏

Python基于更相減損術實現求解最大公約數的方法

第一步：任意給定兩個正整數；判斷它們是否都是偶數。若是，則用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))

運行結果：


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

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

defMaxCommDivisor(m,n):
  com_factor=1
  ifm==n:
    returnn
  else:
    # process for even number
    whilem%2==0andn%2==0:
      m=int(m/2)
      n=int(n/2)
      com_factor*=2
    ifm < n:
      m,n=n,m
    diff=m-n
    whilen !=diff:
      m=diff
      ifm < n:
        m,n=n,m
      diff=m-n
    returnn*com_factor
print(MaxCommDivisor(55,120))
print(MaxCommDivisor(55,77))
print(MaxCommDivisor(32,64))
print(MaxCommDivisor(16,128))

通過修改，上面程序執行結果如下

雖說這段程序寫出來看著有點怪怪的，但是總體的算法還是實現了。與輾轉相除等算法相比，這個在循環的層級上有一定的概率會減小。特別是最后的兩組測試數字對兒，這種情況下的效果要好一些。但是，總體上的算法的效率，現在我還不能夠給個準確的衡量。




CDA數據分析師考試相關入口一覽（建議收藏）：

? 想報名CDA認證考試，點擊>>>   “CDA報名” 了解CDA考試詳情；

? 想學習CDA考試教材，點擊>>> “CDA教材” 了解CDA考試詳情；

? 想加入CDA考試題庫，點擊>>> “CDA題庫” 了解CDA考試詳情；

? 想了解CDA考試含金量，點擊>>> “CDA含金量” 了解CDA考試詳情；

python

數據分析咨詢請掃描二維碼

若不方便掃碼，搜微信號：CDAshujufenxi

上一篇回歸系列（一）| 怎樣正確地理解線性回歸
下一篇2020美國總統競選大戲開鑼，川普當選的奇跡會再發生嗎？
數據分析師考試動態
CDA報考指南
數據分析學習
數據分析師資訊
更多

CDA教育閉環

常見問題

關于我們

CDA數據分析師公眾號

  • CDA數據分析師公眾號

CDA考試中心小程序

  • CDA考試中心服務號

CDA數據分析師App下載

  • CDA數據分析師App下載
Copyright © 2015-2021, www.ruiqisteel.com All Rights Reserved. CDA數據分析師(北京國富如荷網絡科技有限公司) 版權所有 京ICP備11001960號-9 京公網安備 11010802034615號 經營許可證編號：京B2-20210330
聯系電話：13321103290 (微信同號)

OK
客服在線
立即咨詢
日韩人妻系列无码专区视频,先锋高清无码,无码免费视欧非,国精产品一区一区三区无码
客服在線
立即咨詢