Python程序来计算GCD

def gcd(a,b):
    if (a>b):
        r1=a
        r2=b
    else:
        r1=b
        r2=a   
    if(r1%r2==0):
        print (r2)
    else:
        gcd(r2, r1%r2)
a= int(input("Enter a number"))
b= int(input("Enter a number"))
gcd(a,b)

该代码用于查找两个数字的最大公约数。
还有更好的方法吗？
我该如何改善代码？

“有更好的方法吗？”根据“更好”的一些定义：从数学导入gcd

#1 楼

错误：

当我输入-6和-3时，我期望结果为3，但我却得到了RecursionError异常：

RecursionError: maximum recursion depth exceeded in comparison

对于UX：

在显示的文本和要输入的数据之间留一些空间：

Enter a number6
Enter a number5

这将是更好的最低选择：

Enter a number: 6
Enter a number: 5

您知道程序的作用，但不是用户，因此您的消息必须清晰准确。要求用户不要输入数字，而是输入整数。否则，这可能会误导用户输入实数，或错误输入字符（甚至尝试破解您的软件）：

Traceback (most recent call last):
  File "cr.py", line 12, in <module>
    a= int(input("Enter a number"))
ValueError: invalid literal for int() with base 10: 'g'

您的程序没有给用户一个退出的选择。为此目的，您可以做的最少就是处理与用户按下Ctrl + c相对应的KeyboardInterrupt异常。消息旨在与用户通信，因此请让他知道程序的作用：

print('Computing the GCD of two numbers.\n')

分而治之：

这是上述情况的结果：是时候实现一个功能，该功能的唯一目的是关心用户的输入：

def read_an_integer_user_input():
    a = None   
    while type(a) != int:
        try:
            a = int(input('Enter an integer: '))
        except ValueError:
            print('I expect an integer value. Try again.')
        except KeyboardInterrupt:
            print('\nGoodbye!')
            break
    return a

不打印，返回：

