給你一些骰子n,每個骰子有許多面孔m。你擲出所有n個骰子並記下你擲出每個骰子的所有擲骰子的總和。如果你得到一個總和> = x,你就贏了,否則你輸了。找出你贏的概率。概率:如果你有n個骰子,每個都有m個面孔,沒有辦法贏得
我想過生成1到m(大小爲n)的所有組合,並保持只有那些總和大於x的組合的計數。總共沒有方法是m^n
之後,它只是兩者的divison。
有沒有更好的方法?
給你一些骰子n,每個骰子有許多面孔m。你擲出所有n個骰子並記下你擲出每個骰子的所有擲骰子的總和。如果你得到一個總和> = x,你就贏了,否則你輸了。找出你贏的概率。概率:如果你有n個骰子,每個都有m個面孔,沒有辦法贏得
我想過生成1到m(大小爲n)的所有組合,並保持只有那些總和大於x的組合的計數。總共沒有方法是m^n
之後,它只是兩者的divison。
有沒有更好的方法?
[編輯:正如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。
只是增加了對@ 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
值。
非常好,+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;
}
你分析有點缺陷:爲了計算'f(x,n)',你需要計算多於'm * n'的函數值(相當於'x * n',但肯定小於這個值)。所以最後它會導致類似'O(x * n * m)' – jpalecek
@jpalecek:很好,謝謝。假設x <= n * m(因爲否則答案是平凡的0),O(m^2 * n^2)的界限應該沒問題 - 我會更新答案。 –