微软的有意思的招聘题

接地者

微软的有意思的招聘题

1、海盗分金
5个海盗抢到了100颗宝石，每一颗都一样的大小和价值连城。
他们决定这么分：
1。抽签决定自己的号码（1，2，3，4，5）
2。首先，由1号提出分配方案，然后大家5人进行表决，当且仅当达到半数以上的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
3。如果1号死后，再由2号提出分配方案，然后大家4人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
4。以此类推
条件：

每个海盗都是很聪明的人，都能很理智的判断得失，从而做出选择。
问题：
最后的分配结果如何？

通天雷神

 原题：  
  5个海盗抢到了100颗宝石，每一颗都一样的大小和价值连城。  
  他们决定这么分：  
  1。抽签决定自己的号码（1，2，3，4，5）  
  2。首先，由1号提出分配方案，然后大家5人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。  
  3。如果1号死后，再由2号提出分配方案，然后大家4人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。  
  4。以此类推  
  条件：  
  每个海盗都是很聪明的人，都能很理智的判断得失，从而做出选择。  
  在不影响自己利益的情况下，强盗乐于看到别人死掉。  
  问题：  
  最后的分配结果如何?      
     
  答案：  
  100  
  0，100  
  1，0，99  
  0，1，0，99  
  ....  
  关键是在前面一个“被认可方案”选取足够的人，并让他们得更多的利益就行了。  
  到200人以后，金币已经不够分了，所以第202个人必死，所以为了不轮到自己提方案，后面的说什麽她都同意，于是203个人可活，依次类推，第201加2的整次幂的人可活。  
   
  新问题：对于“超过半数”很多人理解为绝对的大于，不包括等于，于是，这就变成了一个困难的多的问题：  
  100  
  100，-1       （没有方案，不妨这样记)  
  0，0，100  
  1，1，0，98  
  2，0，1，0，97或   0，2，1，0，97  
  由上面两种方案，得出每人在第5个人提方案时，所得金币的期望值：  
  1，1，1，0，97  
  继续，从3个1中选2，有3种选法，期望值为  
  4/3，4/3，4/3，1，0，95  
  第7个海盗肯定会给第5个海盗一个金币，不给第6个海盗，再从1，2，3，4中选2个人，每人给2个金币  
  现在，深刻的问题出现了：  
  怎麽从他们中选？  
  如果怎麽选都和她本身利益无关的话，可以随机选。  
  可是，这四个人是不同的，分成两类：4/3和1，如果根据公平原则，4/3类的期望大，应该几率大才对！  
  这和第7个人有什麽关系呢？  
  因为第七个人在第8，9，10...号做方案时，也会被相应的归类，他当然希望自己所属的类会有大一点的几率，而各强盗之间不能私下交流，所以，如果大家都遵从一个“共同获利”的规范来做任何选择问题时，个人会间接获利！（有点象纳什的理论）  
   
  于是，道德产生了.....  
     
  引发的两个问题：  
  1、公共约定可以统过纯粹的推理（无交流），而产生吗？  
  2、所谓每个强盗都足够聪明，关键是这种深度推理的层次会不会是无穷阶的？

hyjappllo

这个问题是硕士一级的水平，防雷领域学强电当然回答不出

hyjappllo

学计算机的就知道这一道题，这是博弈论的题：海盗分金，弱者获利。书上有的。学电子和自控的，学了《遗传算法》的话，书里也有博弈论的应用

cpu50436

呵呵呵~~~~~（傻了的笑）^^

焱

我可没你这么傻。：）

cpu50436

要不然乘别人抢分的当儿把船凿个大大的洞，一起沉了，等若干年后再让其他人来寻宝：）造福下一代，哈哈：）

接地者

呵呵
不得其门

cpu50436

把金子和宝石再仍进海里，然后每个人原地自转3百圈，再下海去捞，谁捞着归谁：）

焱

不会吧？
我都这么慷慨了，他们还想怎么着？！