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)
結果截圖
以上為個人經驗,希望能給大家一個參考,也希望大家多多支持腳本之家。
相關文章
在Python中使用SimpleParse模塊進行解析的教程
這篇文章主要介紹了在Python中使用SimpleParse模塊進行解析的教程,文章來自于IBM官方的開發(fā)者技術文檔,需要的朋友可以參考下2015-04-04Python使用BeautifulSoup解析并獲取圖片的實戰(zhàn)分享
這篇文章主要介紹了Python使用BeautifulSoup解析并獲取圖片的實戰(zhàn)分享,文中通過代碼和圖文結合的方式給大家講解的非常詳細,對大家的學習或工作有一定的幫助,需要的朋友可以參考下2024-06-06