最大公分母函数没有意义

Question

我发现有一个功能可以使用，但我不明白为什么它可以使用。我认为它应该输出 8，但它给了我正确答案 4。顺便说一下，这是 Python。

def gcd (a, b):
    while(b != 0):
        t = b
        a = b
        b = t % b

return a

同样，当 a = 8 和 b = 20 时，它正确地输出 4，但是当我打印 (8 % 20) 时，它输出 8。那我错过了什么？

Answer 1

你这里指定的是Euclidean method [wiki]。你的代码有错字，应该是：

def gcd (a, b):
    while(b != 0):
        <b>t = a</b>
        a = b
        b = t % b
    return a

请注意，它在每次迭代中“交换”a 和b。事实上，如果你调用 gcd(8, 10) 比在第一个循环 a = 8 和 b = 20.

之前

然后在第一次迭代之后a = 20和b = 8 % 20，所以在第一次迭代之后a = 20和b = 8。下一轮我们计算a = 8和b = 20 % 8，这等于b = 4。然后最后一轮将设置 a = 4 和 b = 8 % 4 所以 b = 0 我们可以停止了。

正如维基百科文章所指定的那样，它的工作原理是：

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.

也就是说，如果a < b 那么gcd(a, b) = gcd(a, b - a).我们可以不断地从 b 中减去 a 直到我们达到 0 和 之间的值b，因此 gcd(a, b) = gcd(a, b mod a)。由于我们知道amodb介于0（含）和[=之间38=]b（不包括），因此我们可以交换两个数以确保两个数中最大的再次排在第一位。我们可以继续这样做，直到最小的达到零。

最大公分母函数没有意义

Greatest Common Denomintor function not making sense

python

algorithm

function

algebra

greatest-common-divisor