专栏名称: 算法与数学之美
从生活中挖掘数学之美,在实践中体验算法之奇,魅力旅程,从此开始!
目录
相关文章推荐
超级数学建模  ·  研究生和导师恋爱了,又分手了...发帖问课题 ... ·  3 天前  
超级数学建模  ·  去世921年,苏东坡依旧是全国豁达之极的男人! ·  2 天前  
超级数学建模  ·  有它在,同龄人都老了,你还是绝色 ·  6 天前  
超级数学建模  ·  当导师加了研究生的微信好友…...哈哈哈哈哈 ... ·  1 周前  
51好读  ›  专栏  ›  算法与数学之美

策略问题与数学常数e

算法与数学之美  · 公众号  · 算法 数学  · 2016-09-26 22:33

正文

看了本微信号 9 22 日《 数学常数 e 的含义 》,也想到在一个场合很神秘地出现常数 e ,自然对数的底 e 确实是一个很神奇的数,正如圆周率 π一样,经常会出现在各种公式及问题的答案中。下面是一个通俗的策略问题,题目如下:

有一栋十层大楼,每层电梯门口都放着一颗钻石,你只知道每颗钻石大小不一,但是不知道钻石的重量分别是多少。假设你乘坐电梯从一楼到十楼,到达每层楼时,电梯门都会打开一次,你可以在任何一层楼选择一颗钻石(假设每层钻石的重量都在旁边标明),而且只能选择一次。问采取什么策略,才能以最大的概率拿到最大的那颗钻石?

题目的背景可以换成找工作、找对象等。用古典概率论知识解答如下:

策略一 :直接取第一层的钻石,取到最大钻石的概率为P1 = 0.1。

策略二

假设第1层不拿,从2层开始,采取如下策略:

(1) 如果第2层钻石比第1层大,则取该钻石,否则再上一层;

(2) 如果第3层钻石比前面2层都大,则取该钻石,否则再上一层;

(3) 循环以上步骤;如果前9层都没有取到要求的钻石,则取第10层的钻石。

按照以上策略,分别在第2层、3层,……、10层取到最大钻石为互不相容事件,概率可以相加。下面分别计算其概率。

第2层取到最大钻石,即第1层不是最大钻石,第2层正好为最大钻石,概率为:


同理,第3层取到最大钻石,即前2层不含最大钻石,且前2层的最大钻石在第1层中,第3层正好为最大钻石,概率为:


……

第10层取到最大钻石,即前9层不含最大钻石,且前9层的最大钻石在第1层中,第10层正好为最大钻石,概率为:


于是采取该策略取得最大钻石的概率是:


策略三

假设前2层都不拿,从3层开始,采取如下策略:

(1) 如果第3层钻石比前面2层都大,则取该钻石,否则再上一层;

(2) 如果第4层钻石比前面3层都大,则取该钻石,否则再上一层;

(3) 循环以上步骤;如果前9层都没有取到要求的钻石,则取第10层的钻石。

同理,按照以上策略,分别在第3层、4层,……、10层取到最大钻石为互不相容事件,概率可以相加。下面分别计算其相应概率。

第3层取到最大钻石,即前两层不含最大钻石,第3层正好为最大钻石,概率为:


同理,第4层取到最大钻石,即前3层不含最大钻石,且前3层的最大钻石在前两层中,第4层正好为最大钻石,概率为:


…………

第10层取到最大钻石,即前9层不含最大钻石,且前9层的最大钻石在前两层中,第10层正好为最大钻石,概率为:


于是采取该策略取得最大钻石的概率是:


同理可以得到其它策略:

策略四 :假设前3层都不拿,从4层开始,采取类似的策略,取得最大钻石的概率是:


同理可以得到 策略五、六、七、八和九 ,它们取得最大钻石的概率分别是:

策略十 :假设前9层都不拿,直接取第10层的钻石,取得最大钻石的概率是
综上所述,可以看出策略四以最大的概率值0.399取到最大钻石,该策略最优。

上面的楼层只有十层,如果将楼层的层数推广到任意的n层,那么一般化的最大钻石问题的解答如下:

一共n层楼,假设前m层都不拿,从m + 1层开始,采取如下策略:

(1)  如果第m + 1层钻石比前面m层都大,则取该钻石,否则再上一层;

(2)  如果第m + 2层钻石比前面m + 1层都大,则取该钻石,否则再上一层;

(3)  循环以上步骤;如果到达第n - 1层都没有取到要求的钻石,则取第n层的钻石。

按照以上策略,分别在第m层、m + 1层,……、n层取到最大钻石为互不相容事件,概率可以相加。下面分别计算其相应概率。

第m + 1层取到最大钻石,即前m层不含最大钻石,第m + 1层正好为最大钻石,概率为:







请到「今天看啥」查看全文