4

n個のサイコロが与えられ、それぞれにm個の面があります。n 個のサイコロをすべて転がし、各サイコロを振って得たすべての出目の合計を書き留めます。合計が x 以上の場合は勝ち、それ以外の場合は負けです。勝つ確率を求めてください。

1 から m (サイズ n ) のすべての組み合わせを生成し、合計が x を超える組み合わせのみをカウントすることを考えました。ウェイの総数は m^n

その後は、両方を分割するだけです。

より良い方法はありますか？

4

3 に答える 3

7

[編集: jpalacek が指摘したように、時間の計算量が間違っていました -- これを修正しました。]

最初に質問に変更することにより、動的計画法でこれをより効率的に解決できます。

n 個のサイコロから少なくとも x を得る方法は何通りありますか?

これを f(x, n) と表現します。そしたらそうなるに違いない

f(x, n) = sum(f(x - i, n - 1)) すべての 1 <= i <= m.

つまり、最初のサイコロの目が 1 の場合、残りの n - 1 個のサイコロの合計は少なくとも x - 1 になる必要があります。最初のサイコロが 2 の場合、残りの n - 1 サイコロの合計は少なくとも x - 2 になる必要があります。等々。

合計には m 個の項があるため、この関数をメモすると、O(m^2*n^2) になります。これは、この合計作業を最大で (m * n) * n 回実行する必要があるためです (つまり、最初のパラメーター x <= m * n であると仮定して、関数への入力の一意のセットごとに 1 回)。

確率を求める最後のステップとして、f(x, n) の結果を可能な結果の総数、つまり m^n で割ります。

于 2013-01-06T13:48:41.153 に答える
4

@j_random_hackerの基本的に正しい答えを追加するために、次のことに注意すると、さらに速くすることができます

f(x, n) = f(x-1, n) - f(xm-1, n-1) + f(x-1, n-1) if x>m+1

O(1)この方法では、各値の計算に時間を費やすだけfです。

于 2013-01-06T13:59:54.997 に答える
1

//curFace 値を渡すと組み合わせの重複は許可されません
//3 つのサイコロの場合 - 合計 8 - 2 4 2 と 2 2 4 は同じ組み合わせなので、1 つとしてカウントする必要があります

int sums(int totSum,int noDices,int mFaces,int curFace,HashMap<String,Integer> map)
{

    int count=0;

    if (noDices<=0 || totSum<=0)
            return 0;

    if (noDices==1)
    {
         if (totSum>=1 & totSum<=mFaces)
             return 1;
         else
             return 0;    
    }
    if (map.containsKey(noDices+"-"+totSum))
        return map.get(noDices+"-"+totSum);

    for (int i=curFace;i<=mFaces;i++)
    {

        count+=sums(totSum-i,noDices-1,mFaces,i,map);
    }

    map.put(noDices+"-" +totSum,count);

    return count;
}
于 2013-08-11T06:38:19.757 に答える