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

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.

但为什么再次调用相同的方法,但转换args并再次采用模数？

我不是在讨论这个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

关键事实是，对于 b 的每个除数 g，当且仅当 g 除以 a % b 时，我们有 g 除以 a（特别是，这适用于 GCD）。这是由恒等式 a = (a / b) * b + a % b，其中 / 是整数除法，因为 g 除以 a（分别为 a % b），而 g 除以 b 的所有倍数，包括 (a / b ) * b，因此 g 除以 a % b（分别为 a）。因此，递归调用在终止时给出正确的结果，并且它终止是因为我们总是减小输入的大小（除了在根调用处）。

切换参数的原因是较大的数字是第一个参数，因为 0 <= a % b < b 表示正 a 和 b。这确保递归调用取得进展。

Answer 2

这就是所谓的欧几里德算法.

为了理解为什么需要交换数字并进行另一次递归调用,你需要了解它背后的实际数学是什么.查看此YouTube视频,了解欧几里德算法的工作原理.否则,我在下面写了我对算法的解释.

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

输入

• 两个正整数,a和b.

产量

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

内部计算

• 如果a <b,则交换a和b.
• 将a除以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时,我们返回 b

现在这里是重要的部分!如果我们没有交换数字,我们将无法执行必要的数学运算,并最终跟踪b的位置,这是我们的gcd.

因此,基本上需要交换来保持正确的因素.尝试在没有交换的情况下进行数学运算,你会很快发现为什么它很重要;)

希望这可以帮助!