python - 寻找最大公约数(作业打错了，我迫切需要你的帮助)

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

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

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

TA 没有给作业打错分吗？还是我错了？

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。虽然这没有错，但它肯定不是欧拉算法(虽然很接近)。

欧拉算法可以:

if the smaller number perfectly divides the larger
    return the smaller number as the GCD
else
    return the GCD of 
        1. the remainder from dividing the bigger number by the smaller
        2. the smaller number

因为欧几里德算法使用模数运算符，它的步骤要少得多，而实际上计算的内容与您的算法相同。因此，它的效率更高。

这是欧几里得算法的一个实现:

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