推 LPH66: 其實 DP 做法跟把這個多項式做 n 次方本質上是一樣的 01/20 23:23
推 firejox: 用\FFT/ 01/21 16:23
※ 引述《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
: 依此類推
數學一點的作法
擲n次骰子點數和為P的機率，等於下列方程式之中，x^P項的係數除以6^n
( x + x^2 + x^3 + x^4 + x^5 + x^6 )^n
n,P又會滿足下列兩個等式:
P1 + P2 + P3 + P4 + P5 + P6 = n
1*P1 + 2*P2 + 3*P3 + 4*P4 + 5*P5 + 6*P6 = P
其中, P1是n次擲骰子過程中，擲出1點的次數
P2是n次擲骰子過程中，擲出2點的次數
P3是n次擲骰子過程中，擲出3點的次數
P4是n次擲骰子過程中，擲出4點的次數
P5是n次擲骰子過程中，擲出5點的次數
P6是n次擲骰子過程中，擲出6點的次數
對於任意的n與P，寫個程式可以找出所有的P1,P2...P6組合
然後帶入多項式定理，算出x^P項係數
......想到這邊我覺得還是DP比較好寫
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.133.252.160
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1421765213.A.6D2.html