Python程序查找最大公因數（HCF）或最大公約數（GCD）

在此示例中，您將學習使用兩種不同的方法查找兩個數字的GCD：函數和循環以及歐幾里得算法

要理解此示例，您應該了解以下Python編程主題：

兩個數的最大公因數(H.C.F)或最大公約數(G.C.D)是能完美地將兩個給定數相除的最大正整數。例如，H.C.F(12, 14)等于2。

源代碼：使用循環

示例# Python程序查找兩個數字的H.C.F

# 定義一個函數

def compute_hcf(x, y):

# 選擇較小的數字

if x > y:

smaller = y

else:

smaller = x

for i in range(1, smaller+1):

if((x % i == 0) and (y % i == 0)):

hcf = i

return hcf

num1 = 54

num2 = 24

print("H.C.F. 是", compute_hcf(num1, num2))

輸出結果H.C.F. 是 6

這里，存儲在變量num1和num2中的兩個整數被傳遞給compute hcf()函數。該函數計算H.C.F.這兩個數字并返回它。

在這個函數中，我們首先確定兩個數字中較小的那個F只能小于或等于最小的數。然后我們使用一個for循環從1到那個數字。

在每次迭代中，我們檢查我們的數字是否完美地將兩個輸入數字相除。如果是這樣，我們將這個數字存儲為H.C.F.，在循環結束時，我們得到的最大的數字完美地將兩個數字相除。

上述方法易于理解和實施，但是效率不高。查找HCF的一種更有效的方法是歐幾里得算法。

歐幾里得算法

該算法基于以下事實：兩個數字的HCF也將它們的差除。

在此算法中，我們將較大者除以較小者，然后取余數。現在，將較小者除以該余數。重復直到剩余為0。

例如，如果我們想求54和24的hcf，我們用54除以24。余數是6。24除以6，余數是0。因此，6是必需的hcf

源代碼：使用歐幾里得算法

示例# 函數查找HCF的使用歐幾里德算法

def compute_hcf(x, y):

while(y):

x, y = y, x % y

return x

hcf = compute_hcf(300, 400)

print("The HCF is", hcf)

在這里我們循環直到y變為零。該語句x, y = y, x % y在Python中交換值。單擊此處以了解有關在Python中交換變量的更多信息。

在每次迭代中，我們同時將y的值放在x中，其余的(x % y)放在y中。當y變為0時，我們得到x的hcf。

總結

以上是生活随笔為你收集整理的python用递归方式实现最大公约数_Python程序查找最大公因数（HCF）或最大公约数（GCD）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。