专栏首页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中。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Android技术选型闲聊

    技术好只能保证做出来的App不烂,品味好了才能将有限的技术发挥到极致,将所做App提升一个档次。

    冰之角
  • Android水波动画帮助类,一行代码实现View显示/隐藏/startActivity特效(0.3.1)

    So,你可以如下compile该library了,也可以把这个类CircularAnim拷贝到项目里去。

    冰之角
  • 一个随机播放的算法II

    音乐时光? 骑着车,戴着耳机,播放列表里有几首歌。 突然,很想听《且听风吟》,但是不想掏出手机,于是一路双击耳机播放键切歌。 emmm,下面是切过的歌:

    冰之角
  • Python学习笔记(三)-数据类型

    张树臣
  • LintCode 寻找丢失的数 II代码

    给一个由 1 - n 的整数随机组成的一个字符串序列,其中丢失了一个整数,请找到它。

    desperate633
  • 浅尝一个排程引擎Optaplanner - 前序

        当码农有10多年了,由建筑行业软件,各种MIS,通用物流定制平台,CCTV客户端(是闭路电视,不是央视喔)啥都做过。最后小试一下创业,不过那都是闹着玩的...

    Kent Zhang
  • Python学习之文件操作

    py3study
  • kubernetes集群搭建(7):常见问题及处理

    2.问题现象:错误提示中有证书错误,certificate  xxxx,在node节点上执行

    肖哥哥
  • 400 FPS!CenterFace+TensorRT部署人脸和关键点检测

    本文作者:yanwan https://zhuanlan.zhihu.com/p/106774468 本文系原作者投稿,欢迎大家分享优质工作

    Amusi
  • 玩转分布式事务系列 - 可靠消息解决跨库转账问题

    第7步执行成功之后,网络出问题了,第8步会提交失败,此时的结果是:A库资金减少了100,B库资金却没有增加;这是一个网络问题导致了我们业务失败了,网络因素是程序...

    路人甲Java

扫码关注云+社区

领取腾讯云代金券