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是 sum，目的是找出它有多少个（sum）组合。

我只想知道为什么要这样做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，因为有 8 种方法可以使小于 3 的数字变成 7，如下所示：（为简单起见，我们可以假设始终按从大到小的顺序添加数字）

  • 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

现在我们可以将这些组合分成两组：

  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

p(n-m,m)所以和 Group1 的任何成员都是一一对应的，它们的大小是相等的。

证明size(Group2)=p(n, m-1)：

根据定义，p(n,m-1)是n通过添加一些小于或等于m-1（小于m）的数字而得到的结果的数量。如果你重新阅读 Group2 的定义，你会发现这两个定义是相同的。=> 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 所说）将它们一一添加（增加了许多零的低效率）。不过幸运的是，它可以在数组中以极快的速度计算：

#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)定义为n最大成员最多为 的分区数m。

因此p(n, m)是m其最大成员最多的分区数m。让我们根据最大的成员是否实际来划分它们m。

最大成员为的分区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)为总和为n且每个加数小于或等于的所有组合的数量m。这里的关键是证明以下递归方程：

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

(1)的左边是p(n, m)和p(n, m - 1)的差，它们是包含至少一个m作为加数的所有组合的数量，剩下的和是n-m（使得总体是n)，除此之外每个加数都小于或等于m. 但这恰好意味着 p(nm, m)，它是 (1) 的右侧。

显然，问题的答案应该是p(n,n)。

于 2012-12-27T13:35:22.430 回答