五个强盗分100颗宝石

5个强盗分100颗宝石

面试题2：5个强盗分100颗宝石

5个海盗抢到了100颗宝石，每100颗宝石大小相同且价值连城，他们决定这么分：

（1）抽签决定自己的号码（1、2、3、4、5）。

（2）首先，由1号提出分配方案，然后大家5人进行表决，当超过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼。

（3）1号死后，再由2号提出分配方案，然后大家4人进行表决，当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。

（4）依此类推。

条件：每个海盗都是很聪明的人，都能够非常理智地判断得失，从而做出选择。并有以下的判断原则：

A：尽量保命。

B：尽量多得宝石。

C：尽量多杀人。

问题：最后的分配结果如何?

1．所涉及的知识点

递推法

分析法

2．分析问题

可用递推法来解决本题，由已知条件层层向下分析，要确保每一步都能准确无误。可能会有几个分支，应本着先易后难的原则，先从简单的分支入手。

如果从五个强盗开始考虑，非常不好入手，可以先考虑简单的情况，即海盗人数较少的情况，然后逐步复杂化，但是原理和简单情况还是相同的。

（1）当仅有二个海盗时，那么无论一号提出什么方案，二号都反对，那么一号肯定喂鱼，二号拿到所有的珠宝。

（2）当有三个海盗时，二号海盗肯定不希望一号海盗死，否则他就成了（1）中的一号。那么这里的一号就会想拿走所有的珠宝，因为他知道二号肯定支持他，因为如果二号反对，那么三号肯定也反对，一号喂鱼的话，那么二号也肯定喂鱼。所以一号拿走所有的珠宝。

（3）当有四个海盗时，一号必须要有三票赞成，而二号海盗肯定是反对的，因为当前的一号死后，他就成了（2）中的一号，所以当前的一号必须给三号海盗和四号海盗一个宝石，所以分配方案为一号98个，二号没有，三号四号各一个。在此不要忘记海盗判断原则C。

（4）当有五个海盗时，那么一号必须要有三票赞成，而根据（3）可知二号肯定反对他，因为他死了二号便成了（3）中的一号，可以拿98个宝石，所以不给二号。可以给三号1个宝石，三号便会支持他，否则三号将成为（3）中的二号，得不到宝石。给四号或五号中的一个两颗宝石，让他多于（3）中所得到的宝石数，另外一个不给，即可获得一个支持者。

3．答案

所以最后的方案为：

1号：97

2号：0

3号：1

4号：0

5号：2

或者：四号：2，五号：0

实现递推的方法的原则，就是由简单到复杂，逐步地深入分析，但是基本的原理却和简单情况非常相似。