Google 电面 2月份

假设有10张牌分别是 1，2，3，4，5，6，7，8，9，10 。可以无限次取牌。你是dealer，给你一个数字，根据下面规则求busted的概率。
1. if the dealer's total is less than 17, the dealer draws another card。
2. if the dealer's t

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

mg src="static/image/smiley/QQ2011/4823172_m_4823174_4790.gif" smilieid="451" border="0" alt="" />。各位好运

我有点不动  pro(16) busted 概率是不是  16 +6，7，8，9，10  所以概率是 5/10 = 0.5?  是不是可以这样算?

vector<double> cal21(){
        vector<double> res(27, 0);
        for(int i = 1; i <= 10; i++)
                res[i] = 0.1;
        for(int i = 1; i < 17; i++){
                for(int j = 1; j <= 10; j++){
                        res[i+j] += res[i]*0.1;
                }
        }
        return res;
}

不知此法是否可行   

// Dynamic Programming
    public static double lostProb(int number) {
        if(number > 21) return 1.0;
        if(17 <= number && number <= 21) return 0.0;
        // the maximum number is 16 + 10 = 26
        // 17 ~ 21 wins, 22 ~ 26 lost
        // state: dp[i] = probability to reach number i
        double[] dp = new double[27];
        // initialize
        // note that number is less than 17
        for(int i = number + 1; i <= number + 10; i++) {
             dp[i] = 0.1;
        }
        // top-down function
        for(int i = number + 2; i <= 26; i++) {
            for(int j = Math.max(number + 1, i - 10); j < Math.min(i, 17); j++) {
                dp[i] += dp[j] * dp[i - j];
            }
        }
        // answer
        return dp[22] + dp[23] + dp[24] + dp[25] + dp[26];
    }
    //*******************************************************

谢谢楼主的帖子，别灰心，结果还没出的，祝你找到早日找到工作！！！

楼主，请问如果给的是15， 那么它busted的概率是什么啊。 dp[21 - 15] 吗？

我在想楼主的意思是不是base case是dp[22],dp[21]之类的，然后倒推出dp[16]dp[15],大概的思路就是dp[16]= dp[22]*0.1+dp[23]*0.1+dp[24]*0.1+...以此类推，然后推到0这样。

这一题之前的面经里出现过一次，我记得是最近一个月的

取一张牌之后，下次是从剩下9张里面取吗？还是每次取牌都有10种可能

这道题就是动态规划取算术平均把

不过更数学一点

虽然知道要用dp，但题目都得看老半天。。。

橙小夕 发表于 2018-2-11 08:29
我在想楼主的意思是不是base case是dp[22],dp[21]之类的，然后倒推出dp[16]dp[15],大概的思路就是dp[16]= d ...

是的。是要倒着推