Python求最大公約數(shù)：幾種實(shí)現(xiàn)方式全解析
在編寫 Python 程序中，經(jīng)常需要求取兩個(gè)或多個(gè)數(shù)的最大公約數(shù)。求最大公約數(shù)是一道基礎(chǔ)算法題，也是許多高級算法的基礎(chǔ)。Python 作為一門通用編程語言，提供了多種求最大公約數(shù)的實(shí)現(xiàn)方式。本文將介紹幾種 Python 求最大公約數(shù)的方法，包括輾轉(zhuǎn)相除法、更相減損法、歐幾里得算法（輾轉(zhuǎn)相減法）、Euclid 擴(kuò)展算法等。
輾轉(zhuǎn)相除法
輾轉(zhuǎn)相除法又稱為歐幾里得算法（Euclidean Algorithm）。該算法基于一個(gè)定理：兩個(gè)整數(shù)的最大公約數(shù)等于其中較小的數(shù)與兩數(shù)相除余數(shù)的最大公約數(shù)。用公式表達(dá)為：gcd(a, b) = gcd(b, a mod b)
例如，求取 60 和 24 的最大公約數(shù)：文章來源：http://www.zghlxwxcb.cn/news/detail-460506.html
gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12
代碼實(shí)現(xiàn)：
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
更相減損法
更相減損法是古代中國數(shù)學(xué)家采用的一種求最大公約數(shù)的方法。該算法基于一個(gè)結(jié)論：兩個(gè)正整數(shù)的最大公約數(shù)等于它們的差值的最大公約數(shù)。用公式表達(dá)為：gcd(a, b) = gcd(|a-b|, min(a,b))
例如，求取 60 和 24 的最大公約數(shù)：
gcd(60,24) = gcd(60-24, 24) = gcd(36, 24)
gcd(36,24) = gcd(36-24, 24) = gcd(12, 24)
gcd(12,24) = gcd(24-12, 12) = gcd(12, 12)文章來源地址http://www.zghlxwxcb.cn/news/detail-460506.html
到了這里，關(guān)于Python求最大公約數(shù)：幾種實(shí)現(xiàn)方式全解析的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
