剑指offer 面试题60. n个骰子的点数（易）

要想把各种现实问题抽象成数学模型并用计算机的编程语言表达出来，应聘者除了需要具备扎实的数学基础和编程能力，还需要具有敏锐的洞察力和丰富的想象力。

建模的第一步是选择合理的数据结构来表述问题。 建模的第二步是分析模型中的内在规律，并用编程语言表述这种规律。

Question

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例 1: 

1
2
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2: 
1
2
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
限制：1 <= n <= 11

测试用例

功能测试（1、2、3、4个骰子的各点数的概率）。 特殊输入测试（输入0）。 性能测试（输入较大的数字，如11）。

本题考点

考查应聘者的数学建模能力。不管采用哪种思路解决问题，我们都要先想到用数组来存放n个骰子的每个点数出现的次数，并通过分析点数的规律建立模型，最终找到解决方案。 考查应聘者对递归和循环的性能的理解。

Intuition

基于递归来实现

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

现在我们考虑如何统计每个点数出现的次数。要想求出n个骰子的点数和，可以先把n个骰子分为两堆：第一堆只有一个；另一堆有n-1个。

单独的那一个有可能出现1~6的点数。我们需要计算1~6的每一种点数和剩下的n-1个骰子来计算点数和。

接下来把剩下的n-1个骰子仍然分成两堆：第一堆只有一个；第二堆有n-2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加，再和剩下的n-2个骰子来计算点数和。

分析到这里，我们不难发现这是一种递归的思路，递归结束的条件就是最后只剩下一个骰子。我们可以定义一个长度为 6n-n+1 的数组，将和为s的点数出现的次数保存到数组的第s-n个元素里。

基于循环来实现

首先，很明显只有一个骰子的时候，1，2，3，4，5，6出现的次数都为1。那么如果 n=2，即2个骰子，最终能得到的骰子点数和的范围时2-12。出现点数和为分别为6、7、8、9、10、11、12的话，各自有多少种情况呢？设数组 count[i] 为掷出骰子的和为 i 的组合数，则 count[6]=1、count[7]=6、count[8]=5、count[9]=4、count[10]=3、count[11]=2、count[12]=1。

n i count(probability) combination
1 1 1 (1/6) 1
2 1 (1/6) 2
3 1 (1/6) 3
4 1 (1/6) 4
5 1 (1/6) 5
6 1 (1/6) 6
2 2 1 (1/36) 1+1
3 2 (2/36) 1+2、2+1
4 3 (3/36) 1+3、2+2、3+1
5 4 (4/36) 1+4、2+3、3+2、4+1
6 5 (5/36) 1+5、2+4、3+3、4+2、5+1
7 6 (6/36) 1+6、2+5、3+4、4+3、5+2、6+1
8 5 (5/36) 2+6、3+5、4+4、5+3、6+2
9 4 (4/36) 3+6、4+5、5+4、6+3
10 3 (3/36) 4+6、5+5、6+4
11 2 (2/36) 5+6、6+5
12 1 (1/36) 6+6
3 3 1 (1/216) 1+1+1
4 3 (3/216) 1+2+1、2+1+1、1+1+2
5 7 (7/216) 1+2+2、2+1+2、3+1+1、2+2+1、1+3+1、1+2+2、1+1+3
... ... ...

由此可知，如果要计算 n=2 时，count=6 的概率，我们需要先计算出 n=1 时，P(count=1|n=1)=1/6、P(count=2|n=1)=1/6、P(count=3|n=1)=1/6、P(count=4|n=1)=1/6、P(count=5|n=1)=1/6、P(count=6|n=1)=1/6。则 P(count=6|n=2) 的概率可以由下列公式计算得到：

1
2
3
4
5
6
P(count=6|n=2) = P(count=1|n=1) * P(count=5|n=1) + 
                 P(count=2|n=1) * P(count=4|n=1) + 
                 P(count=3|n=1) * P(count=3|n=1) + 
                 P(count=4|n=1) * P(count=2|n=1) + 
                 P(count=5|n=1) * P(count=1|n=1)
                 =  1/36 +  1/36 + 1/36 + 1/36 + 1/36  = 5/36

同理，如果要计算 n=2 时，count=1 的概率 P(count=1|n=3)，可以由下列公式计算得到

1
2
3
4
5
P(count=1|n=3) = P(count=1|n=1) * P(count=1|n=1) * P(count=1|n=1)
               = P(count=1|n=1) * P(count=1|n=2)
               = 1/6 * 1/6 * 1/6
               = 1/36 * 1/6
               = 1/216

以上过程可以通过循环代码来实现。

参考链接

作者：lucifer 链接：https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/di-gui-huo-zhe-die-dai-du-ke-yi-python-and-javascr/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

基于迭代来实现

注意，统计的是组合数量。最后除以了 \(6^n\)，就是概率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def twoSum(self, n: int) -> List[float]:
        MAX_VALUE = 6
        def diceCnt(n):
            # step 1 层层递归 求解cnts
            if n == 1:
                return [0] + [1] * MAX_VALUE  # 第0位为0，n=1，就是只有一个骰子，这种情况下，骰子不可能掷出0的结果。
            cnts = diceCnt(n - 1) + [0] * MAX_VALUE  # 用一个数组cnts，cnts[i] 表示掷出的骰子点数和为i的组合数。
            # step 2 基于前面的结果逐个更新 cnts
            for i in range(6 * n, 0, -1):
                cnts[i] = sum(cnts[max(i - MAX_VALUE, 0): i])
            return cnts
        return list(filter(
                    lambda a: a != 0, list(
                        map(lambda a: a / MAX_VALUE ** n, diceCnt(n))  # 求解概率，count / 6 ** n，保留不为0的概率。
                    )
                )
            )

基于循环来实现（推荐，效率更高！）

注意，循环过程中直接就是在计算概率。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def twoSum(self, n):
        MAX_VALUE = 6
        pre_probabilities = [1/MAX_VALUE] * MAX_VALUE  # base probability
        for i in range(1, n):
            new_add_probabilities = [1/MAX_VALUE] * MAX_VALUE  # 每次新增骰子之后的new-add probability 
            temp = [0] * (MAX_VALUE + 5 * i)
            for pre_index in range(len(pre_probabilities)):
                for cur_index in range(len(new_add_probabilities)):
                    temp[pre_index+cur_index] += pre_probabilities[pre_index]* new_add_probabilities[cur_index]
            pre_probabilities = temp  # 更新base probability
        
        return [round(probability, 5) for probability in pre_probabilities]

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