[問題] 扔n次骰子,各種點數和的機率

作者: o07608 (無良記者)   2015-01-18 19:32:37
開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
VC++ 2013
問題(Question):
我不太確定這種問題能否在這邊發問,不過還是會試著盡量詳述我的問題與想法
這次有個功課,是要寫一個能夠計算扔n次骰子,出現的點數和的機率
比方說,扔一次骰子,點數會有1~6,機率各是1/6
扔兩次骰子,點數會從2~12,機率則會分別是{1,2,3,4,5,6,5,4,3,2,1}/36
依此類推
我最一開始的想法很直白,就是寫一個多層的巢狀迴圈來做這件事情
像是扔兩次骰子的情況下:
int a[11]; //然後把每個位置都初始為0
for(int i = 1; i <= 6; i++)
for(int j = 1; j <= 6; j++)
{
a[i + j]++;
}
扔三次骰子的話,則再多加一層以k為變數驅動的for迴圈,然後變成a[i + j + k]++;
依此類推,就可以算出每種點數和的個別次數,進而得知每種點數和的機率
但是現在的麻煩就是:n是使用者給定的,而n的大小關係到迴圈的層數
我不知道該怎麼隨著n的變化而增減迴圈層數,也不知道C++有沒有辦法做到這件事情
另一個有想到的作法是用遞迴,但是我的遞迴能力不怎麼樣,不知道該怎麼實現這個想法
請問版上的板友們能夠提供我一些可以實現此想法的建議或提示嗎?
或者能夠指引我另一條路?
感謝
作者: wvwvwvwvwv (殺死丁力這個雜碎a~)   2015-01-18 19:43:00
2~12的機率有錯哦 1.2....6....2.1
作者: remizu (remizu)   2015-01-18 20:20:00
函數包迴圈再遞迴即可
作者: dritchie (卍~邁斯納效應~卍)   2015-01-19 00:26:00
應該是DP找零錢問題的延伸?
作者: bibo9901 (function(){})()   2015-01-19 02:53:00
convolution
作者: bigpigbigpig (To littlepig with love)   2015-01-19 06:38:00
你需要 Cartesian product (直積)http://pastebin.com/jxaZ0L2C (Python)http://pastebin.com/NvsuMKxL (6顆骰子點數和機率)
作者: o07608 (無良記者)   2015-01-19 14:32:00
喔喔感謝0.0有時間的話三種方法都各寫一個版本看看測資太大會跑不動(噴笑)
作者: bigpigbigpig (To littlepig with love)   2015-01-19 17:40:00
10 顆骰子,測資會太大嗎?多少顆骰子算太大?
作者: o07608 (無良記者)   2015-01-19 17:50:00
10顆沒問題,不過會花點時間運算不過我還沒用Cartesian product來寫,待會貼上程式碼剛剛測了一下時間,扔十次要花三秒如果我沒理解錯的話,應該是要跑6^n次那扔20次要跑5.6年......
作者: winken2004 (新竹肥宅)   2015-01-19 18:18:00
另外我看一下6^20約有10^15 分散給20~120data type用int的話小心overflow
作者: o07608 (無良記者)   2015-01-19 18:24:00
可是在我的電腦上,long的大小和int一樣0.0
作者: bigpigbigpig (To littlepig with love)   2015-01-19 19:41:00
20 顆骰子就得用 Dynamic Programming 才算得出來:)
作者: o07608 (無良記者)   2015-01-19 20:13:00
這又是一個要重新學習的範疇(死)
作者: bigpigbigpig (To littlepig with love)   2015-01-19 20:19:00
http://codepad.org/gQHslXOG (20 顆點數和機率)
作者: o07608 (無良記者)   2015-01-19 20:23:00
居然瞬間想出來了......天啊
作者: bigpigbigpig (To littlepig with love)   2015-01-19 21:34:00
提示:n顆點數和S 第一顆出1~6 其他顆總和S-1...S-6
作者: o07608 (無良記者)   2015-01-20 17:09:00
目前寫出來了,但不是用DP來寫的,現在回頭想DP

Links booklink

Contact Us: admin [ a t ] ucptt.com