pythonはどのように2つの最大公約数を解決しますか?
タイトル:
二つの自然数を与えて、この二つの数の最大公約数を求めます。
分析:
テーマだけを見ると、とても簡単です。自然数を循環して、二つの自然数を割ることができれば、この数を記録して、これらの記録の中で一番大きなものを見つけます。
しかし、このようにするといくつかの欠点があります。一つは割り算をする量が多いこと、もう一つは自然数を遍歴する必要がないことです。また、循環できるなら、再帰しないほうがいいです。Pythonの関数が再帰的に最大スタック空間は1000ですから、数字が大きいと、爆発が起きやすいです。
ここでは二つの処理方法があります。
1、大きな自然数がより小さい自然数を除いて、剰余を取得すれば、より小さい自然数と剰余の最大公約数は私達が要求する値です。
2、大きな自然数から小さい自然数を減らせば、差を取り、小さい自然数と差の最大公約数は私たちが要求する値です。
以上の2つに基づいて、定義に基づいて得られたアルゴリズムをもとに改善することができます。減算操作はもちろん余裕よりも多く便利です。また、コンピュータではビット演算の速度が加減乗除よりも速いので、4つのアルゴリズムを書きました。doc_にコメントがあります
コード:
二つの自然数を与えて、この二つの数の最大公約数を求めます。
分析:
テーマだけを見ると、とても簡単です。自然数を循環して、二つの自然数を割ることができれば、この数を記録して、これらの記録の中で一番大きなものを見つけます。
しかし、このようにするといくつかの欠点があります。一つは割り算をする量が多いこと、もう一つは自然数を遍歴する必要がないことです。また、循環できるなら、再帰しないほうがいいです。Pythonの関数が再帰的に最大スタック空間は1000ですから、数字が大きいと、爆発が起きやすいです。
ここでは二つの処理方法があります。
1、大きな自然数がより小さい自然数を除いて、剰余を取得すれば、より小さい自然数と剰余の最大公約数は私達が要求する値です。
2、大きな自然数から小さい自然数を減らせば、差を取り、小さい自然数と差の最大公約数は私たちが要求する値です。
以上の2つに基づいて、定義に基づいて得られたアルゴリズムをもとに改善することができます。減算操作はもちろん余裕よりも多く便利です。また、コンピュータではビット演算の速度が加減乗除よりも速いので、4つのアルゴリズムを書きました。doc_にコメントがあります
コード:
def greatest_common_divisor_1(self, num1, num2):
'''
, , , o(min(num1,num2)),
'''
gbc = 1
for i in xrange(2, min(num1, num2)+1):
if num2 % i == 0 and num1 % i == 0:
gbc = i
return gbc
def greatest_common_divisor_2(self, num1, num2):
'''
, o(min(num1,num2)), 。
'''
while num1 != num2:
if num1 > num2:
num1 = num1 - num2
else:
num2 = num2 - num1
return num1
def greatest_common_divisor_3(self, num1, num2):
'''
, , o(log max(num1, num2))
'''
while num1 != num2:
if num1 > num2:
if num1 % num2 == 0:
return num2
num1 = num1 % num2
else:
if num2 % num1 == 0:
return num1
num2 = num2 % num1
return num1
def greatest_common_divisor(self, num1, num2):
'''
, , , o(log max(num1,num2))
, 、 ,
a = 999999342353200
b = 777774234
print greatest_common_divisor(a, b)
'''
factor = 1
if num1 < num2:
return greatest_common_divisor_1(num2, num1)
while num1 != num2:
if num1 & 1 is False and num2 & 1 is False: #
num1 = num1 >> 1
num2 = num2 >> 2
factor *= 2
elif num1 & 1 is False and num2 & 1 is True:
num1 = num1 >> 1
elif num1 & 1 is True and num2 & 1 is False:
num2 = num2 >> 1
else:
if num1 > num2:
num1 = num1 - num2
else:
num2 = num2 - num1
return factor*num1
以上が本文の全部です。皆さんの勉強に役に立つように、私たちを応援してください。