python輾轉相除法求最大公約數和最小公倍數的實現
輾轉相除法求最大公約數和最小公倍數
輾轉相除法數學原理
輾轉相除法也稱歐幾裡得算法,是用來求兩個正整數的最大公約數的算法。接下來我們用實例來解釋一下。假如我們需要求12和21的最大公約數,用輾轉相除法是這樣實現的:
21 / 12 = 1 (餘 9) 12 / 9 = 1(餘 3) 9 / 3 = 3 (餘 0)
至此,得到21與12的最大公約數為3(註意:這裡的3是第二個式子取餘得到的3,而非最後一個式子相除得到的),然後把兩個數相乘再除以最大公約數就可以得到最小公倍數:(21*12)/ 3 = 84
python代碼實現
接下來我們用python代碼來實現這樣一道題目:
題目:輸入兩個正整數,求其最大公約數和最小公倍數。
def func(m,n): a = m b = n # 默認m>n,若不是,則交換 if m < n: m,n = n,m while n != 0: # 對m除n取餘 r = m % n m = n n = r return m,(a*b)/m
print("正整數m與n的最大公約數與最小公倍數分別為:",func(12,21))
正整數m與n的最大公約數與最小公倍數分別為: (3, 84.0)
用遞歸的方式實現
def rec(m,n): # 默認m>n,若不是,則交換 if m < n: m,n = n,m # 終止條件 if n == 0: return m,(a*b)/m # 遞歸部分 return rec(n,m%n) a = 12 b = 21
print("正整數m與n的最大公約數與最小公倍數分別為:",rec(12,21))
正整數m與n的最大公約數與最小公倍數分別為: (3, 84.0)
Python3 20.輾轉相除法
算法分析
1.算法定義為:在有限的步驟內解決數學問題的程序,即為瞭解決某項工作或某個問題,所需要有限數量的機械性或重復性指令與計算步驟。
2.最大公約數:可整除兩個整數的最大整數。
3.用兩個數中較大的整數除以較小的數,求得商和餘數。
源代碼
# coding:gbk Num_1 = int(input("請輸入一個整數: ")) Num_2 = int(input("請輸入一個整數: ")) if Num_1 < Num_2: Tmp_Num = Num_1 # 是交換而不是賦值 Num_1 = Num_2 Num_2 = Tmp_Num while Num_2 != 0: Tmp_Num = Num_1 % Num_2 Num_1 = Num_2 Num_2 = Tmp_Num print('輸出這兩個整數的最大公約數:', Num_1)
結果截圖
以上為個人經驗,希望能給大傢一個參考,也希望大傢多多支持WalkonNet。
推薦閱讀:
- 淺談Python從全局與局部變量到裝飾器的相關知識
- Python函數命名空間和作用域(Local與Global)
- python基礎學習之遞歸函數知識總結
- Python的數據類型與標識符和判斷語句詳解
- python 裝飾器的使用與要點