与えられた数nについて、2と言うと、2未満の数を使用して合計2を取得する方法はいくつありますか。
1+1 = 2
so, for 2 - just 1 way.
n = 3
1+1+1=3
1+2=3
so,for 3 - it is 2 ways
n = 4
1+1+1+1=4
1+1+2=4
1+3=4
2+2=4
so, for 4 - it is 4 ways
この質問に対する一般的なパターン/解決策はありますか？
5960 次
1 に答える
12
この問題はPartition Problemとして知られています。wiki からの参照リンクで詳細を参照してください。
分割関数のハンドルを取得する 1 つの方法には、少なくとも k と同じ大きさの自然数のみを使用して n の分割数を表す中間関数 p(k, n) が含まれます。k の任意の値について、p(k, n) によってカウントされるパーティションは、次のカテゴリのいずれかに正確に適合します。
smallest addend is k smallest addend is strictly greater than k.最初の条件を満たすパーティションの数は p(k, n − k) です。これを確認するには、数 n − k のすべてのパーティションを少なくとも k のサイズの数に分割したリストを想像してください。次に、リスト内の各パーティションに「+ k」を追加することを想像してください。今それは何のリストですか？補足として、これを使用して、中間関数に関して分割関数の一種の再帰関係を定義できます。つまり、
1+ sum{k=1 to floor (1/2)n} p(k,n-k) = p(n),正確に k の部分を含まない少なくとも k の部分への分割は、すべての部分が少なくとも k + 1 でなければならないため、2 番目の条件を満たす分割の数は p(k + 1, n) です。
2 つの条件は相互に排他的であるため、いずれかの条件を満たすパーティションの数は p(k + 1, n) + p(k, n − k) です。したがって、再帰的に定義された関数は次のようになります。
p(k, n) = 0 if k > n p(k, n) = 1 if k = n p(k, n) = p(k+1, n) + p(k, n − k) otherwise.
実際、 memoizationによってすべての値を計算して、余分な再帰呼び出しを防ぐことができます。
編集: unutbu がコメントで述べたように、計算の最後に 1 を引いて結果を出力する必要があります。つまり、最後のステップまでのすべてのP値は、ウィキが示唆するように計算する必要がありますが、結果を出力する前の最後の最後に、 で減算する必要があります1。
于 2011-11-19T10:49:42.350 に答える