推 o07608: 感謝!我再好好思考看看 01/21 13:50
※ 引述《o07608 (無良記者)》之銘言:
: 不能推文._.
: 在多方詢問下的成果,目前我的code如下:
: http://codepad.org/oJhiZbtj
: 原理是使用如下的機率分布規則:
: 1 1 1 1 1 1 (投一次)
: 1 1 1 1 1 1
: 1 1 1 1 1 1
: 1 1 1 1 1 1
: 1 1 1 1 1 1
: 1 1 1 1 1 1
: --------------------------------
: 1 2 3 4 5 6 5 4 3 2 1 (投兩次)
: 1 2 3 4 5 6 5 4 3 2 1
: 1 2 3 4 5 6 5 4 3 2 1
: 1 2 3 4 5 6 5 4 3 2 1
: 1 2 3 4 5 6 5 4 3 2 1
: 1 2 3 4 5 6 5 4 3 2 1
: 1 2 3 4 5 6 5 4 3 2 1
: -------------------------------------------------
: 1 3 6 10 15 21 25 27 27 25 21 15 10 6 3 1 (投三次)
: 這樣累加下去,就能獲得投n次骰子,每種點數和的機率
: 為了避免overflow,我用long long型態來存資料
: 不過這畢竟不是我想出來的,因此希望能再比較多靠自己的力量來想一個解法
: 目前正在思考bigpigbigpig給的提示,不過之前都沒有什麼DP的概念
: 想起來有點辛苦......
令 N(n,S) 代表投擲 n 顆骰子,點數和等於 S 的方式。
假設所有骰子均為公正,且彼此獨立,故 N(2,3) = 2,因為必須擲出 (1, 2)
或 (2, 1) 才能滿足 S = 3。
幾個顯然的邊界條件:
(1) N(n,S) = 0 for S < n and S > 6n
(2) N(1,S) = 1 for 1 <= S <= 6,
0 otherwise
(3) N(n,S) = N(n-1,S-1) + N(n-1,S-2) + N(n-1,S-3) +
N(n-1,S-4) + N(n-1,S-5) + N(n-1,S-6)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.25.176.232
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1421818786.A.621.html