Python實現求解最大公約數的方法

來源：懂視網責編：小采時間：2020-11-27 14:13:01

Python實現求解最大公約數的方法

Python實現求解最大公約數的方法:這次給大家帶來Python實現求解最大公約數的方法，Python實現求解最大公約數的注意事項有哪些，下面就是實戰案例，一起來看一下。先從網上摘錄一段算法的描述如下：更相減損法：也叫更相減損術，是出自《九章算術》的一種求最大公約數的算法，它原本是為約

推薦度：

點擊下載本文 文檔為doc格式

導讀Python實現求解最大公約數的方法:這次給大家帶來Python實現求解最大公約數的方法，Python實現求解最大公約數的注意事項有哪些，下面就是實戰案例，一起來看一下。先從網上摘錄一段算法的描述如下：更相減損法：也叫更相減損術，是出自《九章算術》的一種求最大公約數的算法，它原本是為約

這次給大家帶來Python實現求解最大公約數的方法，Python實現求解最大公約數的注意事項有哪些，下面就是實戰案例，一起來看一下。

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

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

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

翻譯成現代語言如下：

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

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

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

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

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

運行結果：

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

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

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

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