骰子点数之和问题

冰之角

发布于 2018-12-06 10:00:39

1.5K0

发布于 2018-12-06 10:00:39

文章被收录于专栏：Winter漫聊技术

6骰子之和的概率

小伙伴前阵子面试被问到一个问题：

同时掷出六个骰子，求可能出现的点数之和的概率。

思索

6个骰子，点数都是1～6，可能出现的点数和是6～36，那么各个点数和的概率呢？

从独立概率入手可能可以更好地解决问题，因为不需要单独考虑每个点数和的概率。6个骰子，每个骰子出现1、2、3、4、5、6的概率相等且独立随机的，所以总的情况有6^6 种（如果有10个骰子，那就是6^10种）。然后我们对这 6^6 种情况遍历，然后根据其点数之和丢进其点数和对应的桶里（需要6～36的31个桶）。最后，每个桶里的情况个数/6^6即其出现的概率。

这是一种不错的思路，如果从点数之和入手那很可能陷入很复杂的计算，因为点数6只有1种，点数7则可能有6种，点数8点数9呢？其复杂度会随着点数往中间挪而骤增。而且如果骰子不是6颗而是100颗呢？

代码实现

从思索的结论看，其实我们代码要做的就只是一个遍历而已。

那么，如何遍历这6^n 种情况？6^n 表示n颗骰子出现的情况，其无非就是第n颗骰子出现的6种情况与n-1颗骰子出现的6^(n-1) 种情况的匹配。所以我们需要考虑递归，让6^n 变成6^(n-1) ... 直到6^0 。

因此，该方法的构建应该是这样的：

    public static void getDiceSum(
            int oldSum,
            int remainDiceCount,
            Map<Integer, Integer> sumMap) {
    }

oldSum用于记录前面骰子的和，remainDiceCount表示还有多少颗骰子没有加入计算，sumMap用于存储最后每种和出现的次数。

最终的Java代码如下：

    public static void getDiceSum(
            int oldSum,
            int remainDiceCount,
            Map<Integer, Integer> sumMap) {
        if (remainDiceCount == 0)
            return;
        for (int num = 1; num <= 6; num++) {
            if (remainDiceCount == 1) {
                int key = oldSum + num;
                Integer oldValue = sumMap.get(key);
                if (oldValue == null)
                    oldValue = 0;
                sumMap.put(oldSum + num, ++oldValue);
            } else {
                getDiceSum(oldSum + num, remainDiceCount - 1, sumMap);
            }
        }
    }

实际上，这是一个flatmap的过程，从1个getDiceSum映射到6个getDiceSum，再映射到36个getDiceSum...当remainDiceCount==1的时候说明可以求和了，这时再将当前的这条（6^n 中的一条）的和次数加一丢进sumMap中。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018.11.03 ，如有侵权请联系 cloudcommunity@tencent.com 删除

存储