这个方法如何确定最大公约数？

Question

在数学中，两个或多个整数的最大公约数（gcd），当其中至少一个不为零时，是能够整除这些数字而没有余数的最大正整数。例如，8和12的GCD是4。维基百科 以下方法能够确定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

- mbigras

---

也许只需添加一些 puts 语句以查看它的运行情况？有趣的是，Ruby 内置了 12.gcd(4) 函数。 - akuhn

如果你尝试在55和105上运行一下，我认为这个方法会更清晰明了。 - Gordon Linoff

Answer 1

这就是所谓的欧几里得算法。

为了理解为什么需要交换数字并进行另一个递归调用，您需要了解其背后的实际数学原理。请查看YouTube视频以了解欧几里得算法的工作原理。否则，我在下面写出了该算法的解释。

---

欧几里得算法的正式解释：

输入

• 两个正整数a和b。

输出

• a和b的最大公约数gcd。

内部计算

• 如果a < b，则交换a和b。
• 将a除以b并获取余数r。如果r = 0，则将b报告为a和b的GCD。
• 将a替换为b，并将b替换为r。返回到上一步。

---

例如：

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，因此我们返回 b。

现在是重要的部分！如果我们不交换数字，我们将无法执行必要的数学运算，并最终跟踪 b 的位置，而这正是我们的 gcd。

所以，交换实际上是为了保持因子在右侧。尝试在没有交换的情况下进行数学计算，您很快就会发现为什么它很重要 ;)

希望这有所帮助！

- Tim

Answer 2

关键的事实是，对于b的每个因子g，当且仅当g除以a时，g才能被除以a％b（特别地，这适用于GCD）。这是通过恒等式a =（a / b）* b + a％b得到的，其中/是整数除法，因为g除以a（分别为a％b），并且g除以所有b的倍数，包括（a / b）* b，因此g除以a％b（分别为a）。因此，如果递归调用终止，则可以给出正确的结果，并且它会终止，因为我们总是减小输入的大小（除了根调用）。

将参数交换的原因是让较大的数字成为第一个参数，因为对于正的a和b，0 <= a％b

- David Eisenstat