7

私は最大公約数を見つけようとしています。

低い値を1つ減らし、分子と分母の両方を均等に分割するかどうかを確認するために%を使用してチェックする、悪い(操作集約型)アルゴリズムを作成しました。分割すると、プログラムを終了します。ただし、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ビットごとの and 演算子の代わりにキーワードを使用する必要があります&

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

これも同じです:

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

&andandは最初のケースでは同じ結果になりますが、2 番目のケースではそうではないことに注意してください。

orただし、問題は、の代わりに使用したいということですand。また、アルゴリズムは非常に非効率的です。GCD を計算するより良い方法があります。

于 2012-05-26T06:01:58.903 に答える
1

andキーワードを使用します。&ビットごとの and 演算子です。

于 2012-05-26T07:15:43.200 に答える