n个骰子的点数

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. 算法实现