我有一個作業(作業)如下：

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

2-)絕對不需要檢查> b并且也不需要檢查輸入是否為正,因為我使用了abs()

TA沒有誤導作業嗎？還是我錯了？

最佳答案 雖然你實現的確實是一個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.雖然這沒有錯,但肯定不是Euler的算法(雖然它很接近).

歐拉的算法確實：

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

因為Euclid的算法使用模數運算符,所以它會經歷更少的步驟,而實際上計算的算法與算法相同.結果,它更有效率.

這是Euclid算法的一個實現：

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