在此示例中，您將學(xué)習(xí)使用兩種不同的方法查找兩個數(shù)字的GCD：函數(shù)和循環(huán)以及歐幾里得算法
要理解此示例，您應(yīng)該了解以下Python編程主題：
兩個數(shù)的最大公因數(shù)(H.C.F)或最大公約數(shù)(G.C.D)是能完美地將兩個給定數(shù)相除的最大正整數(shù)。例如，H.C.F(12, 14)等于2。
# Python程序查找兩個數(shù)字的H.C.F
# 定義一個函數(shù)
def compute_hcf(x, y):
# 選擇較小的數(shù)字
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))輸出結(jié)果
H.C.F. 是 6
這里，存儲在變量num1和num2中的兩個整數(shù)被傳遞給compute hcf()函數(shù)。該函數(shù)計算H.C.F.這兩個數(shù)字并返回它。
在這個函數(shù)中，我們首先確定兩個數(shù)字中較小的那個F只能小于或等于最小的數(shù)。然后我們使用一個for循環(huán)從1到那個數(shù)字。
在每次迭代中，我們檢查我們的數(shù)字是否完美地將兩個輸入數(shù)字相除。如果是這樣，我們將這個數(shù)字存儲為H.C.F.，在循環(huán)結(jié)束時，我們得到的最大的數(shù)字完美地將兩個數(shù)字相除。
上述方法易于理解和實施，但是效率不高。查找HCF的一種更有效的方法是歐幾里得算法。
該算法基于以下事實：兩個數(shù)字的HCF也將它們的差除。
在此算法中，我們將較大者除以較小者，然后取余數(shù)?，F(xiàn)在，將較小者除以該余數(shù)。重復(fù)直到剩余為0。
例如，如果我們想求54和24的hcf，我們用54除以24。余數(shù)是6。24除以6，余數(shù)是0。因此，6是必需的hcf
# 函數(shù)查找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)在這里我們循環(huán)直到y(tǒng)變?yōu)榱?。該語句x, y = y, x % y在Python中交換值。單擊此處以了解有關(guān)在Python中交換變量的更多信息。
在每次迭代中，我們同時將y的值放在x中，其余的(x % y)放在y中。當(dāng)y變?yōu)?時，我們得到x的hcf。