Python基於輾轉相除法求解最大公約數的方法範例

這篇文章主要介紹了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))

#運行結果：

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

PS：這裡再為大家推薦幾款運算工具供大家進一步參考借鑒：

##線上一元函數（方程式）求解計算工具：
http://tools.jb51.net/jisuanqi/equ_jisuanqi

##科學計算器線上使用_高階計算器線上計算：

http://tools.jb51.net/jisuanqi/jsqkexue
## 線上計算器_標準計算器：

http://tools.jb51.net/jisuanqi/jsq
相關推薦：

php計算兩個整數的最大公約數常用演算法小結_PHP教程

使用Python求解最大公約數的實作方法

以上是Python基於輾轉相除法求解最大公約數的方法範例的詳細內容。更多資訊請關注PHP中文網其他相關文章！