前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2021-08-17:谷歌面试题扩展版,面值为1~N的牌组成一组,每次你从组里等概率的抽出1~N中的一张,下次抽会换一个新的组,

2021-08-17:谷歌面试题扩展版,面值为1~N的牌组成一组,每次你从组里等概率的抽出1~N中的一张,下次抽会换一个新的组,

作者头像
福大大架构师每日一题
发布2021-09-03 15:20:37
4340
发布2021-09-03 15:20:37
举报

2021-08-17:谷歌面试题扩展版,面值为1~N的牌组成一组,每次你从组里等概率的抽出1~N中的一张,下次抽会换一个新的组,有无限组,当累加和<a时,你将一直抽牌,当累加和>=a且<b时,你将获胜,当累加和>=b时,你将失败。返回获胜的概率,给定的参数为N,a,b。

福大大 答案2021-08-17:

递归。一张牌一张牌累加,概率累加即可。

时间复杂度:O(N*b)。

代码用golang编写。代码如下:

代码语言:javascript
复制
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代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class13/Code01_NCardsABWin.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档