這種方法如何確定最大公約數？

Question

在數學中，兩個或更多個整數的最大公約數（gcd），當它們中的至少一個不爲零時，是將數除以餘數的最大正整數。例如，8和12的最大公約數是4 Wikipedia

以下方法能夠確定的GCD：

def gcd(a, b) 
    if a % b == 0 
    b 
    else 
    gcd(b, a % b) 
    end 
end 
p gcd(4, 12) 
#=> 4 

請問這個方法的工作？

這是有道理的，如果a % b == 0然後b是可以進入a和b的最大數字。

但爲什麼再次調用相同的方法，但切換參數並再次取模數？

我並不喜歡else部分背後的推理。

編輯：

添加一些puts報表，使其更清晰：

def gcd(a, b) 
    puts "Inside gcd, a: #{a}, b: #{b}, a \% b: #{a % b}" 

    if a % b == 0 
    puts "Inside if, a: #{a}, b: #{b}, a \% b: #{a % b}" 
    b 
    else 
    puts "Inside else, a: #{a}, b: #{b}, a \% b: #{a % b}" 
    gcd(b, a % b) 
    end 
end 

p gcd(55, 105) 

標準輸出：

Inside gcd, a: 55, b: 105, a % b: 55 
Inside else, a: 55, b: 105, a % b: 55 
Inside gcd, a: 105, b: 55, a % b: 50 
Inside else, a: 105, b: 55, a % b: 50 
Inside gcd, a: 55, b: 50, a % b: 5 
Inside else, a: 55, b: 50, a % b: 5 
Inside gcd, a: 50, b: 5, a % b: 0 
Inside if, a: 50, b: 5, a % b: 0 
5 

Answer 1

這就是所謂的歐幾里德算法。

爲了理解爲什麼您需要交換數字並進行另一次遞歸調用，您需要了解它背後的實際數學是什麼。看看這個YouTube video看看歐幾里德算法是如何工作的。否則，我寫了下面的算法的解釋。歐幾里德算法的

---

正式解釋：

輸入

• 兩個正整數，a和b。

輸出的a和b

• 最大公約數，GCD。

內部計算

• 如果< B，交換a和b。
• 除以b得到餘數r。如果r = 0，則報告b作爲a和b的GCD。
• 將b替換爲b並將r替換爲b。返回到上一步。

---

例如：

gcd(40,7) 

40 = 7(5) + 5 
7 = 5(1) + 2 
5 = 2(2) + 1 <-- your gcd 
2 = 1(2) + 0 

但是，這意味着...

gcd(40,7) = gcd(7, gcd(40,7)) = 
gcd(7, 5) = gcd(5, gcd(7, 5)) = 
gcd(5, 2) = gcd(2, gcd(5, 2)) = 
gcd(2, 1) = 0 

當gcd(a,b) = 0，b爲等於 1，所以我們return b

現在這裏是的重要部分！如果我們沒有交換數字，我們將無法執行必要的數學運算，並最終跟蹤b的位置，這是我們的gcd。

---

因此，交換本質上是需要保持正確的因素。嘗試做沒有交換的數學，你會很快看到爲什麼它很重要;）

希望這有助於！

Answer 2

關鍵的事實是，對於每個因子g B的，當且僅當g除以％b（特別是對於GCD來說），我們有g除法。這是通過身份a =（a/b）* b + a％b，其中/是整數除法，因爲g除以a（分別爲a b），g除以b的所有倍數，包括（a/b ）* b，因此g除以％b（分別爲a）。遞歸調用因此在結束時給出正確的結果，並且因爲我們總是減小輸入的大小（除了根呼叫），它會終止。

切換參數的原因是，較大的數字是第一個參數，因爲對於正數a和b，0 < = a％b < b。這確保遞歸調用取得進展。