【刷题篇】抽牌获胜的概率-Toy模板网

这篇具有很好参考价值的文章主要介绍了【刷题篇】抽牌获胜的概率。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目

谷歌面试题

将面值1-N的牌组成一组
每次从组中等概率的抽出1-N中的一张
下次抽会换一个新的组，有无限组
当抽到的牌累加和<a时，将一直抽牌
当累加和>=a且<b时，你将获胜
当累加和>=b时，你将失败
给定的参数N,a，b 返回获胜的概率

二、题解

核心思想
数字为1-n的扑克牌组成一组,每次从1-n的一组牌中等概率抽中一张牌,下一次抽会从另,动态规划,算法,leetcode

2.1 递归

public static double f2(int N,int a,int b){
    if(N < 1 || a >= b || a < 0){
        return 0.0;
    }
    if(b-a>=N){
        return 1.0;
    }
    return p2(0,N,a,b);
}
//cur 表示目前累加和
    public static double p2(int cur,int N,int a,int b){
        if(cur>=a&&cur<b){
            return 1.0;
        }
        if(cur>=b){
            return 0.0;
        }
        double w=0.0;
        for (int i = 1; i <=N ; i++) {
            w+=p2(cur+i,N,a,b);
        }
        return w/N;
    }

2.2 优化递归

优化递归函数中的for循环, 因为计算累加和为cur的获胜概率的时候，需要通过for循环枚举，我们想做的是优化这个循环过程
数字为1-n的扑克牌组成一组,每次从1-n的一组牌中等概率抽中一张牌,下一次抽会从另,动态规划,算法,leetcode

 public static double f3(int N,int a,int b){
        if(N < 1 || a >= b || a < 0){
            return 0.0;
        }
        if(b-a>=N){
            return 1.0;
        }
        return p3(0,N,a,b);
    }
    public static double p3(int cur,  int N,int a,int b){
        if(cur>=a&&cur<b){
            return 1.0;
        }
        if(cur>=b){
            return 0.0;
        }
        if(cur==a-1){
            return 1.0*(b-a)/N;
        }
        double w=p3(cur+1,N,a,b)+p3(cur+1,N,a,b)*N;
        if(cur+1+N<b){
            w-=p3(cur+N+1,N,a,b);
        }
        return w/N;
    }

2.3 动态规划

将2.2 的代码改成动态规划即可文章来源地址https://www.toymoban.com/news/detail-736898.html

 public static double f4(int N,int a,int b){
        if(N < 1 || a >= b || a < 0){
            return 0.0;
        }
        if(b-a>=N){
            return 1.0;
        }
        double[] dp=new double[b];
        for (int i = a; i <b ; i++) {
            dp[i]=1.0;
        }
        if(a-1>=0){
            dp[a-1]=1.0*(b-a)/N;
        }
        for (int cur = a-2; cur >=0 ; cur--) {
            double w = dp[cur + 1] + dp[cur + 1] * N;
            if (cur + 1 + N < b) {
                w -= dp[cur + 1 + N];
            }
            dp[cur] = w / N;
        }
        return dp[0];
    }