【刷题篇】抽牌获胜的概率

一、题目

谷歌面试题

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

二、题解

核心思想

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循环枚举，我们想做的是优化这个循环过程

 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 的代码改成动态规划即可

 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];
    }