[brush title] probability of winning a draw

One 、 subject

Google interview questions

Will face value 1-N Your cards form a group
Each time from the group with medium probability 1-N One of them
Next time, I'll change to a new group , There are infinite groups
When the drawn cards add up <a when , Will draw all the time
When you add up and >=a And <b when , You will win
When you add up and >=b when , You will fail
Given parameters N,a,b Returns the probability of winning

Two 、 Answer key

The core idea

2.1 recursive

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  Indicates the current cumulative sum 
    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 Optimal recursive

Optimize... In recursive functions for loop , Because the cumulative sum is calculated as cur The probability of winning , Need to pass through for Loop enumeration , What we want to do is optimize the loop process

 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 Dynamic programming

take 2.2 Code can be changed to dynamic planning

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