思维风暴：5名海盗如何分配100枚金币？

作者 | 梁唐

大家好，我是梁唐。

因为公众号迁移了，有同学给我留言说想看之前的海盗分金问题。所以我把之前的这一篇找了出来，做了一些修改，重新发出来。

今天我们讨论的算法问题，有一个非常有意思的背景。

海盗分金问题

说是有5个海盗组成了一个舰队，找到了传说中的宝藏。这份宝藏是100枚金币，于是这伙海盗就面临一个分赃的问题，我们知道海盗是非常残忍并且贪婪的。虽然这100枚金币每一枚都价值连城，但海盗们还是依然希望尽可能多地分到金币。

经过一系列协商，最终这5名达成共识，决定采取一种非常残忍的方案。

首先，海盗们会按照功劳大小对五个人进行编号，由编号小的海盗先提出分配方案。如果方案能够得到大多数人（过半）的同意，那么就按照他提出的方案进行分配。如果不能通过，说明他已经失去了威望，海盗们会残忍地将他投入海中喂鲨鱼。

在一个朦胧的早上你一觉醒来，突然发现自己成了一号海盗，那么你应该如何分配才能获得最多的金币，又不会被喂鲨鱼呢？

这就是经典的海盗分金问题。

思考

在我们思考之前，我们先完善一下题意，增加几个隐藏条件。

首先，每一个海盗都非常残忍。这意味着，在不影响收益的情况下，他们会更倾向于杀人。

其次，每一个海盗都极其聪明，以至于理论上能想到的东西他们都能想到。

也就是说这是一个理想情况下的博弈问题，有些像是囚徒困境，对于囚徒困境问题，我补充在了文末，大家如果对囚徒困境问题感兴趣可以拉到文末阅读。

对于这样的博弈问题，由于涉及多方视角，我们直接去推导或者是分析是非常困难的。因为涉及的变量以及因素太多，我们难以同时分析。

所以面临这样的问题，我们首先要做的就是缩小问题的规模，减少分析的变量，看看能不能分析出一些结论，或者是找到解题的思路。

在这个问题当中我们有5个海盗，所以显得无从下手，如果我们减少海盗的数量，也许就会简单很多。

一个海盗

那么我们从最极端的情况开始，假设只有一个海盗，结论很明显，他独吞所有宝藏。

两个海盗

我们继续，假设有2个海盗，1号海盗和2号海盗，会发生什么？

也很显然，由于题目中说了，每个海盗的提议必须要严格过半，所以无论1号海盗如何分配，2号海盗都一定不会同意。所以1号的结局是确定的，就是被扔进海里喂鲨鱼，即1号必死，2号独吞所有宝藏。

三个海盗

那如果再加一个海盗呢？

再加一个海盗的话，1、2、3号海盗，我们已经知道在有两个海盗的情况下，第一个海盗必死。所以2号海盗无论如何一定会同意1号的方案。

由于每一个海盗都极度聪明，1号海盗也知道这一点。既然无论怎么分配2号都会投同意，那么1号海盗完全可以提议独吞所有金币，这样1号和2号同意，3号反对，同意过半，所以分配方案是[0, 0, 100, 0, 0]。

四个海盗

我们再加入一个海盗，考虑一共剩下4个海盗的情况。

我们已经知道了只剩三个海盗时的情况，所以对于2号海盗来说，如果1号死了，那么他就可以独吞所有的宝藏。所以2号无论如何也不会同意。

当有4个海盗时，需要有3票同意才能通过，所以对于1号来说一定要拉拢3号和4号海盗。通过前面的分析得知，如果1号死了，2号分配，那么3号和4号海盗一无所有。所以1号只需要给3号和4号海盗每人分配1枚金币就可以拉拢他们。

这个时候的分配方案是：[0, 98, 0, 1, 1]

五个海盗

最后我们再加入一个海盗，就达成了题意当中说的5个海盗齐聚的情况了。

首先，5个海盗时需要3张同意票，1号需要拉拢两人投票。如果1号死了，2号可以得到98枚金币，所以2号一定反对。只能从3、4、5号海盗中下手，如果1号死了，2号提议的话，那么3、4、5号海盗的收益是[0, 1, 1]。1号只需要拉拢两人，可以给3号一枚，在4号和5号中挑一人给2枚即可。

