0

问题：

拉里的数学很差——他通常使用计算器，这在整个大学期间都很好用。不幸的是，他现在和他的好伙伴瑞恩在一次滑雪事故后被击中了一个荒岛。他们现在正试图花一些时间解决一些好的问题，如果他不能回答，莱恩会吃掉拉里，所以他的命运取决于你！

这是一个非常简单的问题——给定一个数 N，小于 N 的 K 个数加起来 N 有多少种方式？

例如，对于 N = 20 和 K = 2，有 21 种方式：

0+20
1+19
2+18
3+17
4+16
5+15
...
18+2
19+1
20+0

输入 每行将包含一对数字 N 和 K。N 和 K 都是从 1 到 100 的整数，包括 1 到 100。输入将在 2 个 0 处终止。输出 由于拉里只对答案的最后几位感兴趣，因此对于每对数字 N 和 K，在一行上打印一个数字 mod 1,000,000。

样本输入

20 2
20 2
0 0

样本输出

21
21

解决方案代码：

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
#define maxn 100

typedef long ss;
ss T[maxn+2][maxn+2];

void Gen() {
    ss i, j;
    for(i = 0; i<= maxn; i++)
        T[1][i] = 1;
    for(i = 2; i<= 100; i++) {
        T[i][0] = 1;
        for(j = 1; j <= 100; j++)
            T[i][j] = (T[i][j-1] + T[i-1][j]) % 1000000;
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    ss n, m;
    Gen();
    while(cin>>n>>m) {
        if(!n && !m) break;
        cout<<T[m][n]<<endl;
    }
    return 0;
}

这个计算是如何得出的？它是怎么来的T[i][j] = (T[i][j-1] + T[i-1][j])？

4

4 回答 4

1

注意：我只使用n和k（小写）来引用一些匿名变量。我将始终使用 N 和 K（大写）来指代问题中定义的 N 和 K（总和和部分数量）。

设 C( n , k ) 为n选择k的结果，则问题的解为 C(N + K - 1, K - 1)，假设这 K 个数是非负数（或者有即使对于 N = 0 和 K = 2) 也是无限多解。

由于 K 个数是非负数，并且 N 的总和是固定的，我们可以把问题想成：K 个人之间有多少种分配糖果的方法。我们可以通过将糖果排成一条线来划分糖果，并在糖果之间放置 (K - 1) 分隔符。(K - 1) 分隔符将糖果分成 K 份糖果。换个角度看，也好比在（N+K-1）个位置中选择（K-1）个位置放入分隔符，剩下的位置都是糖果。所以，这就解释了为什么方法数是 N + (K - 1) 选择 (K - 1)。

然后问题归结为如何找到 C( n , k )的最低有效数字。（由于 N 和 K 的最大值是 100 中定义的maxn，因此我们不必担心算法是否达到 O(n 3 )）。

计算使用此组合恒等式 C( n , k ) = C( n - 1 , k ) + C( n , k - 1 ) （帕斯卡规则）。该实现的聪明之处在于它不存储 C( n , k )（组合结果表，它是一个锯齿状数组），而是存储 C(N,K)。身份实际上存在于T[i][j] = (T[i][j-1] + T[i-1][j])：

  • 第一个维度实际上是 K，即部分的数量。而第二维是和N。T[K][N]将直接存储结果，根据上面推导的数学结果，是C(N + K - 1, K - 1)的(最低有效位)。

  • 将背面重写T[i][j] = (T[i][j-1] + T[i-1][j])为等效的数学结果：

    C(i + j - 1, i - 1) = C(i + j - 2, i - 1) + C(i + j - 2, i - 2)，根据恒等式正确。

该程序将逐行填充数组：

  • 行 K = 0 已经初始化为 0，使用静态数组初始化为 0 的事实。
  • 它用 1 填充行 K = 1（只有一种方法可以将 N 分成 1 部分）。
  • 对于其余的行，它将案例 N = 0 设置为 1（只有 1 种方法可以将 0 分成 K 个部分 - 所有部分都是 0）。
  • 然后用表达式 填充其余部分，该表达式T[i][j] = (T[i][j-1] + T[i-1][j])将引用前一行和同一行的前一个元素，这两者都已在早期的迭代中填充。
于 2012-08-19T11:52:02.540 回答
0

这是一个著名的问题 - 您可以在此处查看解决方案

有多少种方法可以将 N 个相同的球扔到 K 个盒子中。

以下算法是您问题的动态规划解决方案：

将 D[i,j] 定义为 i 数小于 j 的方式数，总和为 j。

0 <= i < = N 1 <= j <= K

其中对于每个 j，D[j,1] = 1。

在哪里 j > 1 你得到：

D[i,j] = D[i,j-1] + D[i-1,j-1] +...+ D[0,j-1]
于 2012-08-19T12:43:27.613 回答
0

令 C(x, y) 为 x 选择 y 的结果，则其值T[i][j]等于：C(i - 1 + j, j)。

你可以通过归纳来证明这一点。

基本情况：

T[1][j] = C(1 - 1 + j, j) = C(j, j) = 1

T[i][0] = C(i - 1, 0) = 1

对于归纳步​​骤，使用公式（对于 0<=y<=x）：

C(x,y) = C(x - 1, y - 1) + C(x - 1, y)

所以：

C(i - 1 + j, j) = C(i-1+j - 1, j - 1) + C(i-1+j - 1, j) = C(i-1+(j-1), (j-1)) + C((i-1)-1+j, j)

或者换句话说：

T[i][j] = T[i,j-1] + T[i-1,j]

现在，正如nhahtdh之前提到的，您正在寻找的值是 C(N + K - 1, K - 1)，它等于：

T[N+1][K-1] = C(N+1-1+K-1, K-1)

（模 1000000）

于 2012-08-19T12:50:01.293 回答
0

该问题被称为“整数分区问题”。基本上存在 n 的 k 分区的递归计算，但您的解决方案只是它的动态编程版本（简称非递归和自下而上计算）。

于 2013-06-26T15:20:10.157 回答