[问题] 扔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