Python如何求得最大公約數

這次為大家帶來Python怎麼求得最大公約數，Python求得最大公約數的注意事項有哪些，下面就是實戰案例，一起來看一下。

先前總結過一次高德納TAOCP中的最大公約數求解，其實課後題中的演算法修改要求實現的是輾轉相除法求解最大公約數。

這個題目我最初的理解理解錯了，自然也沒有做出標準答案。現在就按照標準答案的解答寫一下對應的程式碼實作：

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
  while m * n != 0:
    m = m % n
    if m == 0:
      return n
    else:
      n = n % m
      if n == 0:
        return m
print(MaxCommpisor(55,120))

程式的執行結果：

交換兩個數字的位置，程式碼如下：

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
  while m * n != 0:
    m = m % n
    if m == 0:
      return n
    else:
      n = n % m
      if n == 0:
        return m
print(MaxCommpisor(120,55))

程式的執行結果：

題目提示中提到了會降低效率，透過上面的程式碼來看，效率的損失應該是在除法以及判斷上。在此，把之前演算法的程式碼拿過來比較一下：

def CommDevisor(m,n):
  r = m % n
  while r != 0:
    m = n
    n = r
    r = m % n
  return n
print(CommDevisor(120,25))

運行結果：

新演算法在循環中，多了一個除法以及比較操作。其實，比較的效率還是不錯的，但是除法的運算會導致效率的降低。

相信看了本文案例你已經掌握了方法，更多精彩請關注php中文網其它相關文章！

推薦閱讀：

Python Numpy如何操作陣列與矩陣

怎麼操作Python遍歷numpy陣列

以上是Python如何求得最大公約數的詳細內容。更多資訊請關注PHP中文網其他相關文章！