算法-连胜概率问题-10把连胜3把概率

算法-连胜概率问题-10把连胜3把概率

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

问题描述

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

解题思路

1. 简单暴力 穷举法
2. 枚举找规律 这里采用穷举法(为了提高效率后期可以考虑“裁剪分支”)

10把游戏连续赢3把的概率，输赢概率百分之五十 可以将问题转化成一棵二叉树问题 问二叉树的根结点data为3，左子树根为赢，左子树根data为根结点data减去1,即为2,右子树根节点为输,右子树根data为重置为3，当某结点data为0时候，它以下所有结点data均为0 最终，求解叶子结点中 data为0与叶子总数的比例

public class DemoTest {
          
   

    private final static Integer INIT_WIN_COUNT=3;

    public static void main(String[] args) {
          
   
        execute(10,INIT_WIN_COUNT);
    }

    private static void execute(Integer level,Integer winCount){
          
   
        GameTree gameTree = buildTree(level, winCount);
        System.out.println("满足条件的次数是:"+zeroLeafCount(gameTree));
        System.out.println("概率是:"+1.0*zeroLeafCount(gameTree)+"/"+(int)Math.pow(2.0,(double)level));
        System.out.println("概率是:"+1.0*zeroLeafCount(gameTree)/(int)Math.pow(2.0,(double)level));
    }

    private static Integer zeroLeafCount=0;

    private static Integer zeroLeafCount(GameTree root){
          
   
        if (root.getLeft()==null&&root.getRight()==null){
          
   
            if (root.getData()==0){
          
   
                return 1;
            }else {
          
   
                return 0;
            }
        }
        return zeroLeafCount(root.getLeft())+zeroLeafCount(root.getRight());
    }

    /**
     * 生成树
     * @param level 多少把游戏
     * @param winCount 连续赢多少把
     * @return
     */
    private static GameTree buildTree(Integer level, Integer winCount){
          
   
        if (level<0){
          
   
            return null;
        }
        GameTree root=new GameTree();
        root.setData(winCount);
        if (winCount==0){
          
   
            GameTree left=buildTree(level-1,winCount);
            root.setLeft(left);
            GameTree right=buildTree(level-1,winCount);
            root.setRight(right);
        }else {
          
   
            GameTree left=buildTree(level-1,winCount-1);
            root.setLeft(left);
            GameTree right=buildTree(level-1,INIT_WIN_COUNT);
            root.setRight(right);
        }
        return root;
    }
}



@Data
@Accessors(chain = true)
class GameTree{
          
   
    private Integer data;
    private GameTree left;
    private GameTree right;
}

这里的算法还存在优化的点，使用算法导论的"裁剪法"，即可以考虑在中间某结点的data为0时候，不再往下生成二叉子树，也不再遍历，有兴趣的可以往下研究一下