所以最终的分配方案是[97, 0, 1, 2, 0]或者是[97, 0, 1, 0, 2]。

到这里，这个问题就结束了。但是我们的思考并没有结束，不知道大家从刚才的解法当中有没有看出规律。我们面临5个海盗这种错综复杂情况的时候根本无从下手，但是当我们倒过来思考，整个推导过程非常简单，而且顺理成章。

如果大家学过算法，想必能反应过来，这其实就是递归算法。我们不妨试着写一下，使用递归来解题的代码框架。

假设，获取n个海盗分配方案的函数是f。当我们计算f(2)时，我们需要根据f(1)的结果。我们试着写成伪代码：

def f(n):
  if n == 1:
    return [0, 0, 0, 0, 100]
  else:
    allocation = f(n-1)
    # 新的分配
    new_allocation = allocate(allocation)
    return new_allocation

我们先忽略allocate这个方法内部是怎么实现的，单纯看这段代码，整个框架已经有了。

递归的精髓也就在这里，程序自己调用自己只是表象，内里的精髓其实是问题的拆分，以及子问题向原问题的推导。整个递归从上到下的过程，其实是一个大问题化解成小问题，再有小问题拼装回大问题的过程。如果还不明白，我们再来看一个经典的例子来巩固一下，这个问题就是大名鼎鼎的汉诺塔问题：

在印度神话当中有一个大神叫做梵天，他在创造世界的时候创造了三根金刚柱。为了排解无聊，他在其中一根柱子上摆放了64个圆盘。这64个圆盘从上往下依次增大，他给僧侣出了一个问题。一次只能移动一个圆盘，并且圆盘只能放在比它大的圆盘上，该怎么做才能将圆盘从一根柱子移动到另一根呢？

为了简化问题，我们先观察摆放5个圆盘的情况。从图中可以看出来，一开始的时候圆盘都在A柱，如果我们想要将圆盘移动到B柱应该怎么办呢？

我们同样先来观察最简单的情况，A柱上只有一个圆盘，那很简单，我们直接将它移动到B柱即可。如果有两个圆盘呢？我们需要先将第一个移动到C柱，然后将第二个移动到B柱，最后再将C柱上的圆盘移动到B。那如果是三个圆盘呢，稍微复杂一些，但仔细列举一下，也能算得出来。

但是我们怎么通过问题规模的缩小来化简问题呢？

这需要我们对于题目进行深入思考，找到其中的关键点。这题的关键点就是圆盘的限制，大的圆盘不能落在小的圆盘上面。所以如果我们想要将n个圆盘从A柱移动到B柱，必须要将前n-1个圆盘先移动到C柱，这样才可以将最大的那块放到B，如此之后再将n-1块移动回B。

也就是说，我们将n-1块圆盘当做是一个整体，这样n块圆盘的方案就和两块圆盘时一样了。这就通过递归完成了简化。

最后，也是最关键的，怎么移动n-1块圆盘呢？其实很简单，我们套用同样的方法，再将这n-1块圆盘中的n-2块看成是整体，递归操作。理解了之后，不妨试着写出代码，其实只有几行：

def hanoi_tower(num, tower_start, tower_dest, tower_other):
  if num == 1:
    print('move plate {} from {} to {}'.format(num, tower_start, tower_dest))
    return 
  hanoi_tower(num-1, tower_start, tower_other, tower_dest)
  print('move plate {} from {} to {}'.format(num, tower_start, tower_dest))
  hanoi_tower(num-1, tower_other, tower_dest, tower_start)

我们调用一下这个方法，进行一下测试：

结果和我们的预期一致，说明我们的算法是正确的。最后，我们再回到海盗问题，又该怎么用代码实现呢？感兴趣的同学不妨亲自动手试试，如果实在写不出代码，在公众号回复关键词“海盗分金”查看我写的代码。

囚徒困境

囚徒困境是一道经典的博弈论问题。

说是有两个囚犯被抓住分开审问，如果两个囚犯都不招认，那么关押一年。如果一人招认，一人不招，那么招认的无罪释放，不招的关押十年。如果都招认，那么都关押5年。

这个问题表面上看很复杂，复杂的原因在于我们无法预测同伴的选择。但其实如果我们不考虑同伴，会发现这个问题非常简单，就是选择招认。因为无论同伴招不招认，招认对于己方来说都是最优解，并且一定不会落入关押十年的最坏情况。