欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python實現(xiàn)求解最大公約數(shù)的五種方法總結(jié)

 更新時間:2022年07月11日 15:08:05   作者:Kristian-c  
求最大公約數(shù)是習題中比較常見的類型,本文小編將給大家提供五種比較常見的算法,都是用Python語言實現(xiàn)的,感興趣的小伙伴可以了解一下

求最大公約數(shù)是習題中比較常見的類型,下面小編會給大家提供五種比較常見的算法,記得幫忙點個贊哦!

一般來說,最大公約數(shù)的求法大概有5種

方法一:短除法

短除法是求最大公因數(shù)的一種方法,也可用來求最小公倍數(shù)。求幾個數(shù)最大公因數(shù)的方法,開始時用觀察比較的方法,即:先把每個數(shù)的因數(shù)找出來,然后再找出公因數(shù),最后在公因數(shù)中找出最大公因數(shù)。后來,使用分解質(zhì)因數(shù)法來分別分解兩個數(shù)的因數(shù),再進行運算。之后又演變?yōu)槎坛ā6坛ㄟ\算方法是先用一個除數(shù)除以能被它除盡的一個質(zhì)數(shù),以此類推,除到兩個數(shù)的商是互質(zhì)數(shù)為止。

簡單來說就是逐步找出兩個數(shù)的所有公約數(shù),再將這些公約數(shù)累乘起來,就能得到最大公約數(shù)啦!

a=int(input("please input the first number:"))
b=int(input("please input the second number:"))
m,n=a,b #  創(chuàng)建兩個變量存儲a和b
t=1 #  創(chuàng)建t作為最大公約數(shù)的載體
for i in range(2,min(a,b)):
    while (a%i==0 and b%i==0):
       t*=i #  所有公約數(shù)累乘起來
       a/=i
       b/=i
print((f"{m},{n}的最大公約數(shù)為:{t}"))

這種方法雖然有點麻煩,但是邏輯卻很清楚,不容易出錯。

方法二:歐幾里得算法(輾轉(zhuǎn)相除法)

歐幾里得算法是用來求兩個正整數(shù)最大公約數(shù)的算法。古希臘數(shù)學家歐幾里得在其著作《The Elements》中最早描述了這種算法,所以被命名為歐幾里得算法。      

假如需要求 1997 和 615 兩個正整數(shù)的最大公約數(shù),用歐幾里得算法,是這樣進行的:

1997 / 615 = 3······152

615 / 152 = 4······7

152 / 7 = 21······5

7 / 5 = 1······2

5 / 2 = 2······1

2 / 1 = 2······0

至此,最大公約數(shù)為1

以除數(shù)和余數(shù)反復做除法運算,當余數(shù)為 0 時,取當前算式除數(shù)為最大公約數(shù),所以就得出了 1997 和 615 的最大公約數(shù) 1。

明白了這其中的邏輯,我們就可以著手開始寫程序啦!

a=int(input("please input the first number:"))
b=int(input("please input the second number:"))
#  首先要給兩數(shù)排序,保證大數(shù)除以小數(shù)
m=max(a,b)
n=min(a,b)
t=m%n
while t!=0:
    m,n=n,t #  仔細觀察不難發(fā)現(xiàn):每個除式的m、n是都是上一個式子的n和余數(shù)
    t=m%n #  更新余數(shù)
print(f"{a}和的最大公約數(shù)為{n}")

當然了,遞歸方法也能實現(xiàn)歐幾里得算法。

def GCD(a,b):
    #  比較大小,保證大數(shù)除以小數(shù)
    if a<b:
        a,b=b,a
    #  判斷是否能整除,若能整除,直接返回被除數(shù)
    if a%b==0:
        return b
    #  若不能整除,則返回函數(shù)GCD,參數(shù)做相應變化
    else:
        return GCD(b,a%b)
a=int(input("please input the first number:"))
b=int(input("please input the second number:"))
gcd=GCD(a,b)
print(f"{a}和的最大公約數(shù)為{gcd}")

方法三:更相減損術(shù)

更相減損術(shù)是出自《九章算術(shù)》的一種求最大公約數(shù)的算法,它原本是為約分而設(shè)計的,但它適用于任何需要求最大公約數(shù)的場合。原文是:

可半者半之,不可半者,副置分母、子之數(shù),以少減多,更相減損,求其等也。以等數(shù)約之。     

白話文譯文:

(如果需要對分數(shù)進行約分,那么)可以折半的話,就折半(也就是用2來約分)。如果不可以折半的話,那么就比較分母和分子的大小,用大數(shù)減去小數(shù),互相減來減去,一直到減數(shù)與差相等為止,用這個相等的數(shù)字來約分。

具體步驟:

第一步:任意給定兩個正整數(shù);判斷它們是否都是偶數(shù)。若是,則用2約簡;若不是則執(zhí)行第二步。

第二步:以較大的數(shù)減較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減小數(shù)。繼續(xù)這個操作,直到所得的減數(shù)和差相等為止。

則第一步中約掉的若干個2的積與第二步中等數(shù)的乘積就是所求的最大公約數(shù)。

其中所說的“等數(shù)”,就是公約數(shù)。求“等數(shù)”的辦法是“更相減損”法。

