5 
int s_dynamic(int n,int k) {
    int maxj = n-k;

    int *arr = new int[maxj+1];

    for (int i = 0; i <= maxj; ++i)
        arr[i] = 1;

    for (int i = 1; i <= k; ++i)
        for(int j = 1; j <= maxj; ++j)
            arr[j] += i*arr[j-1];

    return arr[maxj];
}

動的計画法を使用してスターリング数を決定する私の試みは次のとおりです。

次のように定義されています。

S(n,k) = S(n-1,k-1) + k S(n-1,k)、1 < k < n の場合

S(n,k) = 1、k=1 または k=n の場合

大丈夫そうですよね？単体テストを実行するときを除いて...

partitioningTest ..\src\Test.cpp:44 3025 == s_dynamic(9,3) expected:    3025    but was:    4414

誰かが私が間違っていることを見ることができますか?

ありがとう！

ところで、再帰的な解決策は次のとおりです。

int s_recursive(int n,int k) {
    if (k == 1 || k == n)
        return 1;

    return s_recursive(n-1,k-1) + k*s_recursive(n-1,k);
}
4

2 に答える 2

4

バグを発見。k=1 (すべての n に対して S(n,1)=1) のスターリング数の動的配列を既に計算しています。S(n,2) の計算を開始する必要があります。つまり、次のようになります。

for (int i = 2; i <= k; ++i) //i=2, not 1
  for(int j = 1; j <= maxj; ++j)
    arr[j] += i*arr[j-1];
于 2011-02-27T13:16:03.070 に答える
3

単純なインデックス作成エラーを犯したように見えることを除いて、あなたのアプローチは問題ありません。iインデックスとj表現が何を表し、内側のループが何に変換されるかを考えるとarr[j]、それは十分に簡単であることがわかります (嘘です。何が何であるかを理解するのに 30 分かかりました :))。

私が解読できるものから、計算中iの値を表し、から に変換されます。初期化する最上位の for ループは、それを として設定します。これらのループによると、計算は問題ないように見えます。1つのことを除いて：最初のループはが含まれていると想定しているため、問題がある場所です。の開始値をからに変更した場合、すべて問題ありません (エッジ ケースでは if または 2 つが必要になる場合があります)。イニシャルはからに変換され、残りの変換は問題ありません。karr[j]S(i+j, i-1)S(i+1+j, i)arrS(1+j, 1)iarr[j]S(0+j, 0)i12i=2arr[j]S(1+j, 1)S(2+j, 2)

または、定義されている場合は に初期化arr[j]することもできS(0+j, 0)ましたが、残念ながら、スターリングの数値は で未定義k=0です。

編集：どうやら私の最後のコメントは間違っていたようです。arr を {1, 0, 0, ...} に初期化すると、の開始値をそのままにiしておくことができます1。このために、代わりに初期値S(0, 0)=1とを使用しS(n, 0)=0, n>0ます。

于 2011-02-27T13:18:10.957 に答える