1. 题目描述

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

2. 思路分析

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

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

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

3. 算法实现

注释中都有详细说明:

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);
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
60
61
62