华为的一道面试题 求高手解答
5个高智商囚犯，分别按1-5号在装有100颗绿豆的麻袋面前站好，让他们按次序抓绿豆，规定每人至少要抓一颗，而抓得最多和最少的人将被处死，而且，他们之间不能交流，但在抓的时候，可以摸出剩下的豆子数量。问他们中谁的存活几率最大？
提示：
1，他们都是很聪明的人 ！
2，他们的原则是先求保命，再去多杀人 .
3，100颗不必都分完 .
4，若有重复的情况，则也算做是最大或最小的情况，一并处死
问题点数：0、回复次数：37Top
1 楼VivianSnow（Phoenix）回复于 2005-08-18 18:52:52 得分 0
第三个人存活几率最大Top
2 楼tufaqing（）回复于 2005-08-18 18:56:12 得分 0
最后一个人没有豆子抓了怎么办？Top
3 楼VivianSnow（Phoenix）回复于 2005-08-18 18:58:03 得分 0
题目可以理解成``必须保证后面每个人都可以抓到至少1粒豆子```
应该是第三个人``没错```Top
4 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-08-18 19:03:04 得分 0
早就发过了
怎么又出来了？？Top
5 楼xingbozy（3951263）回复于 2005-08-18 20:17:07 得分 0
不可能最后一个没有抓的,每个人必须<20粒,即为Ｎ粒，因为都是高智商,谁都怕死,不能大于平均数20,第二个能算出第一个,抓的肯定不能相同,所以剩下的如果是奇数，则最近的为Ｎ－２粒，如果为偶数则应为Ｎ－１粒，而第一位与第二位应该能算出第三位的结果（有种或两种），可是第四位为保全自身，只能选择前三位的平均数取整再减二,所以第二个人最坏,控制权最大,第三个人存活率应该最大!
这是本人自己的观点!请大家一起来讨论Top
6 楼xingbozy（3951263）回复于 2005-08-18 20:18:14 得分 0
有答案没?说答案吧?Top
7 楼AncientHouse（小胖）回复于 2005-08-18 20:39:41 得分 0
晕，好难的问题Top
8 楼t_y（逝去的帆）回复于 2005-08-18 20:43:54 得分 0
由于不可能都大于20，也不可能都小于20，第一个人抓20个就不会死了，除非大家想自杀，都抓20个Top
9 楼xingbozy（3951263）回复于 2005-08-18 20:48:39 得分 0
为什么不能小于20,第三个条件是100颗不必都分完!Top
10 楼t_y（逝去的帆）回复于 2005-08-18 20:48:57 得分 0
错了，不能都大于20，但是可以都小于20的，呵呵Top
11 楼henan_lujun（地平风线）回复于 2005-08-18 20:55:20 得分 0
有意思的，研究研究！Top
12 楼xsp919（末末）回复于 2005-08-19 09:32:44 得分 0
原本是第二个人或第三个人存活概率最大，但是大家都是最聪明的人，而且第五个是必死无疑，所以第五个肯定要拉一个垫背的，会抓一个中间数和其中的某一个一样。结果第一个最不容易死。Top
13 楼tianhxk（c++<>_JAVA(拒绝回答中文作为字段的问题)）回复于 2005-08-19 12:30:44 得分 0
假设第一个人抓n粒（当然这个家伙不是白痴（n<20)),第二个人抓的数目不可能让第三个人有选择中间值的可能（如果选择第三个人能选择中间值的话，第四个人和第五个人同样可以选择中间值，必死无疑），那么第二个人可能抓n-1,n+1粒。第三个人会做一个选择（他同样会取前面两个人的中间值）得到k=(2n-1)/2或者（2n+1)/2,但是对他来说，他得作出一个选择，是取k,还是k+1,不管怎么样，总得跟前面两个人中的一个人相同；同理，第四个人和第五个人也必须取中间值，结果他们没有一个人能活下来.
我觉得他们活下来得概率是一样的.Top
14 楼ilelf（獨毒）回复于 2005-08-19 12:49:13 得分 0
我个人感觉好象全部都没有活命的机会似的。
由于每个人都要选不大不小的数，所以他肯定要先算一下前面的人选的数的平均数。
假如ai为每个人选的颗数.
第三个人选的时候肯定先算是一下(a1+a2)/2,假如这个时候选出来的是整数的话，如第一个人和第二个人选的数之差大于等于2,那么第三个人肯定挑a3=(a1+a2)/2颗,[例如a1=6,a2=8,a3=7]后面的人全都挑一样的7，于是只有1,2死。
但由于大家都是联明人,2肯定不会这样做，因为那样他必死。
所以我觉得可能的情况是1选了数a1，二则选|a2-a1|=1的数,第三个人算(a1+a2)/2的时候得到一个中间数，于是他只能从a1,a2里随机挑一个，后面的类似，于是最后所有人挑的数不是a1,就是a2，所以全部都死。Top
15 楼yjy1001（蓝鲸--优秀得郁闷的鱼）回复于 2005-08-19 13:12:33 得分 0
如果都是聪明人 差不多如楼上分析
最后全部都要死
中间的相同，2头的因为是最大或最小，
最终全部都挂……Top
16 楼OMA_yudy（太平洋深深）回复于 2005-08-19 15:11:35 得分 0
聪明反被聪明误啊。可怜的五个白痴。Top
17 楼guangtougl（guangtougl）回复于 2005-08-19 15:39:35 得分 0
看楼上分析，好像全都的死Top
18 楼luojxun（）回复于 2005-08-19 16:01:04 得分 0
我想应该是第四个人,他可以保证自己的豆不会少与第五人,而且他可以知道前几位手里的斗的平均数.好的情况:如果前几位的平均数大于20,他只要保证自己的豆大于剩余的1/2多一颗,他肯定不会死.若小于20,将前三位拿的豆总数除以3余数为0,拿平均数,最坏是他们拿一样的数目豆,则5人都要死.否则他可活.余1,2则说明起码有一个人手里的豆大于平均数,也拿平均数.那他手里的豆将小于他们四位的平均数第五位绝对不会那大于平均数的豆,那要看他的运气了,下面的情况大家考虑吧.Top
19 楼luojxun（）回复于 2005-08-19 16:05:28 得分 0
第5位要保证自己不死的机会最大,他应该拿前四位手里豆数的平均数.Top
20 楼luojxun（）回复于 2005-08-19 16:48:36 得分 0
其实我的结果5人都没生存的机会.首先题目还得说明不能全拿,因为第一个的生存机会最小,若第一位全拿那5个都死,第一位没得选择,但他必考虑到最有利第四人的情况,他肯定不会拿大于20的豆,第二位知道第一为拿的豆数为了自己生存希望大些会拿比第一个人少一颗的豆,第三个出于以上考虑肯定拿与第二个人一样数的豆,第四照以上考虑拿的与第2,3人一样的数,第四个人也肯定那与第2,3,4人一样数的豆.那5人都死.Top
21 楼canoe_eyes（阿里）回复于 2005-08-19 17:00:16 得分 0
第一个Top
22 楼whzhhit（茫茫雪飘）回复于 2005-08-19 19:12:06 得分 0
我也觉得1，2，3，4，5都必死无疑，分析如下：
因为他们每个人都不会取大于20 的数，第一个当然也不会取19，也不会取1，2 ，否则他将是最小者。现1号在3到18之间随即取一个数，比如 12 吧，而2号只能选13或者11。因为他知道选相同者必死，所以不会选12，而且他也不愿意给别人取1，2号中间数的机会，因而也不会选其它的数，而选13和11的概率相同，现假定他选11吧，而3号会选10，11，12，13 。因为他知道：5号没有选择的机会而必死，根据“他们的原则是先求保命，再去多杀人”这一原则，5号一定会选择一个垫背的，而4号跟5号一样也没有选择的机会，他自己不能活命，当然也不会给别人活命的机会，所以它同样会选择一个垫背的。如果3号选择11或者12 ，他必死，而4号和5号会选择11或者12而且一定有一个会选择3号未选的那个数。如果3号选择10或者13，那4号和5号一定有一个人会选择前三个人的中间数12，而另一个人会在三个数中任选一个。
Top
23 楼whzhhit（茫茫雪飘）回复于 2005-08-19 19:13:54 得分 0
1号如果取19或者20，他将会是最大者Top
24 楼smile2005（）回复于 2005-08-19 23:06:19 得分 0
是概率问题吗?嘿嘿......
Top
25 楼yifeng4592（栋冬）回复于 2005-08-19 23:38:44 得分 0
这是一道for 的两层循环题吧Top
26 楼lanyus（）回复于 2005-08-19 23:59:37 得分 0
这五个人谁也没办法确定他拿的数量不是最大或者最小，因为这100个绿豆没有一个绝对的分法让自己知道是否不属于最大或者最小。
这五个聪明人最后拿的数量至少有四个应该是连续的数字，那么，当第一个人拿了之后，他的数字成为最大或者最小的概率是1/2*1/2*1/2*1/2，第二个人成为最大或者最小的概率是1/2*1/2*1/2，第三个人的概率是1/2*1/2。。。。。
所以最后成为最大或者最小的概率是第一个人最小，也就是说他的生存概率最大。Top
27 楼defyer007（深入浅出）回复于 2005-08-20 00:29:23 得分 0
看了楼上的各位解答，好象基本上都是考虑的一些特殊情况下的解，但是从概率与统计理论的角度来说，应该考虑所有的情况，然后统计结果，再看谁的生存概率最大，偶有两个想法：
１．用条件概率算，每颗豆子被取或不被取，概率分别为1/2，将每个人的取豆行为看成一个100重伯努力实验，再用条件概率的公式计算。
２．虽然有点笨，但偶觉得可以写个循环，先设n1,n2,n3,n4,n5，n1从1到96循环，n2从1到100-n1循环，n3从1到100-n1-n2循环，依次类推（上面是５个外层循环）然后在内层中判断去掉最大和最小的数（可以重复）将剩下的n(i)所对应的一个统计数组（假设为SurvivRate[i]，i=1,2,3,4,5）+1，表示增加它的存活概率；最后，SurvivRate数组中最大的那个数对应的下标号就是解了。
愚见:)Top
28 楼luojxun（）回复于 2005-08-20 08:30:43 得分 0
这种问题是无法用程序模拟的,据我所知还没谁可以写出模拟人的思维软件,也没那台电脑有这么高的智能.不用考虑太多的可能性.因为从第三人开始他拿前面人手里的豆数的平均数(取整数部分),则他手里的豆数大于一个人,小与另一人可能性最高.他必会如此选择.Top
29 楼sxinyying（水心云影！）回复于 2005-08-21 02:50:43 得分 0
我准备这几天都来这里了，虽然我不会Top
30 楼magic_laubj2008（C++初学者）回复于 2005-08-21 17:55:14 得分 0
好耐啦Top
31 楼whzhhit（茫茫雪飘）回复于 2005-08-25 14:59:16 得分 0
怎么没有人做了呢？？Top
32 楼caio0（戴 强）回复于 2005-08-26 14:45:01 得分 0
我觉得他们没一个能活
首先，第一个人抓的时候，或考虑到后面的人是怎么想的
也会考虑到后面的人想他是怎么想的，一直往下想下去，。。。。。
因为他们是一样的聪明，也都知道别人和他一样聪明
这样就会导致所有人抓的都一样。（如果有一个让自己存活下来的值）
这样他们存活的概率相同0。
这叫同生死，共命运。Top
33 楼caio0（戴 强）回复于 2005-08-26 15:00:09 得分 0
如果4个人分80颗怎么样呢？
如果三个人分60颗呢?(这个不用说了)Top
34 楼zyang（）回复于 2005-08-27 19:21:24 得分 0
说点搞笑的：至少抓一颗，可没说最多抓几颗。 100颗绿豆能有多少，第一个人全抓了得了，其他人 全枪毙。嘿嘿
Top
35 楼zyang（）回复于 2005-08-27 19:22:52 得分 0
哦，没注意，抓得最多也要死Top
36 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-08-27 21:09:50 得分 0
看看吧
早有人讨论过了
http://community.csdn.net/Expert/topic/4167/4167667.xml?temp=.0713312Top
37 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-08-27 21:11:01 得分 0
再贴一个类似的问题
[以下转帖]
海盗分金问题异调
这是一帮亡命之徒，在海上抢人钱财，夺人性命，干的是刀头上舔血的营生。在我们的印象中，他们一般都瞎一只眼，用条黑布或者讲究点的用个黑皮眼罩把坏眼遮上。他们还有在地下埋宝的好习惯，而且总要画上一张藏宝图，以方便后人掘取。不过大家是否知道，他们是世界上最民主的团体。参加海盗的都是桀骜不驯的汉子，是不愿听人命令的，船上平时一切事都由投票解决。船长的唯一特权，是有自己的一套餐具——可是在他不用时，其他海盗是可以借来用的。船上的唯一惩罚，就是被丢到海里去喂鱼。
现在船上有若干个海盗，要分抢来的若干枚金币。自然，这样的问题他们是由投票来解决的。投票的规则如下：先由最凶猛的海盗来提出分配方案，然后大家一人一票表决，如果有50%或以上的海盗同意这个方案，那么就以此方案分配，如果少于50%的海盗同意，那么这个提出方案的海盗就将被丢到海里去喂鱼，然后由剩下的海盗中最凶猛的那个海盗提出方案，依此类推。
我们先要对海盗们作一些假设。
1) 每个海盗的凶猛性都不同，而且所有海盗都知道别人的凶猛性，也就是说，每个海盗都知道自己和别人在这个提出方案的序列中的位置。另外，每个海盗的数学和逻辑都很好，而且很理智。最后，海盗间私底下的交易是不存在的，因为海盗除了自己谁都不相信。
2) 一枚金币是不能被分割的，不可以你半枚我半枚。
3) 每个海盗当然不愿意自己被丢到海里去喂鱼，这是最重要的。
4) 每个海盗当然希望自己能得到尽可能多的金币。
5) 每个海盗都是现实主义者，如果在一个方案中他得到了1枚金币，而下一个方案中，他有两种可能，一种得到许多金币，一种得不到金币，他会同意目前这个方案，而不会有侥幸心理。总而言之，他们相信二鸟在林，不如一鸟在手。
6) 最后，每个海盗都很喜欢其他海盗被丢到海里去喂鱼。在不损害自己利益的前提下，他会尽可能投票让自己的同伴喂鱼。
现在，如果有10个海盗要分100枚金币，将会怎样？
要解决这类问题，我们总是从最后的情形向后推，这样我们就知道在最后这一步中什么是好的和坏的决定。然后运用这个知识，我们就可以得到最后第二步应该作怎样的决定，等等等等。要是直接就从开始入手解决问题，我们就很容易被这样的问题挡住去路：“要是我作这样的决定，下面一个海盗会怎么做？” 以这个思路，先考虑只有2个海盗的情况（所有其他的海盗都已经被丢到海里去喂鱼了）。记他们为P1和P2，其中P2比较凶猛。P2的最佳方案当然是：他自己得100枚金币，P1得0枚。投票时他自己的一票就足够50%了。 往前推一步。现在加一个更凶猛的海盗P3。P1知道——P3知道他知道——如果P3的方案被否决了，游戏就会只由P1和P2来继续，而P1就一枚金币也得不到。所以P3知道，只要给P1一点点甜头，P1就会同意他的方案（当然，如果不给P1一点甜头，反正什么也得不到，P1宁可投票让P3去喂鱼）。所以P3的最佳方案是：P1得1枚，P2什么也得不到，P3得99枚。
P4的情况差不多。他只要得两票就可以了，给P2一枚金币就可以让他投票赞同这个方案，因为在接下来P3的方案中P2什么也得不到。P5也是相同的推理方法只不过他要说服他的两个同伴，于是他给每一个在P4方案中什么也得不到的P1和P3一枚金币，自己留下98枚。
依此类推，P10的最佳方案是：他自己得96枚，给每一个在P9方案中什么也得不到的P2，P4，P6和P8一枚金币。
下面是以上推理的一个表（Y表示同意，N表示反对）：
P1 P2 0 100 N Y P1 P2 P3 1 0 99 Y N Y P1 P2 P3 P4 0 1 0 99 N Y N Y P1 P2 P3 P4 P5 1 0 1 0 98 Y N Y N Y …… P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 0 1 0 1 0 1 0 1 0 96 N Y N Y N Y N Y N Y
现在我们将海盗分金问题推广：
1) 改变一下规则，投票中方案必须得到超过50%的票数（只得到50%票数的方案的提出者也会被丢到海里去喂鱼），那么如何解决10个海盗分100枚金币的问题？
2) 不改变规则，如果让500个海盗分100枚金币，会发生什么？
3) 如果每个海盗都有1枚金币的储蓄，他可以把这枚金币用在分配方案中，如果他被丢到海里去喂鱼，那么他的储蓄将被并在要分配的金币堆中，这时候又怎样？
通过对规则的细小改变，海盗分金问题可以有许多变化，但是最有趣的大概是1)和2)（规则仍为50%票数即可）的情况，本帖只对这两种情况进行讨论。
首先考虑1)。现在只有P1和P2的情形变得对P2其糟无比：1票是不够的，可是就算他把100枚金币都给P1，P1也照样会把他丢到海里去。可是P2很关键，因为如果P3进行分配方案的话，即使他一枚金币也不给P2，P2也会同意，这样一来P3就有P2这张铁票！P3的最佳方案就是：独吞100枚金币。
P4要3张票，而P3是一定反对他的，而如果不给P2一点甜头，P2也会反对，因为P2可以在P3的方案中得救，目前为什么不把P4丢到海里呢？所以要分别给P1和P2一枚金币，这样P4就有包括他自己1票的3票。P4的方案为：P1，P2每人1枚金币，他自己98枚。
P5的情况要复杂点，他也要3票。P4是会反对他的，所以不用给，给P3一枚金币就能使他支持自己的方案，因为在接下来的P4方案中他什么也得不到。问题是P1和P2：只要其中有一个支持就可以了。可是只给1枚金币是不行的，P4方案中他们一定有1枚金币可得，所以只要在他们中随便选一个，给2枚金币，另一个就对不起了，不给。这样P5的方案是：自己97枚，P3得1枚，P1或P2得2枚。
P6的方案建立在P5的上面，只要给每个P5方案中不得益的海盗1枚金币。要注意的是，P1和P2都应该看作在P5方案中不得益的：他们可能得2枚，可是也可能1枚不得，所以只要P6给他们1枚金币，根据“二鸟在林，不如一鸟在手“的原则，就可以让他们支持P6的方案。所以P6的方案是唯一的：P1，P2，P4每人1枚金币，P6自己拿97枚。
这样继续下去，P9的方案是：P3，P5，P7每人1枚金币，然后在P1，P2，P4，P6中任选一人给2枚金币，P9自己得95枚。最后，P10的方案是唯一的：P1，P2，P4，P6，P8每人1枚金币，P10自己得95枚。 2)是最有趣的（提醒：我们回到50%票即可的规则）。原题解中的推理过程直到200个海盗都是成立的：P200给每个偶数号的海盗1枚金币，包括他自己，其他海盗什么也得不到。从P201开始，继续推理就变得有点困难了：P201为了不被丢到海里去，必须什么也不留给自己，而给从P1到P199中所有奇数号海盗每人1枚金币，从而争取到100票，加上他自己1票，逃过一劫。P202也什么都得不到，他必须用这100枚金币买通100个从P201的方案中什么也得不到的海盗，要注意到现在这个方案不是唯一的：P201的方案中得不到金币的海盗是所有奇数号的海盗，有101个（包括P201），所以有101种方案。
P203必须得到102票，除了自己的1票外，他只有100枚金币，所以只能买到100票，所以可怜的家伙就被丢到海里喂鱼了。但是，P203是个很重要的角色，因为P204知道如果自己的方案不被通过，P203也一样会完蛋，所以他有P203的一张铁票。所以P204可以大出一口气：他自己一票，加上P203一票，然后加上用100枚金币买的确100票，他就得救了！100个有幸得到1枚金币的海盗，可以是P1到P202中任何100个：因为其中的偶数号的从P202的方案中什么也得不到，如果P204给他们中某个海盗1枚金币，这个海盗一定会赞同这个方案；而编号为奇数的海盗呢，只是有可能从P202的方案中得益罢了（可能性为100/101），所以根据“二鸟在林，不如一鸟在手“的原则，如果能得到1枚金币，他也会赞同这个方案。
接下去P205是不能把希望放在P203和P204这两张票上的，因为就算他被丢到海里去，P203和P204还可以通过P204的方案机会活下来。P206虽然可以靠P205的铁票，加上自己1票和100枚金币搞到的100票，只有102票，所以他也被丢到海里喂鱼。P207好不了多少，他需要104票，而他自己以及P205和P206的铁票加上100枚金币搞到的100票只有103票——只好下海。
P208运气比较好，他同样也要104票，可是P205，P206，P207都会投票赞成他的方案！加上他自己的1票和买来的100票，他终于逃脱了做鱼食的命运。
这样我们就有了一种可以一直推下去的新逻辑。海盗可以什么也不留给自己，买上100票，然后依靠一部分一定会被丢下海的海盗的铁票，从而让自己的方案通过。有这样运气的海盗分别是P201，P202，P204，P208，P216，P232，P264，P328和P456……我们看到这样的号码是200加上一个2的次幂。 哪些海盗是受益者呢，显然铁票是不用（不能）给金币的。所以只有上一个幸运号码及他以前的那些海盗才有可能得到1枚金币。于是我们得到500海盗分100枚金币的结论是：前44个最凶猛的海盗被丢进海里，然后P456给P1到P328中的100个海盗每人1枚金币。
就这样，最凶猛的海盗被丢进海里，而比较凶猛的什么也得不到，而只有最温柔的那些海盗，才有可能得到1枚金币。正如《马太福音》所说：“温柔的人有福了，因为他们必承受地土！”
Top