我们希望计算结果的函数返回结果而不是将其打印出来。这不仅是本质上的函数定义，而且通过这种方式，您可以为代码的重用和正确使用提供更多的机会。所以我不用写print(r2)而是写return r2;顺便说一下，不要在print和(之间留空格。

鉴于先前提到的递归错误，我会选择一个迭代实现您的代码：

def compute_gcd(a,b):
    a = abs(a)
    b = abs(b)
    while b:
        a, b = b, a%b
    return a

完整程序：

让我们收集上面的内容以构建一个小的连贯程序：

def compute_gcd(a,b):
    a = abs(a)
    b = abs(b)
    while b:
        a, b = b, a%b
    return a

def read_an_integer_user_input():
   a = None   
   while type(a) != int:
       try:
           a = int(input('Enter an integer: '))
       except ValueError:
           print('I expect an integer value. Try again.')
       except KeyboardInterrupt:
           print('\nGoodbye!')
           break
   return a

if __name__ == '__main__':
    print('Computing the GCD of two numbers.')
    a = read_an_integer_user_input()
    b = read_an_integer_user_input()
    if a and b:       
       print('The GCD of {} and {} is: {}'.format(a, b, compute_gcd(a, b)))

\ $ \ begingroup \ $
我喜欢这个答案，只是很少使用类型。您不能在True时使用：试试：返回int（…）…代替吗？
\ $ \ endgroup \ $
–301_Moved_Permanently
18年5月9日在7:30

\ $ \ begingroup \ $
你说对了，你的方法更好。留下您的评论，以便OP可以进行比较并找出始终有待改进的地方。
\ $ \ endgroup \ $
– Billal Begueradj
18年5月9日在7:37

\ $ \ begingroup \ $
“鉴于先前提到的递归错误，我会选择对您的代码进行迭代实现”-这句话没有道理。您的迭代代码可以修复递归版本中的错误，但是正确的递归代码也可以。您还可以编写一个有问题的迭代实现。
\ $ \ endgroup \ $
–康拉德·鲁道夫（Konrad Rudolph）
18年5月9日在10:57

\ $ \ begingroup \ $
我同意您的看法，但：1.如前所述，递归版本中的大量数字可能会导致其他严重的错误。 2. OP表示他愿意接受其他方法@KonradRudolph
\ $ \ endgroup \ $
– Billal Begueradj
18年5月9日在11:08

\ $ \ begingroup \ $
您只需要在末尾取绝对值：def compute_gcd（a，b）：\ n而b：\ n a，b = b，a％b \ n返回abs（a）
\ $ \ endgroup \ $
– 12Me21
18年5月9日在13:50

#2 楼

Python有一个官方的样式指南，PEP8。它建议（除其他事项外）以下内容：

在运算符周围使用空格（因此a = input(...)）。不要使用不必要的括号（if，for，while等）不需要）

除此之外，还应该使函数返回结果而不是打印。否则，您将无法在进一步的计算中使用它：

g = gcd(10, 15)
# 5
print(g)
# None
g + 1
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

使用这些，我会将您的代码更改为：

def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    return gcd(b, a % b)

通常，我会指出这种方法具有Python所有递归解决方案的固有问题，即堆栈限制（默认为1000）。但是，由于始终在递归中继续使用a % b，因此即使对于较大的互质数，此函数也可以使用：

gcd(16956998685025525617332092680088906859010597516989049974644188276809460728386128015966080402491132114558031760245789600047216269236212122151725198496639367,
    130219041176878297644835828972023265387463111246248427493495319607240172982284)
# 1

最后，对于替代方法，还有内置gcd模块中已经存在一个math函数（自Python 3.5起）。由于它是用C语言实现的，因此它比仅在Python中完全运行的此函数要快一些：

In [5]: a = 16956998685025525617332092680088906859010597516989049974644188276809460728386128015966080402491132114558031760245789600047216269236212122151725198496639367 In [6]: b = 130219041176878297644835828972023265387463111246248427493495319607240172982284 In [7]: %timeit gcd(a, b) 57.1 µs ± 590 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) In [8]: %timeit math_gcd(a, b) 2.99 µs ± 6.66 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

@BillalBEGUERADJ时钟提供的答案中的迭代函数在两者之间的中间位置：

In [14]: %timeit compute_gcd(a, b) 17.9 µs ± 316 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

评论
\ $ \ begingroup \ $
在3.5之前的版本中，存在fractions.gcd。
\ $ \ endgroup \ $
–加雷斯·里斯（Gareth Rees）
18年5月9日在6:33
\ $ \ begingroup \ $
@Graipher您可以通过分配“ a％b”的结果而不是重新计算它来将gcd函数的速度提高20％或更多（不尝试）。
\ $ \ endgroup \ $
–肯乔格
18年5月9日在7:30
\ $ \ begingroup \ $
@Konchog是的，可以减少约10％。但是由于迭代方法和内置方法都较快，因此使其难于阅读可能不值得。
\ $ \ endgroup \ $
–地狱
18年5月9日在7:32
\ $ \ begingroup \ $
@Gaipher，当然内置的速度更快-但这不是很多代码审查！如果我们要使用递归，那么您的答案很好-但是通过在最后一行使用例如“ return c == 0？b：gcd（b，c）”，代码在名义上更有效并且可读性强。
\ $ \ endgroup \ $
–肯乔格
18年5月9日在8:04

#3 楼

如果您想知道是否有比Euclid算法更有效的算法，这可能是错误的地方。甚至维基百科都是一个更好的起点。答案是肯定的，但是它们要复杂得多。凭直觉，我会忽略Stein的Python算法（在该页面上称为“二进制GCD算法”），因为它依赖于Python确实不擅长的低级技巧，例如移位。 Euclid的算法可能很好。

关于欧几里得算法的实现

