2

プロジェクト オイラー演習 (#78)の調査中に 、数を分割するためにベキ級数を作成できることを知りました。その系列から、用語係数を展開して使用して、特定の数を分割する方法の数を取得できます。

そこから、この小さな関数を作成しました。

## I've included two arguments, 'lim' for the number you wish to partition and 'ways' a list of numbers you can use to partition that number 'lim'. ##

def stack(lim,ways):

    ## create a list of length of 'lim' filled with 0's. ##
    posi = [0] * (lim + 1)

    ## allow the posi[0] to be 1 ##
    posi[0] = 1

    ## double loop -- with the amount of 'ways'. ##
    for i in ways:
        for k in range(i, lim + 1):
            posi[k] += posi[k - i]

    ## return the 'lim' numbered from the list which will be the 'lim' coefficient. ##
    return posi[lim] 

>>> stack(100,[1,5,10,25,50,100])
>>> 293
>>> stack(100,range(1,100))
>>> 190569291
>>> stack(10000,range(1,10000))
>>> 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435143L

これは比較的小さなパーティションでは問題なく機能しましたが、この演習ではうまくいきませんでした。おそらく再帰またはより高速なアルゴリズムでこれを高速化する方法はありますか? 五角形の数字を使用するとパーティションにも役立つ方法であるという場所をいくつか読んだことがあります。

この問題で実際の数値を返す必要はありませんが、1000000 で割り切れるかどうかを確認してください。

更新:五角数定理を使用することになりました。Craig Citro が投稿した Hardy-Ramanujan 漸近式を使用しようとしています。

4

1 に答える 1

1

私は最近この事実を個人的に確認していませんが、「最速のパーティションアルゴリズム」のタイトルはSageの実装によってまだ保持されている可能性があります。あなたはそれがドキュメントで言及されているのを見ることができます、あるいはもっと良いのは単にソースコードにスキップすることです。この数を計算する方法の議論を探しているなら、この実装につながる元のスレッドは間違いなく興味深いものです。実装自体のソースファイルは、コードに関するいくつかの有用なコメントで始まります。

于 2012-07-30T05:11:57.880 に答える