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

本文實例講述了Python基于輾轉相除法求解最大公約數的方法。分享給大家供大家參考，具體如下：

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

這個題目我最初的理解理解錯了，自然也沒有做出標準答案?，F在按照標準答案的解答寫一下相應的代碼實現：

# -*- coding:utf-8 -*-

#! python2

def MaxCommDivisor(m,n):

while m * n != 0:

m = m % n

if m == 0:

return n

else:

n = n % m

if n == 0:

return m

print(MaxCommDivisor(55,120))

程序的執行結果：

交換一下兩個數字的位置，代碼如下：

# -*- coding:utf-8 -*-

#! python2

def MaxCommDivisor(m,n):

while m * n != 0:

m = m % n

if m == 0:

return n

else:

n = n % m

if n == 0:

return m

print(MaxCommDivisor(120,55))

程序的執行結果：

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

運行結果：

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

完 謝謝觀看

總結

以上是生活随笔為你收集整理的python辗转相除_Python基于辗转相除法求解最大公约数的方法示例的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。