1. 题目描述

把 n 个骰子扔在地上，所有骰子朝上一面的点数之和为 s。输入 n，打印出 s 的所有可能的值出现的概率。

2. 思路分析

递归的思路就是组合出所有情况，然后每种情况记录出现次数，最后除以 6^n 即可。其中，6^n 就是所有情况的总数。

书中提出的方法是使用循环来优化递归，递归是自顶向下，循环是自底向上，思考起来有难度。

技巧性很强，准备 2 个数组，假想每次投掷一个骰子，出现和为 n 的次数，就是之前骰子和为 n-1, n-2, …, n-6 的次数和。依次类推，每次存储结果都和之前的数组不同。

3. 算法实现

注释中都有详细说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
const gMaxValue = 6 // 每个骰子的最大点数

/**
 *
 * @param {Number} number 骰子的个数
 */
function printProbability(number) {
    if (number < 1) {
        return
    }

    const probabilities = [new Array(gMaxValue * number + 1), new Array(gMaxValue * number + 1)]
    let flag = 0

    // 初始化
    for (let i = 0; i < gMaxValue * number + 1; ++i) {
        probabilities[0][i] = probabilities[1][i] = 0
    }

    // 第一次掷骰子，出现的和只有有 gMaxValue 种情况，每种和的次数为 1
    for (let i = 1; i <= gMaxValue; ++i) {
        probabilities[flag][i] = 1
    }

    // 之后是从第 2 ~ number 次掷骰子
    //
    for (let k = 2; k <= number; ++k) {
        // 第k次掷骰子，那么最小值就是k
        // 不可能出现比k小的情况
        for (let i = 0; i < k; ++i) {
            probabilities[1 - flag][i] = 0
        }

        // 可能出现的和的范围就是 [k, gMaxValue * k + 1)
        // 此时和为i的出现次数，就是上次循环中骰子点数和为
        // i - 1, i - 2, ..., i - 6 的次数总和
        for (let i = k; i < gMaxValue * k + 1; ++i) {
            probabilities[1 - flag][i] = 0
            // 这里的j是指：本骰子掷出的结果
            for (let j = 1; j < i && j <= gMaxValue; ++j) {
                probabilities[1 - flag][i] += probabilities[flag][i - j]
            }
        }

        flag = 1 - flag
    }

    // 全部情况的总数
    const total = Math.pow(gMaxValue, number)
    for (let i = number; i < gMaxValue * number + 1; ++i) {
        console.log(`sum is ${i}, ratio is ${probabilities[flag][i] / total}`)
    }
}

/**
 * 测试代码
 * 6个骰子，所有和出现的可能性
 */
printProbability(6)