2021-08-17：谷歌面试题扩展版，面值为1~N的牌组成一组，每次你从组里等概率的抽出1~N中的一张，下次抽会换一个新的组，有无限组，当累加和<a时，你将一直抽牌，当累加和>=a且<b时，你将获胜，当累加和>=b时，你将失败。返回获胜的概率，给定的参数为N，a，b。
福大大 答案2021-08-17：
递归。一张牌一张牌累加，概率累加即可。
时间复杂度：O(N*b)。
代码用golang编写。代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
ret := f2(5, 2, 3)
fmt.Println(ret)
}
func f1() float64 {
return p1(0)
}
// 游戏的规则，如上
// 当你来到cur这个累加和的时候，获胜概率是多少返回！
func p1(cur int) float64 {
if cur >= 17 && cur < 21 {
return 1.0
}
if cur >= 21 {
return 0.0
}
w := 0.0
for i := 1; i <= 10; i {
w = p1(cur i)
}
return w / 10
}
// 谷歌面试题扩展版
// 面值为1~N的牌组成一组，
// 每次你从组里等概率的抽出1~N中的一张
// 下次抽会换一个新的组，有无限组
// 当累加和<a时，你将一直抽牌
// 当累加和>=a且<b时，你将获胜
// 当累加和>=b时，你将失败
// 返回获胜的概率，给定的参数为N，a，b
func f2(N int, a int, b int) float64 {
if N < 1 || a >= b || a < 0 || b < 0 {
return 0.0
}
if b-a >= N {
return 1.0
}
// 所有参数都合法，并且b-a < N
return p2(0, N, a, b)
}
// 游戏规则，如上，int N, int a, int b，固定参数！
// cur，目前到达了cur的累加和
// 返回赢的概率
func p2(cur int, N int, a int, b int) float64 {
if cur >= a && cur < b {
return 1.0
}
if cur >= b {
return 0.0
}
w := 0.0
for i := 1; i <= N; i {
w = p2(cur i, N, a, b)
}
return float64(w) / float64(N)
}
// f2的改进版本，用到了观察位置优化枚举的技巧
// 可以课上讲一下
func f3(N int, a int, b int) float64 {
if N < 1 || a >= b || a < 0 || b < 0 {
return 0.0
}
if b-a >= N {
return 1.0
}
return p3(0, N, a, b)
}
func p3(cur int, N int, a int, b int) float64 {
if cur >= a && cur < b {
return 1.0
}
if cur >= b {
return 0.0
}
if cur == a-1 {
return 1.0 * float64(b-a) / float64(N)
}
w := p3(cur 1, N, a, b) p3(cur 1, N, a, b)*float64(N)
if cur 1 N < b {
w -= p3(cur 1 N, N, a, b)
}
return float64(w) / float64(N)
}
// f3的改进版本的动态规划
// 可以课上讲一下
func f4(N int, a int, b int) float64 {
if N < 1 || a >= b || a < 0 || b < 0 {
return 0.0
}
if b-a >= N {
return 1.0
}
dp := make([]float64, b)
for i := a; i < b; i {
dp[i] = 1.0
}
if a-1 >= 0 {
dp[a-1] = 1.0 * float64(b-a) / float64(N)
}
for cur := a - 2; cur >= 0; cur-- {
w := dp[cur 1] dp[cur 1]*float64(N)
if cur 1 N < b {
w -= dp[cur 1 N]
}
dp[cur] = float64(w) / float64(N)
}
return dp[0]
}执行结果如下：
图片左神java代码
