海盗问题 - 微软经典题

海盗问题 - 微软经典题接答：

记住了这一点，就可以知道我们的出发点应当是游戏进行到只剩两名海盗，即1号和2号的时候。这时最厉害的海盗是2号，而他的最佳分配方案是一目了然的：100块金子全归他一人所有，1号海盗什么也得不到。由于他自己肯定为这个方案投赞成票，这样就占了总数的50%，因此方案获得通过。

现在加上3号海盗。1号海盗知道，如果3号的方案被否决，那么最后将只剩2个海盗，而1号将肯定一无所获。此外，3号也明白1号了解这一形势。因此，只要3号的分配方案给1号一点甜头使他不至于空手而归，那么不论3号提出什么样的分配方案，1号都将投赞成票。因此，3号需要分出尽可能少的一点金子来贿赂1号海盗，这样就有了下面的分配方案：3号海盗分得99块金子，2号海盗一无所获，1号海盗得1块金子。

4号海盗的策略也差不多。他需要有50%的支持票，因此同3号一样也需再找一人做同党。他可以给同党的最低贿赂是1块金子，而他可以用这块金子来收买2号海盗。因为如果4号被否决而3号得以通过，则2号将一块也得不到。因此，4号的分配方案应是：99块金子归自己，3号一块也得不到，2号得1块金子，1号也是一块也得不到。

5号海盗的策略稍有不同。他需要收买另两名海盗，因此至少得用2块金子来贿赂，才能使自己的方案得到采纳。他的分配方案应该是：98块金子归自己，1块金子给3号，1块金子给1号。

这一分析过程可以照着上述思路继续进行下去。每个分配方案都是惟一确定的，它可以使提出该方案的海盗获得尽可能多的金子，同时又保证该方案肯定能通过。照这一模式进行下去，10号海盗提出的方案将是96块金子归他所有，其他编号为偶数的海盗各得1块金子，而编号为奇数的海盗则什么也得不到。这就解决了10名海盗的分配难题。

试想一下500名海盗分金会是怎样的结果呢？

下面是以上推理的一个表（Y表示同意，N表示反对）：

　　　P1　 P2
　　　0　　100
　　　N　　Y

　　　P1　 P2　P3
　　　1　　0　　99
　　　Y　　N　　Y

　　　P1　 P2　 P3　 P4
　　　0　　1　　 0　　99
　　　N　　Y　　 N　　Y

　　　P1　P2　 P3　 P4　 P5
　　　1　　0　　1　　0　　98
　　　Y　　N　　Y　　N　　Y

　　　……

　　　P1　 P2　 P3　 P4　 P5　 P6　 P7　 P8　 P9　 P10
　　　0　　 1　　0　　 1　　0　　1　　 0　　1　　 0　　96
　　　N　　 Y　　N　　Y　　N　　Y　　 N　　Y　　N　 　Y

由此类退。。。。。。。。

回到IQ题