python輾轉(zhuǎn)相除法求最大公約數(shù)和最小公倍數(shù)的實現(xiàn)

更新時間：2022年07月16日 09:01:48 作者：阿松丶

這篇文章主要介紹了python輾轉(zhuǎn)相除法求最大公約數(shù)和最小公倍數(shù)的實現(xiàn)方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

輾轉(zhuǎn)相除法求最大公約數(shù)和最小公倍數(shù)

輾轉(zhuǎn)相除法數(shù)學原理

輾轉(zhuǎn)相除法也稱歐幾里得算法，是用來求兩個正整數(shù)的最大公約數(shù)的算法。接下來我們用實例來解釋一下。假如我們需要求12和21的最大公約數(shù)，用輾轉(zhuǎn)相除法是這樣實現(xiàn)的：

21 / 12 = 1 （余 9）
12 / 9 = 1（余 3）
9 / 3 = 3 （余 0）

至此，得到21與12的最大公約數(shù)為3（注意：這里的3是第二個式子取余得到的3，而非最后一個式子相除得到的），然后把兩個數(shù)相乘再除以最大公約數(shù)就可以得到最小公倍數(shù)：（21*12）/ 3 = 84

python代碼實現(xiàn)

接下來我們用python代碼來實現(xiàn)這樣一道題目：

題目：輸入兩個正整數(shù)，求其最大公約數(shù)和最小公倍數(shù)。

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("正整數(shù)m與n的最大公約數(shù)與最小公倍數(shù)分別為：",func(12,21))

正整數(shù)m與n的最大公約數(shù)與最小公倍數(shù)分別為： (3, 84.0)

用遞歸的方式實現(xiàn)

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("正整數(shù)m與n的最大公約數(shù)與最小公倍數(shù)分別為：",rec(12,21))

正整數(shù)m與n的最大公約數(shù)與最小公倍數(shù)分別為： (3, 84.0)

Python3 20.輾轉(zhuǎn)相除法

算法分析

1.算法定義為：在有限的步驟內(nèi)解決數(shù)學問題的程序，即為了解決某項工作或某個問題，所需要有限數(shù)量的機械性或重復性指令與計算步驟。

2.最大公約數(shù)：可整除兩個整數(shù)的最大整數(shù)。

3.用兩個數(shù)中較大的整數(shù)除以較小的數(shù)，求得商和余數(shù)。

源代碼

# coding:gbk
Num_1 = int(input("請輸入一個整數(shù)： "))
Num_2 = int(input("請輸入一個整數(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('輸出這兩個整數(shù)的最大公約數(shù)：', Num_1)