微软面试题五个囚犯 一道真正难倒亿人的智力题,这是微软的面试题。
五个囚犯 一道真正难倒亿人的智力题,这是微软的面试题。
个囚犯，分别按1-5号在装有100颗绿豆的麻袋抓绿豆，规定每人至少抓一颗，而抓得最多和最少的人将被处死，而且，他们之间不能交流，但在抓的时候，可以摸出剩下的豆子数。问他们中谁的存活机率最大？？提示：
1，他们都是很聪明的人
2，他们的原则是先求保命，再去多杀人
3，100颗不必都分完
4，若有重复的情况，则也算最大或最小，一并处死
[解决办法]
1.这一题里，第i个人拿的时候，都会计算剩下的豆子数n，然后拿 (100-n)/i,取上界或者下界（四舍五入）
2.若第i个人发现(100-n)/i>20；就意味着有人拿超过20个，若他只拿20个，剩给第5个人拿的就一定不够20，第i个人得活。（1<i<5）
那个：
1. 第一个人不会拿超过20个。
因为若第一个人拿20+a个，第二个人一定会拿20个，第三，四个人发现(100-n)/i>20，也拿20个，那么第五个人只能拿20-a
1,5死。
因此可以不用考虑豆子不够的问题
2. 若第一个人拿i个，第二个人之有可能拿i+1或i-1 （i<=20）
假设第一个人拿i个，第二个人拿i+k(k>1),第三个人计算(100-n)/i>20 = i+k/2 ,那么他只需要拿 [i+k/2]下界个，就可以保证不死
由于不用考虑豆子不够的问题，第4，5个人也只需拿[i+k/2]下界，这时 1 2 死
3. 任何一个人都不会拿超过20个，
、、、、、、、、、、、、、、、、、、
因此这5个犯人最可能的情况是
第一个人拿 i个 （i<=20）
第二个人拿 i+1个 或 i-1个
第一个人拿的同一或同二
第一个人拿的同一或同二
第一个人拿的同一或同二
最后同归于尽
呵呵
[解决办法]
全部挂,第一个拿I颗.第2个人不会拿K(K-I>=2)颗,(因为如果那样的话3,4,5就可以拿中间的那个数)那只能紧挨着,那么第3个只能拿和第一个或第二个同样的数(不然中间就夹着一个数.4,5必然会拿那个数),这样下去只要没有自己去找死的最后5个囚犯所拿豆子的数目只有2种.全部枪毙.
就算第一轮死了俩,后面的3个也是同样的结果.
人就这样.自己活不了,大家都别活
[解决办法]
1.显然一号是不会拿超过20个的，因为超过20个的豆子一定会成为最多的那个，
2.显然他们拿豆子的个数一定会是连续连续的整数，否则后面的人会拿到前面的人中间的豆子数
有了这两个结论我们可以得到，5号囚犯是必死的，因为连续的整数中，他一定是最大或最小的那个数，
所以他在必死的情况下会去杀人，所以他会选择前面四个连续整数的中间的两个数字中的一个，和那个人一起死，
这时候就只有一个人活下来，再接下来4号囚犯知道5号囚犯会选择四个连续整数的中间的两个数字中的一个，
那么4号囚犯和5号囚犯一样的命运，4号囚犯也是必死，所以他也会多杀人，但是他的策略就是不定的了，
因为他采取的不同策略会影响5号囚犯的判断，致使还是有人会活下来，而1号2号囚犯是彼此等价的，因为他们是连续的两个整数，对于3号而言他不知道1号在前还是2号在前，所以1号和2号的存活概率最大，4，5必死
[解决办法]
4楼正解，以下是对4楼给出条件的证明
第一个人取值小于等于20就行，设为i，他知道第二个人选值为i+1或i-1，否则就会给第三个人带来优势而牺牲自己。
第二个人肯定是选i+1或i-1，如果第二个人取i+2或i-2，它会假设第三个人取中间值i+1，从而自己和一号会挂掉，因此排除选i+2或i-2.如果第二个人取i个，那就与第一个人一样了，这样一来他与第一个人所选之和为2i，他会猜出第三个人的最优选择也是i，这样大家都必死，他会避免这种情况。因此得出结论，他只可能选i+1或i-1个。
第三个人只知道前两个人的和值sum，sum/2可能为整数或小数。如果sum/2是整数，设t=sum/2，得到这个结果表明第一个人和第二个人都取t个或其中一个人取t+1另一个取t-1，这种情况下第三个人的最优选择是选t个，事实上这种情况不会发生因为第二个人会避免这种情况。如果sum为小数，表明道第二个人取了i+1或i-1个，对sum/2下取整为t，第三个人知道前两个家伙中肯定有一个取值大于等于t+1，另一个小于等于t，最保险的方法是选t或t+1个，若多余t+1个则选t+1的人有可能存活而自己成了最大值，若小于t则选t的可能存活而自己成了最小值。因此得出结论他所选必同于第一或第二人。
第四，第五以三类推.
