微软经典面试题--海盗分宝石,20分钟给出答案即可获得年薪8万美金的职位
微软经典面试题--海盗分宝石,20分钟给出答案即可获得年薪8万美金的职位
微软经典面试题--海盗分宝石,20分钟给出答案即可获得年薪8万美金的职位 5个海盗抢到了100颗宝石，每一颗都一样的大小和价值连城，他们决定这分： 1. 抽签决定自己的号码（1，2，3，4，5） 2. 首先，由1号提出分配方案，然后大家5人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。 3. 如果1号死后，再由2号提出分配方案，然后大家4人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。 4. 以次类推...... 条件： 1.每个海盗都是极其聪明的人 2.每个海盗都是非常残忍的人 3.每个海盗都能明确的判断得失然后作出明智的选择问题： 第一个海盗提出怎样的分配方案才能够使自己的收益最大化
参考答案:我们从最后开始逆推：假定从只剩两名海盗（5号和4号）开始，此时根据当且仅当半数和超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。5号可以反对4号提出的任何分配方式，然后“独吞”100个宝石.4号海盗什么也得不到。
现在在加上3号海盗。4号海盗心里头很清楚，如果3号的方案通不过，那么最后只剩下2名海盗，而他将一无所得，这种情况已在上面分析过了。4号海盗也明白，5号是会完全理解这种形势的。因此，只要3号的分配方案能给4号一点甜头使他不至于空手而归，那么不论3号提出何种方案，4号都将投赞成票。于是3号决定给1号一点点“好处”，既然宝石不允许分割，那就是1颗宝石吧!这样3号提出的分配方案为：3号分得99颗宝石，5号一颗都没有，4号分得1颗宝石。
2号海盗的策略也差不多。他需要有50％的赞成票，因此必须找一人做同党。他可以给同党捞到的“好处”是1颗宝石，而他可以用它来贿赂5号海盗。因为如果2号的方案被否决而3号的方案得以通过，则5号海盗将一无所获，所以5号和2号是同一阵营的。故而，2号的分配方案应是：99颗宝石归自己，给5号1颗宝石，3号与4号一点好处也没有。在这儿有一点值得注意，2号贿赂4号是没有意义的，4号海盗肯定会乐滋滋地欣赏2号被抛人大海，因为3号当家后，他反正还是有1颗宝石可得。
5号海盗的策略有一些小小的变化。他需要有两名同党，才能使自己的方案得以通过。所以他提出的方案应是：97颗宝石归已，给3号一颗宝石，给4号或5号2颗宝石。