7

我试图找到最大的公因数。

我写了一个糟糕的（操作密集型）算法，将较低的值减一，使用 % 检查它是否将分子和分母均分，如果是，则退出程序。但是，我的 while 循环没有使用 and 运算符，因此一旦分子可整除，它就会停止，即使它不是正确的答案。

我使用的数字是 54 和 42，正确的 GCD（最大公分母）是 6。

#heres a simple algorithm to find the greatest common denominator: 

iterations = 0; #used to calculate number of times while loop is executed

u = 54; v= 42; d = v-1; #u is the numerator, v is the denominator, d is the number decremented by one 

while ((v % d !=0) & (u % d != 0)): #while both numerator AND denominator cannot be evenly divided by the decremented number
 d -= 1 #decrement the number by one
 print d #print the number decremented
 iterations +=1 #add 1 to the count of iterations in while loop

print "the gcd is " +str(d) #should be 6 when the number can evenly divide both
print "the number of iterations was " +str(iterations) #display times it took algorithm to complete

我得到的答案是 27，它告诉我一旦达到 27 并且可以平均划分 54/27，它就会停止。关于如何在python的while循环中使用and运算符有什么想法吗？

谢谢！

4

2 回答 2

21

您应该使用关键字and而不是按位和运算符&：

while (v % d != 0) and (u % d != 0):

这也是一样的：

while (v % d) and (u % d):

请注意，&andand在第一种情况下会给出相同的结果，但在第二种情况下不会。

你的问题是你想使用or而不是and. 此外，您的算法效率极低。有更好的方法来计算 GCD。

于 2012-05-26T06:01:58.903 回答
1

使用and关键字。&是位与运算符。

于 2012-05-26T07:15:43.200 回答