首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

一路比较有意思的智力题

2013-02-02 
一道比较有意思的智力题某栋大楼共有10层,为了达到每层只能采用垂直电梯。现在每层的电梯出口放置一块大小

一道比较有意思的智力题
某栋大楼共有10层,为了达到每层只能采用垂直电梯。现在每层的电梯出口放置一块大小不等的石头(大小完全随机)。此时,元芳从大楼乘电梯向上寻找这10块石头中的最大的一块。元芳共有5次打开电梯门的机会。问元芳怎么找到最大的一块石头。
[解决办法]
这个模型变形于博弈论中的“秘书问题”,也曾是微软的应聘试题之一。

秘书问题是这样的:要聘请一名秘书,有n人来面试。每次面试一人,面试过后便要即时决定聘不聘他,如果当时决定不聘他,他便不会回来。面试时总能清楚了解求职者的适合程度,并能和之前的每个人作比较。问凭甚么策略,才使选得到最适合担任秘书的人的机率最大?

基本解决策略如下:对于某些整数r,其中。先面试首r人,都不聘请他们,在之后的n ? r人中,如果任何一人比之前面试的人都更佳,便聘请他。

r的值应该是甚么呢?答案是r≈n/e≈0.368n,其中e是自然对数的底。使用这个r的值的成功率是0.368n。

考虑到此题中n=10,求得r≈3.68,取其最近的整数为4。即:前4层都不选,但记下所见过的最大石头的大小,从第5层开始随便打开一层如果遇到比该石头大一个就选,否则就保留最大的即为最佳。
[解决办法]
应该是一个概率问题吧,要怎么利用这五次机会找打最大的那个石头的可能。如果五次都是随机打开,那找到最大那块的可能为 C(10 5) / (C(10 5) * C(5 1)) = 1 / 5 ;
如果只打开四次电梯的门然后回头来打开这四次中看见的最大的那块,这种情况找到最大的那块的可能为:
C(10 4) / (C(10 4)*C(4 1 )) = 1/4 ;
大概就是后一种方案比较好一点。
如果按照题意真正要找到最大的那块石头,也许就像9楼说的那样,先到达顶楼然后用石头砸了,不过这样也有种可能,要是10楼的石头是最小的,小小的那种,那要砸到什么时候

热点排行