最大通用Denomintor函数没有意义

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，但是当我执行print（8％20）时，它吐出8。所以我想念什么？

Answer 1

您在此处指定的是Euclidean method [wiki]。您的代码中有错字，应该是：

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

请注意，在每次迭代中，它都是“ swaps” 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 则gcd（a，b）= gcd（a，b-a）]。我们可以继续从b中减去a，直到达到0和b之间的值，因此gcd（a，b）= gcd（a，b mod a）。因为我们知道a mod b在0（包括）和b（不包括）之间，所以我们可以交换两个数字以确保两个中的最大值再次位于第一位。我们可以继续进行下去，直到最小的零值为止。