3

我正在 MIT 6.00 学习 Python 并堆叠制作递归代码。我唯一想做的就是从x中迭代减去1，但不知道该怎么做..

这是我的代码

def gcdIter(a, b):
    '''
    a, b: positive integers

    returns: a positive integer, the greatest common divisor of a & b.
    '''
    # Your code here
    x = min(a, b)
    if max(a, b) % min(a, b) == 0: 
        return x
    else:
        return #What comes to iterate -1 from x

请帮忙 ！！！

4

3 回答 3

6

你的代码过于复杂，试试这个改编自维基百科的递归实现：

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

您似乎在寻找迭代解决方案（这个问题具有误导性）。如果是这样的话，这里有几个可能的实现，也改编自维基百科：

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

def gcd(a, b):
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
    return a
于 2013-06-15T01:22:49.437 回答
0

一个简单的解决方案是这样的

def gcd(a, b):
    #find the gcd of a,b,None if not found
    miner = min(a, b)
    gcd = None
    for i in xrange(1, miner+1):
        if(a % i == 0 and b % i == 0):
            gcd = i
    return gcd

现在如果 a > b，你可以从谷歌得到这个 gcd(a,b) = gcd(a%b,b) 你可以用一个 while 循环来提高函数的性能，你可以试试

于 2013-06-15T02:05:16.387 回答
0

你们真是太棒了！！！！感谢所有的答案。事实证明，我需要使用负 1 的 While 循环，直到 min(a, b) 到达 gcd。

尽管您的答案看起来要简单得多，但此问题集的答案如下

def gcdIter(a, b):
    '''
    a, b: positive integers

    returns: a positive integer, the greatest common divisor of a & b.
    '''
    x = min(a, b)

    # Keep looping until testValue divides both a & b evenly
    while a % x != 0 or b % x != 0:
        x -= 1

    return x

再次感谢大家！！！

于 2013-06-15T05:48:50.900 回答