0

nx 1 のグリッドがあります。少なくとも r 個の赤のセル、少なくとも g 個の緑のセル、少なくとも b 個の青のセルで色を付ける必要があります。(n + r + g <= n)。少なくとも 1 つの位置が異なる場合、2 つのパターンは異なると言われます。いくつの方法で色を付けることができますか。(解決策は、アルゴリズムまたは数学のいずれかです)。

私の試み：

enter code here
int func(int id, int r, int g, int b)
{
     int ma = 0;
     if (id == n) {
        if (r > 0)
            ma++;
        if (g > 0)
             ma++;
        if (b > 0)
             ma++;
        return ma;
     }
     if (r > 0)
       ma += func(r-1, g, b, id + 1);
     if (g > 0)
       ma += func(r, g-1, b, id + 1);
     if (b > 0)
        ma += func(r, g, b-1, id + 1);

    if (r + g + b < n - id)  {
           ma += func(r, g, b, id + 1);
    }

    return ma;

}

4

1 に答える 1

0

それらの数が であると仮定するとf(n,r,g,b)、次の再帰があります。

f(n,r,g,b) = f(n-1,r,g,b)*3 + f(n-1,r-1,g,b)+f(n-1,r,g-1,b)+f(n-1,r,g,b-1).

また、基本ケースもわかっていますf(1,1,0,0)=f(1,0,1,0)=f(1,0,0,1)=1。下から開始し、上記の再帰によって f(n,r,g,b) を構築します。( for ループの代わりにメモ化を使用すると簡単です)。実行時間はO(n*r*g*b)です。

更新:あなたのコードは私の答えに近いですが、最初に間違っていると言わなければなりません.2番目に、指数関数的な実行時間を引き起こす単純な再帰を使用し、サイズ n r g*b の配列を割り当てて、既に計算された答えを再計算しないようにします。メモ化の例については、これを参照してください。

于 2013-10-10T13:48:34.897 に答える