


2009年06月13日 4:23 下午
鱼儿前天贴了一批Google面试题,最后一道是经典的“海盗分金币”的对弈问题。原题如下:
有5个海盗,按照等级从5到1排列。最大的海盗有权提议他们如何分享100枚金币。但其他人要对此表决,如果多数反对,那他就会被杀死。他应该提出怎样的方案,既让自己拿到尽可能多的金币又不会被杀死?(提示:有一个海盗能拿到98%的金币)
我的解法基于以下的假定:
- 提议者也参与投票;
- “多数”即超过半数;在1-1,2-2的情况下,反对票未超过半数,提议就算通过。
我们来由简到繁地解这道题:
- 在只剩2个海盗(#4,#5)的情形下,#4无论怎样提议都能通过,因为他自己一票就够了,所以他可以拿走全部100枚金币。因为这个结果对#5最不利,所以如果他能得到1枚金币,就会阻止这样的情形出现;
- 也就是说当只剩3个海盗(#3,#4,#5)的时候,#3只要提议给#5分1枚,自己拿99枚,其提议就会通过。这个结果对#4最不利,所以如果他能得到1枚金币,就会阻止这样的情形出现;
- 也就是说当只剩4个海盗(#2,#3,#4,#5)的时候,#2只要提议给#4分1枚,自己拿99枚,其提议就会通过(#2,#4的两票赞成 vs #3,#5两票反对)。这个结果对#3,#5最不利,所以只要他们每个人能得到1枚金币,就会阻止这样的情形出现。
- 于是#1的难题就解决了,他可以提议自己拿98枚,余下两枚分给#3,#5一人一块,#2,#4空手,他的提议就有3票赞成可以通过。
Popularity: 1%





〖匿名游客〗回复:《ZT 胡锦涛自己的贪腐问题》
〖匿名游客〗回复:《ZT 胡锦涛自己的贪腐问题》
〖过客〗回复:《ZT 胡锦涛自己的贪腐问题》
〖djung〗回复:《ZT 胡锦涛自己的贪腐问题》
〖过客〗回复:《ZT 胡锦涛自己的贪腐问题》
〖真反腐败,不反中共流氓党行吗?〗回复:《ZT 胡锦涛自己的贪腐问题》
〖施化〗回复:《ZT 胡锦涛自己的贪腐问题》
〖匿名游客〗回复:《ZT 胡锦涛自己的贪腐问题》

回复: 《这个厕所怎么了?》
回复: 《只見前三十年,不見後三十年?》
回复: 《黄金突破1000美元后,石油向100美元进发,这一对组合拳将打垮联储局》
回复: 《媒体能否不用“人蛇”这么恶毒的字眼?》
回复: 《黄金突破1000美元后,石油向100美元进发,这一对组合拳将打垮联储局》
回复: 《黄金突破1000美元后,石油向100美元进发,这一对组合拳将打垮联储局》
回复: 《中国教育的问题在哪里 – 评温家宝对教育的评论》
回复: 《唱反调还是唱黄色小调?—把”我要唱点反调“的留言拿出来示众》

链接表
还真有人不依不挠把此题做成哥德巴赫猜想的?
Google要是指望来面试的人都需要用人脑做复杂的“递归”(其实更像Fortran的goto语句),那也太无聊了。
此题应该是在保存自己性命的情况下利益的最大化。
只关注利益最大化的解法都忽略了“如果多数反对,那他就会被杀死”这一性命攸关的主要矛盾。
注意是“被杀死”而不仅仅是“出局”!!每个提议的海盗都有个生死的槛要过。
#5因为不可能死而处在最强势的位子上,把他当成弱势是彻底忽略主要矛盾的结果。
#4最应该怕死。
#3因1-1的平衡而渔翁得利,也不太需要怕死。
#2也是很容易被#3和#5搞死的。
#1因2-2的平衡又渔翁得利了。
此题很elegant,也包含了简单的递归,是面试的好题目。
但如果把生死的因素去掉,则会变得很繁琐,决不适合做一般的面试题。
复杂的递归是留给愚笨而又勤快的电脑做的。
这是我最后一次在此发言。