微软经典面试题--海盗分宝石,20分钟给出答案即可获得年薪8万美金的职位

usoe 2017-2-20 2206

最新回复 (3)
  • fojj -2579400213秒前
    引用 2
    我们从最后开始逆推:假定从只剩两名海盗(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颗宝石。
  • towoy -2579400213秒前
    引用 3
      海盗1分98颗,海盗2分0颗,海盗3分1颗,海盗4分0颗,海盗5分1颗。 原因:   假设海盗1,2,3的意见都没有被采纳而推下海只剩下海盗4,5那么4独吞只要自己同意自己的分法就达成超过半数的人同意的这条规矩5必须接受。所以只要海盗3给自己分到1颗宝石也会同意3的分法而不会轮到4来分。海盗4知道3和5的计划后,如果让海盗3来分,自己肯定是1颗也分不到的,所以在海盗2分宝石的时候只要能分给4一颗宝石就回同意2的分法,所以海盗3和海盗2必然不会被推下海。但是轮到海盗2来分宝石的话3和5肯定分不到,因为海盗2分给自己99颗,给4一颗,两人都同意此分法就达成超过半数的人同意的这条规矩3和5必须接受,所以海盗3和海盗5必然会留住海盗1,不给2有分宝石的机会。由此得出海盗1只需给3和5各1颗自己得98颗,海盗3和5必定会同意。5人中在有3人同意的情况下海盗2和4只好空手而归。     抽到1的人看似最有可能被推下海,但是他利用自己先分的优势和规则的限制使挺而走险是自己获得了最大的利益。
  • jofh -2579400213秒前
    引用 4
      分配方案为:97,0,1,2,0 或 97,0,1,0,2。 从后向前推,如果1—3号海盗都喂了鲨鱼,只剩4号和5号的话,5号一定投反对票让4号喂鲨鱼,以独吞全部宝石。所以,4号唯有支持3号才能保命。 3号知道这一点,就会提出(100,0,0)的分配方案,对4号、5号一毛不拔而将全部宝石占为己有。因为他知道4号一无所有但还是会投赞成票,再加上自己一票他的方案即可通过。 不过,2号推知到3号的方案,就会提出(98,0,1,1)的方案,即放弃3号,而给予4号和5号各一颗宝石。由于该方案对于4号和5号来说比在3号分配时更为有利,他们将支持他不希望他出局而由3号来分配。 这样,2号将拿走98颗宝石。 不过,2号的方案会被1号所洞悉,1号将提出(97,0,1,2,0)或(97,0,1,0,2)的方案,即放弃2号,而给3号一颗宝石,同时给4号(或5号)2颗宝石。由于1号的解决方案对于3号和4号(或5号)来说,相比2号分配时更优,他们将投1号的赞成票,再加上1号自己的票,1号的方案通过,97颗宝石可以轻松落入囊中。这无疑是1号能够获取最大收益的方案了。
返回
发新帖