该方法如何确定最大公约数? [英] How does this method determine the greatest common divisor?

问题描述

在数学中，两个或多个整数的最大公约数(gcd)(当其中至少一个不为零时)是将数字除而无余的最大正整数.例如，GCD的8和12为4.维基百科

以下方法可以确定GCD:

The following method is able to determine the 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 .

It makes sense if a % b == 0 then b is the biggest number that can go into both a and b.

但是为什么要再次调用相同的方法，但要在args周围切换并再次获取模数呢?

But why call the same method again but switch around the args and take the modulus again?

我不理解 else 部分背后的原因.

I'm not grokking the reasoning behind the else part.

添加一些 put 语句使其更清晰:

Adding some puts statements to make it clearer:

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

推荐答案

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

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

In order to understand why you need to swap the numbers and make another recursion call you need to understand what is the actual maths behind it. Check this YouTube video out to see how Euclidean algorithm works. Otherwise, I wrote my explanation of the algorithm below.

输入

Input

• 两个正整数a和b.

输出

Output

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

内部计算

Internal computation

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

---

例如:

gcd(40,7)

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

但是，这意味着...

but, this implies that...

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

when gcd(a,b) = 0, b is equal to 1, so we return b

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

Now here is the important part! If we didn't swap numbers around we wouldn't be able to perform the necessary maths and, ultimately, track the location of b, which is our gcd.

因此，本质上需要交换以保持正确的因素.尝试进行数学运算而无需进行交换，您将很快了解为什么它很重要;)

So, the swap is essentially needed to keep the factors on the right. Try doing the maths without the swaps and you'll quickly see why it is important ;)

希望这会有所帮助！

这篇关于该方法如何确定最大公约数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！