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

[o07608 (無良記者)]

開發平台(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++有沒有辦法做到這件事情

另一個有想到的作法是用遞迴，但是我的遞迴能力不怎麼樣，不知道該怎麼實現這個想法

請問版上的板友們能夠提供我一些可以實現此想法的建議或提示嗎？

或者能夠指引我另一條路？

感謝

--
到那時，在壁爐邊，當孫子坐在某位老人的膝蓋上，問道：「爺爺，你在亡靈天災入侵的
時候幹什麼呢？」 而他不用尷尬地干咳一聲，把孫子移到另一個膝蓋上，吞吞吐吐地說
：「啊……爺爺我當時在清淨農場挖牛糞。」與此相反，他可以直盯著他的眼睛理直氣壯
地說： 「孫子，爺爺我當年在立法院議場和那個狗娘養的三百暴民並肩作戰！」

                                                  ～《太陽花全書》 第一章第二節

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.14.213
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1421580761.A.7BC.html
→ wvwvwvwvwv: 2~12的機率有錯哦 1.2....6....2.1
 對耶XD

推 remizu: 函數包迴圈再遞迴即可
→ dritchie: 應該是DP找零錢問題的延伸?
→ bibo9901: convolution
→ bigpigbigpig: 你需要 Cartesian product (直積)
→ bigpigbigpig: http://pastebin.com/jxaZ0L2C (Python)
→ bigpigbigpig: http://pastebin.com/NvsuMKxL (6顆骰子點數和機率)
沒想到還有這兩種運算方法可以用0.0

......（理解中）（腦袋冒煙）

→ bigpigbigpig: http://stackoverflow.com/questions/5279051/
→ bigpigbigpig: how-can-i-create-cartesian-product-of-vector-of-
→ bigpigbigpig: vectors (C++ code，自己連結 link) :)
→ o07608: 喔喔感謝0.0
→ o07608: 有時間的話三種方法都各寫一個版本看看
→ o07608: 測資太大會跑不動（噴笑）
→ bigpigbigpig: 10 顆骰子，測資會太大嗎？多少顆骰子算太大？
→ o07608: 10顆沒問題，不過會花點時間運算
→ o07608: 不過我還沒用Cartesian product來寫，待會貼上程式碼
我目前先用conan0914板友在下一篇提供的程式碼來跑

感謝conan0914提供的程式碼，讓我至少能完成第一版的程式

而且也能比較熟悉遞迴怎麼用


底下是完整的程式碼：

http://codepad.org/YRy4ifog

不過題目要求要有5次、10次、20次的結果，而測到20次時程式就跑不動了XD


我還沒仔細研究Cartesian product，吃完晚餐來看看

→ o07608: 剛剛測了一下時間，扔十次要花三秒
→ o07608: 如果我沒理解錯的話，應該是要跑6^n次
→ o07608: 那扔20次要跑5.6年......
推 winken2004: 另外我看一下6^20約有10^15 分散給20~120
→ winken2004: data type用int的話小心overflow
→ o07608: 可是在我的電腦上，long的大小和int一樣0.0
推 bigpigbigpig: 20 顆骰子就得用 Dynamic Programming 才算得出來:)
→ o07608: 這又是一個要重新學習的範疇（死）
→ bigpigbigpig: http://codepad.org/gQHslXOG (20 顆點數和機率)
→ o07608: 居然瞬間想出來了......天啊
我目前的想法，是先把所有次數分成兩次兩次來算，分成幾小包

算完之後再每兩個小包下去算，重複直到結束

目前還在想實現的方法，不知道可不可行
※ 編輯: o07608 (114.27.11.45), 01/19/2015 21:22:35
推 bigpigbigpig: 提示：n顆點數和S 第一顆出1~6 其他顆總和S-1...S-6
→ o07608: 目前寫出來了，但不是用DP來寫的，現在回頭想DP