有一位朋友突然问我一道连胜的概率问题，自己也研究一下，和大家分享，同时记录一下。

问题描述

小明每天玩10盘王者荣耀，且胜负完全随机（胜率50%），请用JS写一个模拟算法，算出小明今天获得过至少一次3连胜的概率，并指出该算法的时间与空间复杂度。

解题思路

枚举找规律

眼看10盘太多了，我们来看看3盘，4盘，5盘等，看看有什么规律。随着我们学习计算机，其实计算机所有数据都用0和1组成，这里个人用1代表胜，0代表负，胜率50%也就是
因此，3盘有三连胜概率如下
111 == 1/2^3=0.125
4盘三连胜以上概率如下
1110 == 1/2^4
0111 == 1/2^4
1111 == 1/2^4
sum = 1/2^34+ 1/2^4 + 1/2^4 = 3/2^3=0.1875
5盘三连胜的情况及概率
1110* == 1/2^4
01110 == 1/2^5
*0111 == 1/2^4
11110 == 1/2^5
01111 == 1/2^5
11111 == 1/2^5
sum = 1/2^4 + 1/2^5 + 1/2^4 + 1/2^5 + 1/2^5 + 1/2^5= 1/2^4 * 2+ 1/2^5 * 4 =0.25

枚举推演

我们知道，连胜就是1，也就是多少两胜，就是多少个一并行移动，但是，防止超过本身连胜，所以旁边的连胜得为0.也就是10盘三两胜总数为
十个未知数**********
三连胜推理，01110五个数字，从左移位，总移动个数（10-5）+1会有四种，加上边界问题有两种1110，0111，也就是三连胜概率 1/2^5 * (10-5+1)+2/2^4
四连胜类推 1/2^6 * (10-6+1)+2/2^5
因此类推 把上面设置为N盘，success连胜概率
${\sum }_{i=success}^N$ (1/2^(i+2) * (N-(i+2)+1)+2 * 1/(i+1)) + 1/2^N
用计算机实现如下图

 /**
     * @param success 连胜次数
     * @param count   总局数, count>m+2
     * @return
     */
    public static double rateResult(int success, int count) {
        if (count < success) {
            return 0;
        }
        double sum = 0;
        for (int i = success; i < count; i++) {
            sum += Math.pow(1.0 / 2, i + 2) * (count - i - 1) + Math.pow(1.0 / 2, i + 1) * 2; // i-2连胜概率
        }
        sum += Math.pow(1.0 / 2, count); // n连胜的该路
        return sum;
    }

验证推理

由上枚举推演由两组数据，我们来验证一下

public static void main(String[] args) {
        System.out.println(rateResult(3, 3));  // 0.125
        System.out.println(rateResult(3, 4)); // 0.1875
        System.out.println(rateResult(3, 5)); // 0.25
}

也就是说条件满足，对于有没有错，还有待研究

算法优化

N盘，连胜为success，胜概率为rate，算法优化。

  /**
     * @param success 连胜次数
     * @param count   总局数
     * @param rate 连胜概率
     * @return
     */
    public static double rateResult(int success, int count, double rate) {
        if (count < success) {
            return 0;
        }
        double sum = 0;
        for (int i = success; i < count; i++) {
            sum += Math.pow((1 - rate), 2) * Math.pow(rate, i) * (count - i - 1) + (1 - rate) * Math.pow(rate, i) * 2; // i-2连胜概率
        }
        sum += Math.pow(1.0 / 2, count); // n连胜的该路
        return sum;
    }

实际应用

问题来了，我们怎样才能玩游戏玩上王者呢？
1.比如平常玩游戏，如果胜负均衡，基本会出现连胜三局以上要玩多少局才出现。

   int N = 3;
        while (true) {
            if (rateResult(3, N++, 0.5) > 1) {
                System.out.println(--N);
                break;
            }
        }

输出18，也就是我们打18局游戏一般就会有连续三胜的出现。

2.我们进一步推算演变，如果连胜10局，到底要打多少局王者游戏呢？

   int N = 3;
        while (true) {
            if (rateResult(10, N++, 0.5) > 1) {
                System.out.println(--N);
                break;
            }
        }

结果为2057，是不是很惊讶，凡是连胜超过15局的人，肯定玩不少游戏。
3. 继续演练，但是游戏设计规则，其实基本游戏都是按照50%根据玩家的平常总结能力来综合评分的。当然人为因素很多，其实还有手感，不同手机或者不同时间给人的玩游戏状态不一样，这时我们可以动态产生优胜率因子rate，此外，游戏潜意识设计规则不可能让玩家一直没法上段位，因此出现奖励分数的问题，也就是输了也奖励积分，只要你玩到一定局数，将会可能打上王者，除非你的智慧在这个段位的人之下，否则基本上均可上王者。至于这个算法如何统计就比较复杂了。因为上一个段位你的胜利rate就会地一点，要再次夺取分数，你就需要不断学习和提升自己。这就是游戏潜意识规则。