概率：如果你有n個骰子，每個都有m個面孔，沒有辦法贏得

給你一些骰子n，每個骰子有許多面孔m。你擲出所有n個骰子並記下你擲出每個骰子的所有擲骰子的總和。如果你得到一個總和> = x，你就贏了，否則你輸了。找出你贏的概率。概率：如果你有n個骰子，每個都有m個面孔，沒有辦法贏得

我想過生成1到m（大小爲n）的所有組合，並保持只有那些總和大於x的組合的計數。總共沒有方法是m^n

之後，它只是兩者的divison。

有沒有更好的方法？

來源

2013-01-06 Peter

[編輯：正如jpalacek指出，時間複雜度是錯誤的 - 現在我已經解決了這個問題。]

你可以用動態規劃更有效地解決這個問題，首先改變成問題：

有多少種方法可以從n個骰子中獲得至少x個？

將其表示爲f（x，n）。那麼它必定是所有的

f（x，n）=和（f（x-i，n-1））== m。

I.e.如果第一個die有1個，剩下的n-1個骰子必須加起來至少爲x-1;如果第一個骰子有2個，剩下的n - 1個骰子必須加起來至少爲x - 2;等等。

總和中有m個項，所以如果你使用memoise這個函數，它將會是O（m^2 * n^2），因爲它最多需要做這個求和工作（m * n） * n次（即每個函數的唯一一組輸入一次，假設第一個參數x < = m * n）。

作爲獲得概率的最後一步，只需將f（x，n）的結果除以可能結果的總數即m^n。

來源

2013-01-06 13:48:41

你分析有點缺陷：爲了計算'f（x，n）'，你需要計算多於'm * n'的函數值（相當於'x * n'，但肯定小於這個值）。所以最後它會導致類似'O（x * n * m）' – jpalecek

@jpalecek：很好，謝謝。假設x <= n * m（因爲否則答案是平凡的0），O（m^2 * n^2）的界限應該沒問題 - 我會更新答案。 –

只是增加了對@ j_random_hacker基本上是正確的答案，你可以把它更快，當你注意到

F（X，N）= F（X-1，N） - F（XM-1 ，n-1）+ f（x-1，n-1）如果x> m + 1

這樣，您只需花費O(1)時間計算每個f值。

來源

2013-01-06 13:59:54 jpalecek

非常好，+1！在點擊它之前必須盯着它一段時間：除了第一個和最後一個之外，我給出的總和中的所有項與前一個x值的計算共享，因此只需分別減去並加上它們。 –

//傳遞curFace值將不允許重複組合
//對於3個骰子 - 和總和四月8日至2日2和2 2 4相同組合 - 那麼應該算作一個

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-11 06:38:19

概率：如果你有n個骰子，每個都有m個面孔，沒有辦法贏得

回答

相關問題