2

数値を素因数分解するために次のプログラムを作成しました。

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'、戻り値は適切に出力されますが、戻り値の後は常に何も出力されないようです。私は何が欠けていますか？

また、プログラムを改善するにはどうすればよいですか（再帰を引き続き使用します）

4

6 に答える 6

9

完全に再帰的に実行したい場合は、このコードをお勧めします。正しい答えが返され、動作が非常に明確です。プログラムをできるだけ効率的にしたい場合は、以前の方法のいずれかに固執することをお勧めします。

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]
于 2012-10-31T21:46:45.407 に答える
9

あなたの prime_factorize 関数には、再帰的な場合に return ステートメントがありません。最後の行で "return prime_factorize(x/i,li)" を呼び出したいとします。素数で試して (再帰呼び出しが不要になるように)、その場合に機能することを確認してください。

また、おそらく次のような署名を作成する必要があります。

def prime_factorize(x,li=None):
    if li is None: li = []

そうしないと、2 回以上呼び出したときに間違った結果が得られます。

>>> prime_factorize(10)
[2, 5]
>>> prime_factorize(4)
[2, 5, 2, 2]
>>> prime_factorize(19)
[2, 5, 2, 2, 19]
于 2009-09-12T08:05:27.873 に答える
3

@Anthony's は、 に関する最初の質問に正しく答えました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 自体は末尾再帰の最適化を行わないため、手動で行うことを学ぶことが重要です。

「[非基本ケース] 再帰ステップ'return thisfun(newargs)'を変更しargs=newargs; continueて、本体全体をループに入れるwhile True:」が、末尾再帰最適化の基本的な考え方です。ここでも、 li を非引数にし (引数にする理由はありません)、 に条件を付けwhile、 を回避しましcontinueた。これは、とにかく再帰ステップが本体の最後にあったためです。

この定式化は、さらなる最適化リファクタリング (sqrt 回避、メモ化など) を適用してパフォーマンスを向上させるための優れた基礎となります。

于 2009-09-12T15:04:33.020 に答える
2

より機能的なスタイルのバージョン。

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
于 2009-09-12T13:59:57.537 に答える
0 
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

いいですか。

于 2011-08-09T06:24:34.077 に答える