python中的欧几里德算法（减法）

Question

在“伟大的数学问题 - 无限远景”，第18页Ian Stewart提到了Euclid的命题2，Element VII的命题7，它是寻找最大公约数的一个非常基本的方法。我引用“它的工作原理是反复从较大的数字中减去较小的数字，然后对所得的余数和较小的数字应用类似的处理，并继续直到没有余数。”这个例子是630和135. 135从630（495,360,225）中被“减去”，最后得到90，它小于135.所以数字反转，并且从135中重复减去90，最后得到45然后从90中减去45，最后得到0得到45的gcd。这有时被称为寻找gcd的欧几里德算法。

要教一个初学者（10岁的孩子）我需要在python中编写代码。不应该有任何函数定义，也不应该使用除减法之外的任何其他数学运算。我想用if/while/else/elif/continue/break。应该规定，如果给出三个（或更多）数字，整个程序必须重复决定较小的一个。 从这个角度来看，gcd上的早期链并不看这个算法。

Answer 1

一个典型的快速解决GCD算法将是一些反复的版本像这样的：

def gcd(x, y): 
    while y != 0: 
     (x, y) = (y, x % y) 

    return x 

事实上，在蟒蛇你只是直接使用分数模块提供的GCD功能。

如果你想这样的功能来处理你只是使用减少多个值：

reduce(gcd,your_array) 

现在看来要约束自己只使用循环+ substractions这样一个可能的解决方案来处理与X，Y正整数会是这样：

def gcd_unopt(x, y): 
    print x,y 

    while x!=y: 
     while x>y: 
      x -= y 
      print x,y 
     while y>x: 
      y -= x 
      print x,y 

    return x 

print reduce(gcd_unopt,[630,135]) 

不知道为什么你要避免使用功能，GCD是定义一个函数，即便如此，那很简单，刚刚摆脱函数声明和使用参数作为全局变量，例如：

x = 630 
y = 135 

print x,y 

while x!=y: 
    while x>y: 
     x -= y 
     print x,y 
    while y>x: 
     y -= x 
     print x,y