您无需手动检查a和b中哪个更大。如果它们的处理方式不正确，则第一个%操作将为您交换它们。
您应该让函数返回一个值而不是打印一个值。可以从外面调用打印。
您应该考虑如何处理负数。按照本文所述，GCD为负（-5和10）。它将崩溃（5和-10）。正确的答案可能是5。

#4 楼

让我们回到基础上待一会儿。

欧几里得算法的定义是什么？

首先，该算法仅包含一个前提条件：

数字必须为正。

没有提及a和b的顺序，从而使函数的前六行多余：

def gcd(r1, r2): if r1 % r2 == 0: print(r2) else: gcd(r2, r1 % r2)

（我还按照前面提到的PEP8格式化了代码。）

接下来，算法的停止条件不是r1 % r2 == 0。它是：

余数rN必须最终等于零，此时算法停止

，因此我们只需要测试r2 == 0，为我们节省了一次计算：

def gcd(r1, r2): if r2 == 0: print(r1) else: gcd(r2, r1 % r2)

就目前而言，这是我们要采用的算法。现在，进行一些更一般的说明：

函数应该计算结果或处理I / O。永远不要都。因此，请改为返回GCD：

def gcd(r1, r2): if r2 == 0: return r1 else: return gcd(r2, r1 % r2)

此函数由一个带有两个return语句的测试组成。习惯将这样的语句重写为具有条件值的单个return语句：

def gcd(r1, r2): return r1 if r2 == 0 else gcd(r2, r1 % r2)

这后两种形式大体等效。有些人（包括我在内）发现第二版更具可读性，但是在Python中，由于Python的语法，我看到有人可能会不同意：其他语言编写if a then b else c或a ? b : c；相反，Python会迫使您编写b if a else c；什么？！

现在，尽管此算法的递归形式是惯用且优雅的，但确实这不是pythonic：Python（主要是由于其主要开发人员的心血来潮而不是技术原因）避开了递归支持迭代。

幸运的是，在这种情况下，迭代形式同样优雅且相对简单：它取决于以下认识：递归算法会逐步将余数的值与该系列中的下一个余数交换（尽管现在变量名更具误导性：我们应该确实使用rN和rN + 1：

def gcd(r1, r2): while r2 != 0: r1, r2 = r2, r1 % r2 return r1

奖金：请注意，上述所有实现都暗含前提条件：它们产生的结果为负幸运的是，我们可以轻松地扩展实现以处理负面的输入，好消息是：我们不需要以任何方式修改输入，我们只需要使输出为正即可：

def gcd(r1, r2): while r2 != 0: r1, r2 = r2, r1 % r2 return abs(r1)

当然，递归形式也同样适用：

def gcd(r1, r2): return abs(r1) if r2 == 0 else gcd(r2, r1 % r2)

评论
\ $ \ begingroup \ $
如果您希望gcd始终为非负数（这绝不是通用约定），那么您需要在某个地方添加绝对值。（编辑：对不起，我刚刚注意到这是在您的最后两个版本中完成的。）否则，我感谢您提出这些优雅的简化；在阅读详细的样式指南时，我感到发痒，而这些指南却忽略了算法过于复杂的情况！
\ $ \ endgroup \ $
– Lspice
18年5月10日在0:59

\ $ \ begingroup \ $
bool（r2！= 0）<=> bool（r2）
\ $ \ endgroup \ $
–301_Moved_Permanently
18年5月10日在16:38
\ $ \ begingroup \ $
@MathiasEttinger请不要。明确说明您的意思：我们不想将值转换为bool。我们要比较一个零值。实际上，对转化表示怀疑是一项很好的一般政策。请注意，比较不需要转换，而将bool放在周围则没有任何效果。
\ $ \ endgroup \ $
–康拉德·鲁道夫（Konrad Rudolph）
18年5月10日在17:26

