189 8069 5689

阿里巴巴笔试题集第23题及分析-创新互联

题目:一个骰子, 6 面, 1 个面是 1 , 2 个面是 2 , 3 个面是 3 , 问平均掷多少次能使 1 、 2 、 3 都至少出现一次。

贵南网站建设公司创新互联,贵南网站设计制作,有大型网站制作公司丰富经验。已为贵南上千多家提供企业网站建设服务。企业网站搭建\成都外贸网站建设要多少钱,请找那个售后服务好的贵南做网站的公司定做!

方法: 面对面试概率题几乎屡试不爽的分叉树递归列方程法。

这是一个求数学期望的问题,最终是求 1 , 2 , 3 出现至少一次的最短长度的期望。

这样分叉树的每个节点是一个期望状态,而每个分叉是一次投掷结果。将后续期望出现 1 、 2 、 3 各至少一次的情形记作 L 123 (即题目所求),将后续期望出现 1 、 2 各至少一次( 3 无关)情形记作 L 12 ,而 1 至少一次( 2 , 3 无关)情形 L 1 ,其余数值符号类推,则树结构如下(列出 4 级结构已经足够):

阿里巴巴笔试题集第23题及分析

阿里巴巴笔试题集第23题及分析

接下来,就是要排出方程,因为一共 7 个未知数,如果排出 7 个线性方程就能解决问题。
在此我向大家推荐一个架构学习交流圈。交流学习企鹅群号:948368769(里面有大量的面试题及答案)里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化、分布式架构等这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

这方程组里的未知数对应上述的状态,而其数值则是一个对长度(投掷次数)的数学期望。

根据这个树状结构和其中的递归关系,这个方程组就是:

L 123   = p 1   (L 23 + 1) +   p 2   (L 13 +1) + p 3   (L 12   + 1) = p 1   L 23   + p 2   L 13 +  p 3   L 12   + 1

(以这个 L 123 为例,解释,投掷 1 的概率是 p 1 而由此得到的结果是需要期待后续 2 和 3 各至少出现一次,于是长度期望是 L 23 + 1 ,加 1 是因为投掷了一次,亦即即增进一级)

L 23   =   p 1   L 23   + p 2   L 3 +  p 3   L 2   + 1

L 13   =   p 1   L 3   + p 2   L 13 +  p 3   L 1   + 1

L 12   =   p 1   L 2   + p 2   L 1 +  p 3   L 12   + 1

L 1   = p 1+p 2   L 1 +  p 3   L 1   + 1

(这里实际上是   L 1   =p 1   ·1 + p 2   (L 1 + 1) + p 3   (L 1   + 1)   = p 2   L 1 +  p 3   L 1   + 1 ,因为对 L 1 情形,如果投了 1 就目的达到终止了)

L 2   = p 2+ p 1   L 2   +    p 3   L 2   + 1

L 3   = p 3+ p 1   L 3   + p 2   L 3 + 1

(以上一开始没注意,多加了悬空的概率项,故计算有误)

其中   p 1 , p 2   和   p 3 分别是掷出 1 , 2 和 3 的概率,即 1/6 , 1/3 , 1/2 。

于是求解这个方程,得到:

L 1   = 6 ,   L 2   = 3 ,   L 3   = 2

L 12   = 7 ,   L 13   = 13/2 ,   L 23   = 19/56

L 123   =   219/30 = 7.3  259/36 ~= 7.14

故以上如果没有计算错误,该题结果是,平均掷 7.3  7.14次可出现这些面值各至少一次。

【另一解法】感谢 4 楼 aaaxingruiaaa 同学提供的答案(指示器变量法),整理如下:

定义随机变量 X n ,其可能值为 0 或 1 ,其值为 1 表示 “ 前 n 次掷骰子, 1 , 2 , 3 没能都至少出现一次 ” 的事件,其值为 0 表示这个事件没有发生,即 “ 前 n 次掷骰子, 1 , 2 , 3 各至少出现一次 ” 。

令 p n 为 “ 掷 n 次骰子, 1 , 2 , 3 没能都至少出现一次 ” 的概率,所以显然 p n   = Pr{ X n =1} ,于是 p n   = 1·Pr{ X n =1} + 0·Pr{ X n =1} = E[ X n ] ,即这个随机变量的数学期望。

令随机变量 X 表示 1 , 2 , 3 刚好全部出现过需要的投掷次数。可见题目要求的就是 E[X] 。

