时间戳

首页 > 解决方案 > 最大公分母函数没有意义

python - 最大公分母函数没有意义

问题描述

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

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

return a

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

标签： pythonalgorithmfunctionalgebragreatest-common-divisor

解决方案

您在这里指定的是欧几里德方法[wiki]。您的代码中有错字，应该是：

def gcd (a, b):
    while(b != 0):
        t = a
        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我们可以停止。

正如 Wikipedia 文章所指定的，它的工作原理是：

欧几里得算法是基于两个数的最大公约数不变的原理，即如果较大的数被其与较小数的差值代替，则它们的最大公约数不变。

换句话说，这意味着如果a < b然后gcd(a, b) = gcd(a, b - a)。我们可以继续从b中减去a ，直到达到0和b之间的值，因此gcd(a, b) = gcd(a, b mod a)。由于我们知道a mod b介于0（包括）和b（不包括）之间，因此我们可以交换两个数字以确保两者中最大的再次位于第一位。我们可以继续这样做，直到我们为最小的一个达到零。

推荐阅读