現(xiàn)在使用更相減損術(shù)求98與63的最大公約數(shù)。

解:由于63不是偶數(shù),把98和63以大數(shù)減小數(shù),并輾轉(zhuǎn)相減:

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以,98和63的最大公約數(shù)等于7。

a=int(input("please input the first number:"))
b=int(input("please input the second number:"))
#  首先要給兩數(shù)排序,保證大數(shù)減小數(shù)
m=max(a,b)
n=min(a,b)
#  判斷兩數(shù)是否都是偶數(shù),如果都是偶數(shù)就同時除2
while m%2==0 and n%2==0:
    m,n=m/2,n/2
t=m-n
#  判斷條件是減數(shù)和差相等
while n!=t:
    m,n=max(n,t),min(n,t) #  每減一輪之后,都要重新判斷減數(shù)和差的大小,再次以大數(shù)減去小數(shù)
    t=m-n
print(f"{a}和的最大公約數(shù)為{n}")

方法四:窮舉法(枚舉法)

從兩個數(shù)中較小數(shù)開始,由小到大列舉,找出公約數(shù)并保證該公約數(shù)也屬于較大數(shù),這些公約數(shù)的最大者就是最大公約數(shù);也可以從大到小列舉,直到找出公約數(shù)后跳出循環(huán),該公約數(shù)即是最大公約數(shù)。

a=int(input("please input the first number:"))
b=int(input("please input the second number:"))
p,q=min(a,b),max(a,b)
lst=[]
for i in range(1,p+1):
    if p%i==0 and q%i==0:
        lst.append(i)
gcd=max(lst)
print(f"{a}和的最大公約數(shù)為{gcd}")
 
#a=int(input("please input the first number:"))
#b=int(input("please input the second number:"))
#p,q=min(a,b),max(a,b)
#gcd=0
#for i in range(p,0,-1):
#    if p%i==0 and q%i==0:
#        gcd=i
#        break
#print(f"{a}和的最大公約數(shù)為{gcd}")

方法五:Stein算法

Stein算法是一種計算兩個數(shù)最大公約數(shù)的算法,是針對歐幾里德算法在對大整數(shù)進行運算時,需要試商導致增加運算時間的缺陷而提出的改進算法。

歐幾里得算法缺陷:

歐幾里德算法是計算兩個數(shù)最大公約數(shù)的傳統(tǒng)算法,無論從理論還是從實際效率上都是很好的。但是卻有一個致命的缺陷,這個缺陷在素數(shù)比較小的時候一般是感覺不到的,只有在大素數(shù)時才會顯現(xiàn)出來。

一般實際應用中的整數(shù)很少會超過64位(當然已經(jīng)允許128位了),對于這樣的整數(shù),計算兩個數(shù)之間的模是很簡單的。對于字長為32位的平臺,計算兩個不超過32位的整數(shù)的模,只需要一個指令周期,而計算64位以下的整數(shù)模,也不過幾個周期而已。但是對于更大的素數(shù),這樣的計算過程就不得不由用戶來設(shè)計,為了計算兩個超過64位的整數(shù)的模,用戶也許不得不采用類似于多位數(shù)除法手算過程中的試商法,這個過程不但復雜,而且消耗了很多CPU時間。對于現(xiàn)代密碼算法,要求計算128位以上的素數(shù)的情況比比皆是,設(shè)計這樣的程序迫切希望能夠拋棄除法和取模。

看下面兩個結(jié)論:

gcd(a,a)=a,也就是一個數(shù)和其自身的公約數(shù)仍是其自身。

gcd(ka,kb)=k gcd(a,b),也就是最大公約數(shù)運算和倍乘運算可以交換。特殊地,當k=2時,說明兩個偶數(shù)的最大公約數(shù)必然能被2整除。

當k與b互為質(zhì)數(shù),gcd(ka,b)=gcd(a,b),也就是約掉兩個數(shù)中只有其中一個含有的因子不影響最大公約數(shù)。特殊地,當k=2時,說明計算一個偶數(shù) 和一個奇數(shù)的最大公約數(shù)時,可以先將偶數(shù)除以2。

:param a: 第一個數(shù)

:param b: 第二個數(shù)

:return: 最大公約數(shù)

def gcd_Stein(a, b):
    #  保證b比a小
    if a < b:
        a, b = b, a
    if (0 == b):
        return a
    #  a、b都是偶數(shù),除2右移一位即可
    if a % 2 == 0 and b % 2 == 0:
        return 2 * gcd_Stein(a / 2, b / 2)
    #  a是偶數(shù)
    if a % 2 == 0:
        return gcd_Stein(a / 2, b)
    #  b是偶數(shù)
    if b % 2 == 0:
        return gcd_Stein(a, b / 2)
    #  都是奇數(shù)
    return gcd_Stein((a + b) / 2, (a - b) / 2)
 
a=int(input("please input the first number:"))
b=int(input("please input the second number:"))
gcd=int(gcd_Stein(a,b))
print(f"{a}和的最大公約數(shù)為{gcd}")

以上就是Python實現(xiàn)求解最大公約數(shù)的五種方法總結(jié)的詳細內(nèi)容,更多關(guān)于Python求最大公約數(shù)的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

最新評論