24

合計数（コード内の変数n ）の組み合わせの数を検索します。例：

3 = 1 + 1 + 1 = 2 + 1 = 3=>ANSは3

5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1=>ANSは7

次の例では、mは最大数であり、n合計です。目的は、mがいくつの（合計）組み合わせを持っているかを見つけることです。

なぜそうするのか知りたいだけですp(n, m) = p(n, m - 1) + p(n - m, m)か？

ここのコード：

int p (int n, int m)
{
    if (n == m)
        return 1 + p(n, m - 1);
    if (m == 0 || n < 0)
        return 0;
    if (n == 0 || m == 1)
        return 1;

    return p(n, m - 1) + p(n - m, m);

}

感謝！

4

4 に答える 4

26

n以下の数値を追加して、結果を得るすべての方法を検討してくださいm。あなたが言ったように、私たちはこれを呼びますp(n,m)。たとえば、p（7,3）= 8は、以下に示すように3未満の数値から7を作成する8つの方法があるためです:(簡単にするために、常に大きいものから小さいものの順に数値を追加すると仮定できます）

  • 3 + 3 + 1
  • 3 + 2 + 2
  • 3 + 2 + 1 + 1
  • 3 + 1 + 1 + 1 + 1
  • 2 + 2 + 2 + 1
  • 2 + 2 + 1 + 1 + 1
  • 2 + 1 + 1 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1 + 1 + 1

これで、これらの組み合わせを2つのグループに分割できます。

  1. 最初の要素がm（この例では= 3）に等しい組み合わせ:)

    • 3 + 3 + 1
    • 3 + 2 + 2
    • 3 + 2 + 1 + 1
    • 3 + 1 + 1 + 1 + 1

  2. 最初の要素が以下の組み合わせm：

    • 2 + 2 + 2 + 1
    • 2 + 2 + 1 + 1 + 1
    • 2 + 1 + 1 + 1 + 1 + 1
    • 1 + 1 + 1 + 1 + 1 + 1 + 1

の組み合わせのすべてのメンバーはp(n,m)Group1またはGroup2のいずれかにあるため、と言うことができますp(n,m)=size(Group1) + size(Group2)。今、私たちがそれを証明しsize(Group1)=p(n-m, m)、size(Group2)=p(n,m-1)代用によって私たちが到達する場合p(n,m)=p(n-m,m)+p(n,m-1)

証明するsize(Group1)=p(n-m, m)：

前述の定義によると、以下の数を追加することによってp(n-m, m)得られる方法の数です。n-mm

  • mの各組み合わせに追加するp(n-m, m)と、Group1のメンバーになります。それでp(n-m, m) <= size(Group1)
  • mGroup1の各メンバーの最初を削除すると、の組み合わせになりp(n-m, m)ます。それでsize(Group1) <= p(n-m, m)

=> size(Group1) = p(n-m, m)。この例では：

Group1<===対応===>p（4、3）：

  • 7 = 3+ 3+1<===========> 3+1= 4
  • 7 = 3+ 2+2<===========> 2+2= 4
  • 7 = 3+ 2+1+1<=======> 2+1+1= 4
  • 7 = 3+ 1+1+1+1<===> 1+1+1+1= 4

したがって、とGroup1のメンバーの間には1対1の対応がp(n-m,m)あり、それらのサイズは同じです。

証明するsize(Group2)=p(n, m-1)：

定義上、は、以下（未満）の数値を追加p(n,m-1)することによって得られる方法の数です。Group2の定義を読み直すと、これら2つの定義が互いに同じであることがわかります。nm-1m=> size(Group2) = p(n, m-1)

于 2013-08-21T20:49:43.083 に答える
5 
        / 0 (k>n)
p(k,n)={  1 (k=n)
        \ p(k+1,n)+p(k,n-k) (k<n)

のパーティションの数はnですp(1,n)。

p(k,n)のパーティションの数でありn、加数のみを許可し>=kます。

OPの再帰式のように、（luiges90が言うように）それらを1つずつ追加します（多数のゼロの非効率性が追加されます）。ただし、幸いなことに、配列内で非常に高速に計算できます。

#include <stdio.h>

/* 406 is the largest n for which p(n) fits in 64 bits */
#define MAX 406
long long int pArray[MAX][MAX];

/* Emulate array starting at 1: */
#define p(k,n) pArray[k-1][n-1]

int main(int argc, char **argv) {
    int n, k;
    for (n = 1; n < MAX; n++) {
        for (k = n; k > 0; k--) {
            if (k > n) {
                p(k, n) = 0;
            } else if (k == n) {
                p(k, n) = 1;
            } else {
                p(k, n) = p(k, n - k) + p(k + 1, n);
            }
        }
    }
    for (n = 1; n < MAX; n++) {
        printf("p(%d)=%lld\n", n, p(1, n));
    }
}
于 2014-11-21T00:00:51.223 に答える
4

まず、この関数について知りたい以上のことについては、http：//mathworld.wolfram.com/PartitionFunctionP.htmlを参照してください。

この式については、最大メンバーが最大であるp(n, m)パー​​ティションの数として定義されていることに注意してください。nm

したがって、最大メンバーが最大であるp(n, m)パー​​ティションの数です。最大のメンバーが実際にであるかどうかによってそれらを分割しましょう。mmm

最大メンバーがであるパー​​ティションの数はm、埋める方法の数であり、最大メンバーが最大でであるn = m + ...パー​​ティションの数であり、定義上、である。n-mmp(n-m, m)

n最大のメンバーが最大であるパー​​ティションの数m-1は、定義によるものp(n, m-1)です。

したがってp(n, m) = p(n-m, m) + p(n, m-1)。

于 2013-08-20T15:41:16.957 に答える
2

合計がであり、各加数が。以下でp(n, m)あるすべての組み合わせの数として示します。ここでの重要なポイントは、次の再帰方程式を証明することです。nm

p(n, m) - p(n, m - 1) = p(n-m, m)          (1)

（1）の左側は、p（n、m）とp（n、m --1）の差です。これは、m加数として少なくとも1つを含むすべての組み合わせの数であり、残りの合計はn-m（全体的にはn）ですが、各加数は。以下ですm。しかし、それは正確には（1）の右側であるp（nm、m）を意味します。

明らかに、質問の答えはp（n、n）でなければなりません。

于 2012-12-27T13:35:22.430 に答える