\ $ \ begingroup \ $
@KonradRudolph我使用bool表示两个表达式在布尔上下文（您的ifs和whiles）中是等效的，而不在代码中使用它。关键是r2可以是任何东西，如果馈入了错误的对象，最好让代码在相关的数学运算中失败，而不是（任意）比较。
\ $ \ endgroup \ $
–301_Moved_Permanently
18年5月10日在17:41
\ $ \ begingroup \ $
@MathiasEttinger足够公平，但我仍然不同意。真实值在某些方面很有用，但是它们总是以明确性为代价，在这种情况下，我想（并且我声称，任何程序员都应该）明确在这里执行什么数学运算。就我的代码而言，我不是在看真实值，而是在对整数的特定值进行运算。真实性测试碰巧会在这里产生正确的结果，这纯属偶然。
\ $ \ endgroup \ $
–康拉德·鲁道夫（Konrad Rudolph）
18年5月10日在17:54

#5 楼

您的实现是递归的，这意味着对于需要较大深度的数字，您可能会得到堆栈溢出。由于该算法是尾部递归，因此您可以将其转换为循环，而不会遇到此问题。

评论
\ $ \ begingroup \ $
如其他答案所示，这纯粹是理论上的问题。
\ $ \ endgroup \ $
–康拉德·鲁道夫（Konrad Rudolph）
18年5月9日在11:04
\ $ \ begingroup \ $
虽然这可能是一个理论上的问题（例如在“对于小n，一切都是O（1）”中），但我们在这里对代码进行审查以使其比以前更好，因此指出这些问题也很有用。 OP不需要对此进行更改，但是他们可以考虑此问题。
\ $ \ endgroup \ $
– allo
18年5月10日在11:38

#6 楼

堆栈溢出并不是纯粹的理论问题；我是能够使一个用：

70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

和

113796925398360272257523782552224175572745930353730513145086634176691092536145985470146129334641866902783673042322088625863396052888690096969577173696370562180400527049497109023054114771394568040040412172632376

（连续斐波那契数）<无线电通信/>
评论
\ $ \ begingroup \ $
它在Python 3中对我有效。
\ $ \ endgroup \ $
–康拉德·鲁道夫（Konrad Rudolph）
18年5月9日在16:41

#7 楼

#--input
a = int(input("Enter a number: "))
print() # new line
b = int(input("Enter a number: "))
print() # new line

#--check/make a > b only once
if (b > a):
    a,b = b,a

#--one simple loop for GCD 
while(a%b != 0):
    x,a = a,b
    b = x%b

#--If one or both values are negative
if(b < 0):
    b *= -1

print ("GCD = ", b)

尝试一下。对于GCD，它有一个小循环。和-ve值校正。我添加了注释来描述代码。

评论
\ $ \ begingroup \ $
欢迎使用代码审查！您提出了一种替代解决方案，但尚未查看代码。请说明您的推理（您的解决方案如何工作以及为什么它比原始解决方案更好），以便作者和其他读者可以从您的思考过程中学习。
\ $ \ endgroup \ $
–Vogel612♦
18年5月10日在9:21
\ $ \ begingroup \ $
除了是一个可怕的答案，这还是可怕的代码1）问题被标记为python-3.x，因此请检查您的打印件2）检查您的缩进，这不是有效的Python 3）交换值应为1 -liner得益于tupple拆包4）比较周围的括号是不必要的混乱5）操作符之间的间距保持一致（并阅读PEP8）6）使用更好的，描述性的变量名称7）您删除了原始代码：函数定义
\ $ \ endgroup \ $
–301_Moved_Permanently
18年5月11日在18:02
\ $ \ begingroup \ $
您仍然不会以任何方式引用问题中的代码：否决。
\ $ \ endgroup \ $
–灰胡子
18年5月21日在8:41
\ $ \ begingroup \ $
@MathiasEttinger，缩进有什么问题？
\ $ \ endgroup \ $
–安东·舍伍德（Anton Sherwood）
18年6月18日在19:24
\ $ \ begingroup \ $
自评论以来，@ AntonSherwood帖子已被编辑，这一点已得到解决。
\ $ \ endgroup \ $
–301_Moved_Permanently
18年6月18日在19:28

编程黑洞网