骰子扔k次sum达到n的概率

飞行棋的最基本规则很简单，扔骰子，数值为几就走几步。那如果扔k次，sum达到n的概率有多少呢？

先简化一下，如果骰子m只有1和2这么两种情况，试k=3次，sum到n=5的概率如下：

可以把骰子想象成0和1然后每次扔骰子都起码能+1 (相对于从1开始，这样从0开始的目的是为了后面的表格处理更完整)，因此这个概率等同于n=2, m=1, k=3，则

k=1时
0
1
k=2时
0 0
1 0
0 1
1 1
k=3时，一共8种情况
0 0 0 ==> 0
1 0 0 ==> 1
0 1 0 ==> 1
1 1 0 ==> 2
0 0 1 ==> 1
1 0 1 ==> 2
0 1 1 ==> 2
1 1 1 ==> 3
得
0: 1/8
1: 3/8
2: 3/8
3: 1/8
如果是从1开始，只需位移+3即可
3: 1/8
4: 3/8
5: 3/8
6: 1/8

sum达到2+3和3+3的概率之和为3/8+1/8 = 50%

用归纳法思考这个过程，用dp[i]表示达到正好i次的概率，无论尝试次数k为多少次都没有关系，随着k增大，dp[i]就表示k次之后的概率，不断更新。

用dp[i]表示达到正好i次的概率，用归纳法思考从k到k+1次的过程：

一共有m+1种可能性，

dp[i] if +0 即 上轮i时的概率加上这次为0的概率

dp[i-1] if +1 即 上轮i-1时的概率加上这次为1的概率

dp[i-2] if +2 即 上轮i-2时的概率加上这次为2的概率

…

如下图，扔2次时，dp[1]的新概率为 dp[1]/3 (第一次为1而这次为0) + dp[0]/3 (第一次为0而第二次为1) ==> dp[1] = 2/9

得到：

dp[i] = (dp[i] + dp[i-1]+ dp[i-2] + … + dp[i-m]) * 1/(m+1)

实现下代码如下

直观感受一下，骰子(1–6)扔7次，到这么多次的概率

package main
import (
 "fmt"
)
// n: targeting sum
// m: range of x in each round of generation
// k: num of rounds
func probSum(nn, mm, kk int) float32 {
 scale := float32(mm + 1)
 // upperbound, actually we can just set to size of nn
 // remember to add 1
 size := mm * kk
 if size > nn {
  size = nn
 }
 dp := make([]float32, size+1)
 for i := 0; i < len(dp); i++ {
  if i <= mm {
   // first round
   dp[i] = 1.0 / scale
  } else {
   dp[i] = 0.0
  }
 }
 // fmt.Printf("k=1, dp = %v\n", dp)
// kk rounds of generation
 for k := 2; k <= kk; k++ {
  curr := make([]float32, len(dp))
  // reach out to the upperbound in each round
  for i := 0; i < len(dp); i++ {
   ss := float32(0.0)
   for x := 0; x <= mm; x++ {
    if i-x < 0 {
     break
    }
    ss += dp[i-x]
   }
   curr[i] = ss / scale
  }
  // update the state
  dp = curr
  //  fmt.Printf("k=%d, dp = %v\n", k, dp)
 }
// print out
 ss := float32(100)
 for i := 0; i < len(dp); i++ {
  ss -= dp[i] * 100.0
  fmt.Printf("reach >= %d\t%.3f%%\n", kk+i+1, ss)
 }
ret := float32(0.0)
 for i := 0; i < len(dp); i++ {
  if i >= nn {
   break
  }
  ret += dp[i]
 }
return float32(1.0) - ret
}
func main() {
 nn, mm, kk := 23, 5, 7
 ret := probSum(nn, mm, kk)
 fmt.Printf("nn=%d, mm=%d, kk=%d, prob=%.5f\n", nn, mm, kk, ret)
}

直观感受一下，骰子(1–6)扔7次，到这么多次的概率

reach >= 8    100.000%
reach >= 9    99.997%
reach >= 10    99.987%
reach >= 11    99.957%
reach >= 12    99.882%
reach >= 13    99.717%
reach >= 14    99.389%
reach >= 15    98.794%
reach >= 16    97.791%
reach >= 17    96.213%
reach >= 18    93.878%
reach >= 19    90.612%
reach >= 20    86.284%
reach >= 21    80.830%
reach >= 22    74.283%
reach >= 23    66.784%
reach >= 24    58.579%
reach >= 25    50.000%   <-- 3.5 * 7 = 24.5
reach >= 26    41.421%
reach >= 27    33.216%
reach >= 28    25.717%
reach >= 29    19.170%
reach >= 30    13.716%
reach >= 31    9.388%
nn=23, mm=5, kk=7, prob=0.13716