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

Question

在 "Great Mathematical problems -- Vision of infinity" 中，伊恩·斯图尔特第 18 页提到了 Euclid 的命题 2，《元素》第七册，这是一种非常基本的求最大公约数的方法。我引用"It works by repeatedly subtracting the smaller number from the larger one, then applying a similar process to the resulting remainder and the smaller number, and continuing until there is no remainder."例子是630和135。135从630（495,360,225）重复"subtracted"最后得到90小于135。所以数字倒过来，90是反复从 135 中减去最终得到 45。然后从 90 中减去 45，最后得到 0，得到 45 gcd。这有时被称为寻找 gcd 的欧几里德算法。

为了教一个初学者（10 个 child），我需要在 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

事实上，在python中，您只需直接使用fractions模块提供的gcd函数即可。

如果您希望这样的函数处理多个值，您只需使用 reduce:

reduce(gcd,your_array)

现在，您似乎想限制自己只使用循环+减法，因此处理 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

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

Euclidean Algorithm (subtraction) in python

python

algorithm

subtraction

greatest-common-divisor