寻找最大公约数（作业评分错误，我急需你的帮助）

Question

我的作业如下：

Write a program which enters two positive integers a and b from the keyboard. Also write a recursive function for determining the gcd (greatest common divisor) of a and b using Euclid’s algorithm. According to this algorithm if the first number is divisible by the second one then thesecond one is the gcd. If this is not the case then the gcd of the second number and the remainder of a=b has to be determined. The result should be printed on the screen outside of the function.

我的解决方案是：

a=int(input("Enter the first number: "))
b=int(input("Enter the second number: "))

def GCDfinder(m,n):
    z=abs(m-n)
    if (m-n)==0:
        return n
    else:
        return GCDfinder(z,min(m,n))

print (GCDfinder(a,b))

我得到了50%的答案。我想给这个评分的老师助理不知道她在做什么。她的评论如下：

That is not the method described in the assignment. You should first check if a%b==0 then return b. Or return gcd(b, a%b) Also check that the input is positive and a>b

我使用的方法是基于欧几里得定理。 http://en.wikipedia.org/wiki/Euclidean_algorithm

2-）绝对不需要检查a>；b，也不需要检查输入是否为正，因为我使用了abs（）

他没有把作业评分错误吗？还是我错了？在

Answer 1

虽然您所实现的确实是一个GCD查找器，但它不是Euclid的算法

这就是你所做的：

if the two numbers are equal
    return either one as the GCD
else
    return the GCD of the absolute difference between them and the smaller number

你的算法通过重复减法找到GCD。虽然这并没有错，但它肯定不是欧拉的算法（虽然它很接近）。在

欧拉算法可以：

^{pr2}$

因为欧几里德的算法使用模运算符，所以它所需的步骤要少得多，而事实上，计算的步骤与算法相同。因此，它的效率更高。在

以下是欧几里得算法的实现：

def GCDfinder(a,b):
    while b != 0:
        a,b = b, a%b
    return a

>>> GCDfinder(12,20)
4
>>> GCDfinder(17,20)
1
>>> GCDfinder(3,4)
1

Answer 2

以下是欧几里德算法的递归实现：

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

它基于http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations中的伪代码

Answer 3

我真的认为你和TA都是对的。不过，因为他/她是助教，所以他说得对一点。；）

让我解释一下：

你是对的，因为你完全成功地编写了一个确定GCD的程序。 然而，助教是对的，因为你没有遵循作业的步骤，这在本例中是领先的。在

比较： 你得到50%这一事实意味着，尽管你解决了这个问题（找到了GCD），但你没有遵守规则。把它比作寻宝游戏。要完成它，您必须按照说明中的所有步骤操作。然而，你在这里所做的就相当于无意中听到有人在谈论终点线的位置，然后直接前往终点线，而没有从计划中的挑战/谜题中学到任何东西