Python中如何使用最大公约数（gcd）算法？

Question

我从http://www.s-anand.net/euler.html上获取了一段代码，它与第5个问题相关：

def gcd(a,b): 
    print a,b
    return b and gcd(b, a % b) or a

print gcd(10,20)

输出结果：

10 20

20 10

10 0

10

为什么最后一行只打印出 "a" 而不是 b。

请解释一下上面代码中的 return 语句是如何工作的。

我有点困惑 "and" 和 "or" 运算符。

- Vinod

Answer 1

Python的and和or运算符使用一种称为短路求值的类型，这可能会有点令人困惑。

如果将它们写成函数，它们将像这样工作，除了在需要时它们甚至不会评估右侧的值。

def and(left, right):
    if left:
        return right
    else:
        return left

def or(left, right):
    if left:
        return left
    else:
        return right

因此，这行代码 return b and gcd(b, a % b) or a 可以更详细地写成如下形式：

if b:
    temp_1 = gcd(b, a % b)
else:
    temp_1 = False

if temp_1:
    return temp_1
else:
    return a

如果你理解了这个逻辑，就相当于找到最大公约数的常见方法。然而，除非你已经熟悉Python，否则这段代码很难阅读，因此你可能想避免使用这种风格。

- Jeremy

Answer 2

b and gcd(b, a % b) or a

这是旧的写法：

gcd(b, a % b) if b else a

- Dan D.

---

请注意，语言中添加了a if b else c是因为经常会由于误解/误用b and a or c而导致频繁的错误。如果a是一个假值，它将永远不会被返回。True and "" or "Oops"的结果是"Oops"，而"" if True else "Oops"的结果是""。 - Jeremy

Answer 3

因为在您的情况下，10是最大公约数，例如gcd(10,20)的结果。

您的代码（返回b和gcd(...)或a）与以下代码相同：

def gcd(a,b): 
    print a,b
    if b:
        return b      
    else:
        res = gcd(b, a % b)
        return res if res else a

还要注意，fractions模块中有gcd方法：

from fractions import gcd
print gcd(10,20)

- Artsiom Rudzenka

---

请勿使用“bcoz”。 - c-ram

@C-Ram 但为什么？这样做有什么不好吗？有关于这个的规则吗？你能给我一个链接吗？ - Artsiom Rudzenka

我发现了一个关于拼写和语法的元讨论（接近但不完全相同）。链接。在我看来，用完整的英语回答，而不是文本语言，看起来更好。 - c-ram

@C-Ram - 谢谢。我会看一下的。我同意你的观点，但说实话，在与美国和印度人合作了许多项目之后，我开始使用“bcoz”、“u”等缩写。 - Artsiom Rudzenka