数値を素因数分解するPython再帰プログラム
-
06-07-2019 - |
質問
数値を素因数分解するために次のプログラムを作成しました:
import math
def prime_factorize(x,li=[]):
until = int(math.sqrt(x))+1
for i in xrange(2,until):
if not x%i:
li.append(i)
break
else: #This else belongs to for
li.append(x)
print li #First print statement; This is what is returned
return li
prime_factorize(x/i,li)
if __name__=='__main__':
print prime_factorize(300) #Second print statement, WTF. why is this None
次の出力が得られます:
[2, 2, 3, 5, 5]
None
Altho '、戻り値は適切に出力されますが、戻り値の後は常に何も出力しないようです。何が足りないのですか?
また、どうすればプログラムを改善できますか(再帰を使い続ける)
解決
prime_factorize関数には再帰的なケースではreturnステートメントがありません-" return prime_factorize(x / i、li)"最後の行に。素数で試してみて(したがって、再帰呼び出しは不要です)、その場合に機能することを確認してください。
また、署名を次のようにすることもできます。
def prime_factorize(x,li=None):
if li is None: li = []
それ以外の場合、複数回呼び出すと間違った結果が得られます:
>>> prime_factorize(10)
[2, 5]
>>> prime_factorize(4)
[2, 5, 2, 2]
>>> prime_factorize(19)
[2, 5, 2, 2, 19]
他のヒント
完全に再帰的に実行したい場合は、このコードをお勧めします。正しい答えが返され、動作方法はかなり明確です。 プログラムを可能な限り効率的にしたい場合は、以前の方法のいずれかに固執することをお勧めします。
def primeFact (i, f):
if i < f:
return []
if i % f == 0:
return [f] + primeFact (i / f, 2)
return primeFact (i, f + 1)
これは問題を解決する完全に再帰的な方法です
>>> primeFact (300, 2)
[2, 2, 3, 5, 5]
>>> primeFact (17, 2)
[17]
>>> primeFact (2310, 2)
[2, 3, 5, 7, 11]
@Anthonyは、 print
に関する元の質問に正しく回答しました。ただし、同様に提供されたいくつかのヒントの精神で、テール再帰除去を使用した簡単なリファクタリングを次に示します。
def prime_factorize(x):
li = []
while x >= 2:
until = int(math.sqrt(x))+1
for i in xrange(2,until):
if not x%i:
li.append(i)
break
else:
li.append(x)
return li
x //= i
これは重大なパフォーマンスの問題に対処しません(big-Oの動作は元のソリューションと同じです)-しかし、Python自体は末尾再帰の最適化を行わないため、手動で行うことを学ぶことが重要です。
&quot; [非ベースケース]再帰ステップ 'return thisfun(newargs)'
を args = newargs;に変更します。続行
して、本文全体を while True:
ループ&quot;に入れます。末尾再帰最適化の基本的な考え方です。ここでは、liを非引数(引数である理由はありません)にし、 while
に条件を付け、再帰的であるため continue
を回避しましたとにかくステップは体の終わりにありました。
この定式化は、より最適化されたリファクタリング(sqrt回避、メモ化、...)を適用してパフォーマンスを向上させるための優れた基盤となります。
より機能的なスタイルのバージョン。
def prime_factorize( number ):
def recurse( factors, x, n ):
if x<2: return factors # 0,1 dont have prime factors
if n > 1+x**0.5: # reached the upper limit
factors.append( x ) # the only prime left is x itself
return factors
if x%n==0: # x is a factor
factors.append( n )
return recurse( factors, x/n, n )
else:
return recurse( factors, x, n+1 )
return recurse( [], number, 2)
for num, factors in ((n, prime_factorize( n )) for n in range(1,50000)):
assert (num==reduce(lambda x,y:x*y, factors, 1)), (num, factors)
#print num, ":", factors
def primeFactorization(n):
""" Return the prime factors of the given number. """
factors = []
lastresult = n
while 1:
if lastresult == 1:
break
c = 2
while 1:
if lastresult % c == 0:
break
c += 1
factors.append(c)
lastresult /= c
return factors
それは問題ありません。