python輾轉(zhuǎn)相除法求最大公約數(shù)和最小公倍數(shù)的實(shí)現(xiàn)
輾轉(zhuǎn)相除法求最大公約數(shù)和最小公倍數(shù)
輾轉(zhuǎn)相除法數(shù)學(xué)原理
輾轉(zhuǎn)相除法也稱歐幾里得算法,是用來求兩個(gè)正整數(shù)的最大公約數(shù)的算法。接下來我們用實(shí)例來解釋一下。假如我們需要求12和21的最大公約數(shù),用輾轉(zhuǎn)相除法是這樣實(shí)現(xiàn)的:
21 / 12 = 1 (余 9) 12 / 9 = 1(余 3) 9 / 3 = 3 (余 0)
至此,得到21與12的最大公約數(shù)為3(注意:這里的3是第二個(gè)式子取余得到的3,而非最后一個(gè)式子相除得到的),然后把兩個(gè)數(shù)相乘再除以最大公約數(shù)就可以得到最小公倍數(shù):(21*12)/ 3 = 84
python代碼實(shí)現(xiàn)
接下來我們用python代碼來實(shí)現(xiàn)這樣一道題目:
題目:輸入兩個(gè)正整數(shù),求其最大公約數(shù)和最小公倍數(shù)。
def func(m,n): ? ? a = m ? ? b = n ? ? # 默認(rèn)m>n,若不是,則交換 ? ? if m < n: ? ? ? ? m,n = n,m ? ? while n != 0: ? ? ? ? # 對(duì)m除n取余 ? ? ? ? r = m % n ? ? ? ? m = n ? ? ? ? n = r ? ? return m,(a*b)/m
print("正整數(shù)m與n的最大公約數(shù)與最小公倍數(shù)分別為:",func(12,21))
正整數(shù)m與n的最大公約數(shù)與最小公倍數(shù)分別為: (3, 84.0)
用遞歸的方式實(shí)現(xiàn)
def rec(m,n): ? ? # 默認(rè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("正整數(shù)m與n的最大公約數(shù)與最小公倍數(shù)分別為:",rec(12,21))
正整數(shù)m與n的最大公約數(shù)與最小公倍數(shù)分別為: (3, 84.0)
Python3 20.輾轉(zhuǎn)相除法
算法分析
1.算法定義為:在有限的步驟內(nèi)解決數(shù)學(xué)問題的程序,即為了解決某項(xiàng)工作或某個(gè)問題,所需要有限數(shù)量的機(jī)械性或重復(fù)性指令與計(jì)算步驟。
2.最大公約數(shù):可整除兩個(gè)整數(shù)的最大整數(shù)。
3.用兩個(gè)數(shù)中較大的整數(shù)除以較小的數(shù),求得商和余數(shù)。
源代碼
# coding:gbk Num_1 = int(input("請(qǐng)輸入一個(gè)整數(shù): ")) Num_2 = int(input("請(qǐng)輸入一個(gè)整數(shù): ")) 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('輸出這兩個(gè)整數(shù)的最大公約數(shù):', Num_1)
結(jié)果截圖
以上為個(gè)人經(jīng)驗(yàn),希望能給大家一個(gè)參考,也希望大家多多支持腳本之家。
- python求最大公約數(shù)和最小公倍數(shù)的簡單方法
- Python自定義函數(shù)實(shí)現(xiàn)求兩個(gè)數(shù)最大公約數(shù)、最小公倍數(shù)示例
- Python實(shí)現(xiàn)的求解最小公倍數(shù)算法示例
- Python實(shí)現(xiàn)利用最大公約數(shù)求三個(gè)正整數(shù)的最小公倍數(shù)示例
- Python基于遞歸算法求最小公倍數(shù)和最大公約數(shù)示例
- Python基于遞歸和非遞歸算法求兩個(gè)數(shù)最大公約數(shù)、最小公倍數(shù)示例
- Python 代碼實(shí)現(xiàn)列表的最小公倍數(shù)
- 最小公倍數(shù)Python實(shí)現(xiàn)的方法例子
相關(guān)文章
在Python中使用SimpleParse模塊進(jìn)行解析的教程
這篇文章主要介紹了在Python中使用SimpleParse模塊進(jìn)行解析的教程,文章來自于IBM官方的開發(fā)者技術(shù)文檔,需要的朋友可以參考下2015-04-04python雙端隊(duì)列原理、實(shí)現(xiàn)與使用方法分析
這篇文章主要介紹了python雙端隊(duì)列原理、實(shí)現(xiàn)與使用方法,結(jié)合實(shí)例形式分析了Python雙端隊(duì)列的概念、原理、定義及使用方法,需要的朋友可以參考下2019-11-11Python使用BeautifulSoup解析并獲取圖片的實(shí)戰(zhàn)分享
這篇文章主要介紹了Python使用BeautifulSoup解析并獲取圖片的實(shí)戰(zhàn)分享,文中通過代碼和圖文結(jié)合的方式給大家講解的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下2024-06-06Python使用BeautifulSoup庫解析網(wǎng)頁
在Python的網(wǎng)絡(luò)爬蟲中,網(wǎng)頁解析是一項(xiàng)重要的技術(shù)。而在眾多的網(wǎng)頁解析庫中,BeautifulSoup庫憑借其簡單易用而廣受歡迎,在本篇文章中,我們將學(xué)習(xí)BeautifulSoup庫的基本用法,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步2023-08-08淺談Tensorflow2對(duì)GPU內(nèi)存的分配策略
本文主要介紹了Tensorflow2對(duì)GPU內(nèi)存的分配策略,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-08-08Pytorch 實(shí)現(xiàn)變量類型轉(zhuǎn)換
這篇文章主要介紹了Pytorch 實(shí)現(xiàn)變量類型轉(zhuǎn)換操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-05-05Python 腳本實(shí)現(xiàn)淘寶準(zhǔn)點(diǎn)秒殺功能
這篇文章主要介紹了python實(shí)現(xiàn)淘寶準(zhǔn)點(diǎn)秒殺腳本,本文圖文實(shí)例相結(jié)合給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-11-11