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 までの整数です。入力は 2 つの 0 で終了します。出力 Larry は答えの最後の数桁だけに関心があるため、数値 N と K の各ペアに対して、1,000,000 を法とする 1 つの数値を 1 行に出力します。

サンプル入力

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 choose kの結果とすると、問題の解は C(N + K - 1, K - 1) であり、これらの K 数が非負である (またはN = 0 および K = 2 の場合でも無限に多くの解になります)。

K 個の数は非負であり、和 N は一定であるため、この問題は次のように考えることができます。キャンディーを一列に並べて分割し、キャンディーの間に (K - 1) セパレーターを配置します。(K - 1) セパレーターは、キャンディーの K 個の部分までキャンディーを分割します。別の見方をすれば、(N + K - 1) の位置から (K - 1) の位置を選んで区切り記号を入れれば、残りの位置はキャンディーになるようなものです。したがって、これは、方法の数が N + (K - 1) 選択 (K - 1) である理由を説明しています。

次に、問題は C( n , k )の最下位桁を見つける方法に帰着します。(N と K の最大値は で定義されているように 100 であるため、アルゴリズムが O(n 3maxn )まで上がっても心配する必要はありません)。

計算では、この組み合わせ恒等式 C( n , k ) = C( n - 1 , k ) + C( n , k - 1 ) (パスカルの規則) が使用されます。この実装の賢い点は、 C( n , k ) (組み合わせの結果のテーブル、ジャグ配列) を格納せず、代わりに C(N, K) を格納することです。ID は実際には次の場所に存在しますT[i][j] = (T[i][j-1] + T[i-1][j])。

  • 最初の次元は、実際には部分の数である K です。そして、2 番目の次元は合計 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 に初期化されています。
  • 行 K = 1 を 1 で埋めます (N を 1 つの部分に分割する方法は 1 つしかありません)。
  • 残りの行については、ケース N = 0 を 1 に設定します (0 を K 個の部分に分割する方法は 1 つしかなく、すべての部分が 0 です)。
  • T[i][j] = (T[i][j-1] + T[i-1][j])次に、前の行と同じ行の前の要素を参照する式で残りが埋められます。どちらも以前の繰り返しで埋められています。
于 2012-08-19T11:52:02.540 に答える
0

これは有名な問題です -ここで解決策を確認できます

N個の同じボールをK個の箱に落とす方法は何通りか。

次のアルゴリズムは、問題に対する動的プログラミング ソリューションです。

D[i,j] を、j より小さい i の数を合計して 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

この問題は「整数分割問題」として知られています。基本的に、n の k パーティションの再帰的計算が存在しますが、ソリューションはその動的プログラミング バージョンにすぎません (非再帰的で、略してボトムアップの計算)。

于 2013-06-26T15:20:10.157 に答える
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 に答える