MathProblem 85 Five pirates and a 1000 coins problem

本文主要是介绍MathProblem 85 Five pirates and a 1000 coins problem，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Five pirates have come across a treasure of 1000 coins. According to pirate rules the pirate of highest rank must make a suggestion on how to divide the money. If a majority agree to his suggestion then it is to be followed by all the pirates. However, if the suggestion does not get a majority approval then the suggesting pirate is thrown overboard, after which time the remaining pirate of highest rank then makes a suggestion under the same rules. This process repeats, if necessary, until only the pirate of lowest rank is left, in which case he would get everything. Any pirate may suggest any distribution, rank does not guarantee getting more coins than anybody else. Assume that all pirates are infinitely greedy, infinitely logical, and infintely bloodthirsty, and that each pirate knows this to be true of every other pirate. The highest priority of each pirate is to get as much money for themselves as possible. The second highest priority is to throw overboard the other pirates. A pirate will vote to throw another one over even if they have no monetary gain by doing so, and even if it would cost them their own life, but would not if throwing them over would cost even 1 coin. How should the first pirate suggest dividing the money?

Solution

也是经典问题。先从子问题开始：

• 如果只有 5 一个，那么显然他可以得到所有的金币
• 如果有 4，5两个，无论 4 怎么分配，5都可以直接把他投下水，获得所有的金币
• 如果有 3，4，5三个，如果3全部占有，那么显然 4，5会把他扔下水，所以 3 只能指望 4。为什么呢？因为如果 4 投了反对票，情况又回到了前面， 5 一定会把他扔下水，4 得不到任何东西。所以 3 只需要给 4 一个金币即可，所以此时的结果是 \((999,1,0)\)
• 如果有 2，3，4，5。 是否能和前面一样，2 指望 3 呢？2 如何才能指望 3？ 注意到上一种情况， 3 可以在只花费 1个金币的情况下，得以生存。显然，只要 3 对于 2 的分配不满意，就可以反对票。对 2 满意的分配只能是 1000，但此时无论如何，3 都可以投反对票把 2 投下去自己独吞（当然 4 5 肯定也反对这一分配），由此可知 2 不能指望 3. 如果 2 被扔下去，情况便回到了上一种，4 分得一个金币，而 5 没有金币。所以只需要比这种情况更优即可，即 \((997,0,2,1)\)
• 如果有 1，2，3，4，5。 同样的，1 不能指望 2。 且如果 1 被扔下去以后，金币的分配显然就回到了上一步，所以只需要给 3 一个金币，5 两个金币，就能获得多数的支持。即 \((997,0,1,0,2)\)

这篇关于MathProblem 85 Five pirates and a 1000 coins problem的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！