Question

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

玩过麻将的人都知道，骰子一共6个面，每个面上都有一个点数，对应的是1～6之间的一个数字。所以n个骰子的点数和的最小值为n，最大值为6n。另外根据排列组合的知识，我们还知道n个骰子的所有点数的排列数为6ⁿ。要解决这个问题，我们需要先统计出每一个点数出现的次数，然后把每一个点数出现的次数除以6ⁿ，就能求出每个点数出现的概率。

解法一：基于递归求骰子点数，时间效率不够高

现在我们考虑如何统计每一个点数出现的次数。要想求出n个骰子的点数和，可以先把n个骰子分为两堆：第一堆只有一个，另一个有n－1个。单独的那一个有可能出现从1到6的点数。我们需要计算从1到6的每一种点数和剩下的n－1个骰子来计算点数和。接下来把剩下的n－1个骰子还是分成两堆，第一堆只有一个，第二堆有n－2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加，再和剩下的n－2个骰子来计算点数和。分析到这里，我们不难发现这是一种递归的思路，递归结束的条件就是最后只剩下一个骰子。

我们可以定义一个长度为6n－n＋1的数组，和为s的点数出现的次数保存到数组第s－n个元素里。基于这种思路，我们可以写出如下代码：

上述思路很简洁，实现起来也容易。但由于是基于递归的实现，它有很多计算是重复的，从而导致当number变大时性能慢得让人不能接受。关于递归的性能讨论，详见本书2.4.2节。

解法二：基于循环求骰子点数，时间性能好

可以换一种思路来解决这个问题。我们可以考虑用两个数组来存储骰子点数的每一个总数出现的次数。在一次循环中，第一个数组中的第n个数字表示骰子和为n出现的次数。在下一循环中，我们加上一个新的骰子，此时和为n的骰子出现的次数应该等于上一次循环中骰子点数和为n－1、n－2、n－3、n－4、n－5与n－6的次数的总和，所以我们把另一个数组的第n个数字设为前一个数组对应的第n－1、n－2、n－3、n－4、n－5与n－6之和。基于这个思路，我们可以写出如下代码：

在上述代码中，我们定义了两个数组pProbabilities[0]和pProbabilities[1]来存储骰子的点数之和。在一轮循环中，一个数组的第n项等于另一数组的第n－1、n－2、n－3、n－4、n－5以及n－6项的和。在下一轮循环中，我们交换这两个数组（通过改变变量flag实现）再重复这一计算过程。

值得注意的是，上述代码没有在函数里把一个骰子的最大点数硬编码（hard code）为6，而是用一个变量g_maxValue来表示。这样做的好处是，如果某个厂家生产了其他点数的骰子，我们只需要在代码中修改一个地方，扩展起来很方便。如果在面试的时候我们能对面试官提起对程序扩展性的考虑，一定能给面试官留下很好的印象。

源代码：

本题完整的源代码详见43_DicesProbability项目。

测试用例：

- 功能测试（1、2、3、4个骰子的各点数的概率）。

- 特殊输入测试（输入0）。

- 性能测试（输入较大的数字，比如11）。

本题考点：

- 数学建模的能力。不管采用哪种思路解决问题，我们都要先想到用数组来存放n个骰子的每一个点数出现的次数，并通过分析点数的规律建立模型并最终找到解决方案。

- 考查对递归和循环的性能的理解。