关键等式: X =   Sigma (n=0 to   Inf;  X n )    (这里 Sigma 是求和号,求和范围是 n 从 0 到无穷大)

说明一下,等式两边都是随机变量,假设对于某个随机实例(例如,这里指一次具体的投掷序列),其对应事件是: “ 投了 K 次恰好 1 , 2 , 3 都出现了 ” ,于是等式左边显然等于 K ;而等式右边,对于 n < K ,由于这些项的对应定义事件发生了(即 1 , 2 , 3 没能出现),所以他们的实例值是 1 ,而对于 n⩾K ,则由于对应定义事件都没发生,实例值为 0 ,可见这个和也是 K 。故两侧相等。(为了达到这个相等关系,可以看出需要把 X 0 包含在内的必要性)

值得注意的是(但对于解这道题也可以不去注意,但注意一下有利于比较深入地理解),对 n < 3 , X n 显然恒为1。而对于 n⩾3 ,这些随机变量不是独立的。他们的相关性是不容易求出的,唯一容易知道的是,当序列中一个项为 0 时,其后的项均为 0 。好在对于这题我们不需要担忧这个相关性。

由于数学期望的加性与随机变量的相关性无关(这是数学期望一个很令人高兴的性质),所以即便这样, E[X] 也能容易求出:

E[X] =   Sigma (n=0 to Inf; E[ X n ] ) =  Sigma (n=0 to   Inf;   p n )

p n 的比较直观的求法也由 aaaxingruiaaa 同学 提供了,即所谓容斥原理。稍微解释一下,由于 p n 考虑的是 n 次投掷三者没有全部出现,于是就是其中两者出现或仅一者出现。假设单次投掷 1 , 2 和 3 出现的概率分别为: r 1 , r 2 和 r 3 。于是 ( r 1 + r 2 ) n 表征 n 次投掷只出现 1 或 2 的概率,这其中包括了出现全 1 和全 2 的情形,于是求 p n 可由这样的项求和并剔除重复计算的单面值情形,于是:

p n   = ( r 1 + r 2 ) n + ( r 1 + r 3 ) n + ( r 2 + r 3 ) n - r 1 n - r 2 n - r 3 n ,当 n > 0 ;   而 p 0   = 1 (由定义;同时也可以检验看出,这个 p n 在 n 为 1 和 2 的时候都是 1 )

于是由等比级数(等比数列求和)公式:

E[X] =   1 + Sigma (n=1 to Inf; ( r 1 + r 2 ) n + ( r 1 + r 3 ) n + ( r 2 + r 3 ) n - r 1 n - r 2 n - r 3 n = 1 + (1 -   r 3 ) /  r 3   + (1 -   r 2 ) /   r 2   + (1 -   r 1 ) /   r 1   -   r 1   / (1 -   r 1 ) -   r 2   / (1 -   r 2 ) - r 3   / (1 -   r 3 ) = 7.3

【程序仿真】

以下程序进行一千万轮投掷的仿真,结果基本在 7.3 周围。至此此题答案 7.3 毫无疑问了。

[csharp]view plaincopy

static   void  Main( string [] args)   
{  
    Random rand = new  Random();   
    int [] diceSurfaces =  new   int [6] { 1, 2, 2, 3, 3, 3 };    // 6个面    
    int  nRounds = 10000000;  // 投掷轮数    
    long  totalTimes = 0;     // 所有轮中投掷数加起来的总投掷次数    
    for  ( int  iRounds = 0; iRounds < nRounds; iRounds++)   
    {  
        bool [] occurred =  new   bool [3] {  false ,  false ,  false  };   // 各面值出现标记    
        int  sumPicked = 0;   // 出现不同面值个数    
        int  times = 0;   
        for  (; ; )   
        {  
            int  iSurface = rand.Next(6);   
            int  value = diceSurfaces[iSurface] - 1;   
            times++;  
            if  (!occurred[value])   
            {   // 出现新面值    
                occurred[value] = true ;   
                sumPicked++;  
                if  (sumPicked == occurred.Length)   
                {   // 全部出现,结束此轮    
                    break ;   
                }  
            }  
        }  
        totalTimes += times;  
    }  
    Console.WriteLine("average number of times = {0}" , (( double )totalTimes) / nRounds);   
}  

阿里巴巴笔试题集第23题及分析

创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。


新闻名称:阿里巴巴笔试题集第23题及分析-创新互联
URL地址:http://jkwzsj.com/article/dscgge.html

其他资讯