有趣的海盗分金币问题，不学点算法都不配当个海盗了

WeihanLi.Npoi 根据模板导出Excel

最近几天看到一个挺有趣的博弈相关的趣谈，今天来分享给大家，并且也会详细讲解最终问题的最优解，并且我还好通过这道题扯一扯递归。

问题描述

有 5 个海盗，获得了 100 枚金币，于是他们要商量一个方法来分配金币。商议方式如下：

由 5 个海盗轮流提出分配方案，规则如下

1、如果超过半数海盗（包括提出者）同意该方案，则按照该方案分配。

2、如果同意该方案的人数（包括提出者）小于等于半数，则提出者要被扔到海里喂鱼，剩下的海盗继续商议分配。

3、海盗们都是绝对理性的，以自己尽可能多获得金币为目的。但是在收益相等的情况下，会倾向把提出者扔到海里。

问：第一个海盗应该提出怎样的分配方案，才能保证自己既不被扔到海里，又能使自己利益最大化？

解决问题

先做一些假设和提醒

为了方便后面描述，我们假设轮流提出方案的顺序为：海盗5，海盗4，海盗3，海盗2，海盗1；也就是说，最开始由海盗5 提出分配方案，海盗1排在最后

并且，大家一定要注意最后一个条件，每个海盗是绝对理性以及在收益相等的情况下，会倾向把提出者扔到海里。

前方高能，开始扯淡，请你发挥出你的各种猜想

好了，现在如果你是海盗5，你会怎么分配才能使得获得的金币尽可能多，并且不会被扔进海里喂鱼呢？

说实话，第一眼看到这个问题，有点无从下手，脑子太特么乱了，因为完全不知道怎么证明我的分配方案能够让超过一半的海盗都必须支持我，要不平均分配？要不我少一点他们多一点？要不我多一点他们少一点（这样会不会马上就被扔下海里）？

你也可以自己先想几分钟哦，看看你能否自己想的出来？

事实上，要让别人同意我们的想法，我们必须得知彼知己，才能百战百胜。也就是说，海盗5要给出分配方案，必须基于海盗4的分配方案来；也就是说，海盗5得先假设自己被扔进海里的话，海盗4会如何分配呢？然后根据海盗4的分配方案，海盗5才能给出他的分配方案。

同理，海盗4的分配方法得基于海盗3，海盗3得基于海盗2，以此类推

听不懂？没关系，下面我举个例子你们马上就懂了

逐层击破

1、只有 2 个海盗的情况

现在，我们假设只有两个海盗：海盗1 和海盗2，这个时候你应该知道分配结果了吧？

很显然，无论海盗2提出什么方案，海盗1 都会直接拒绝，这样海盗1就可能获得全部的金币了，也就是说，当只有两个海盗时，海盗2 无论怎么讨好海盗1，最终的结果都是到海里喂鱼，所以分配结果如下

2、只有3个海盗的情况

这个时候突然跳出了个海盗3，也参与到这场分赃活动中，这个时候海盗3该如何分配？

其实也非常简单，海盗3刚才窥听了海盗1和海盗2的对话，知道如果自己被扔进海里的话，海盗2一定也会被扔进海里，所以海盗3知道，自己无论提出什么方法，海盗2都必须同意，所以海盗3可以提出如下的分配方案：

海盗3： 100 个金币

海盗2： 0 个金币
海盗1： 0 个金币。

也就是，只要海盗2支持海盗3，就可以形成 2：1的局面，海盗3就可以稳赢，不需要兼顾海盗1是否支持。所以最终的分配结果如下

有人可能会说，我们用不用给海盗2分配一点好处？例如分配给海盗2一个金币，条件3有个规则：在收益相等的情况下，海盗们会倾向把提出者扔到海，答是不需要的，虽然海盗2没有分配到金币，但是他并没有被扔进海里，这就是最大的好处了

看到这里，你是不是也知道如果是 4 个海盗或者 5 个海盗，你也会分配了？我相信你大概率知道怎么分配了，不过我还是要讲一下，因为后面随着人数的增加，也并没有你想的那么简单，并且后面还会和递归算法串讲一下。

3、只有4个海盗的情况

这个时候又突然蹦出个海盗4，并且海盗4是已经知道了海盗3的分配方案了，这个时候海盗4只需要获得其中两个人的支持即可。

如何获得其中两个人的支持？

这很容易，拿点钱给海盗1和海盗2就可以了，海盗4可以提出如下分配方案

海盗4：98个

海盗3：0个

海盗2：1个

Python的Excel操作及数据可视化

海盗1：1个

注意，在收益相等的情况下，海盗们会倾向把提出者扔到海里，所以海盗4必须在海盗3的基础上，多给海盗1和海盗2一个金币，这个时候海盗1和海盗2一定会支持海盗4，此时的局面是 3：1（支持：反对的人数），因此只有4个人的情况下，分配方案为：

有人可能会问，为啥要拉拢贿赂海盗1和海盗2，咱能不能尝试贿赂下海盗3？

答是咱贿赂不起，如果你有这样的想法，只能说明你不是一个合格的海盗！

4、只有5个海盗的情况

如果有5个海盗，其实海盗5和海盗4一样，只需要拉拢两个人就可以了，那要拉拢谁呢？

这也不难，首先必须得贿赂海盗3，给他一个金币就可以了，其次我们在海盗2或者海盗1之中拉拢一个人即可，想要拉拢哪一个，随你开心，所以海盗5可以提出如下方案：

到这里，就已经分配完毕了，是不是觉得很不可思议？原本还怕自己无论提出啥方案，都会被扔进海里，结果是如此出人意料。以后和别人分赃，是时候拿出这个规则了

问题的核心

我觉得这个问题，非常像我们平时学算法中的递归，例如对于递归方式：f(n) = f(n – 1) + f(n – 2)，并且给出初始条件 f(1) = f(2) = 1。

那么如果一开始要你算 f(n)，你也是无从下手的，f(n) 必须基于 f(n – 1) 和 f(n – 2)，类比于这个海盗问题的话，

1、n 相当于海盗的个数。

2、只有两个海盗时，我们可以非常容易着给出方案，相当于初始条件 f(1) = f(2) = 1

3、f(n) = f(n – 1) + f(n – 2) 相当于海盗之间定下的规则

所以呢，有时候遇到这种看似很复杂的博弈问题，不妨先从问题的规模尽量小处理起，后面在逐一增加问题的规模。

不妨来个拓展

如果又突然冒出了一个海盗呢？也就是在一共有 6 个海盗的情况下，该如何处理呢？

有没有觉得，从 5 个到 6 个，是一个分水岭？因为从 5 个开始，就有多种分配方案，这个时候就更加考验你的逻辑了。

不过，对于 6 个，我姑且给大家分析一下，当然，只是我认为是这样，其实我看过别人的也有不同的版本。下面我来分析下海盗6可以给出的策略：

首先，我们必须拉拢 3 个人，显然，我们是不可能会拉拢海盗5的，因为咱拉不起。因为我们会从海盗1 ~ 海盗4中考虑。

1、首先我们必须拉拢海盗4，因为他最容易贿赂，给他 1 个金币即可。

2、接着，我们拉拢海盗3，给他两个金币即可

此时，我们已经拉拢了海盗3和海盗4，接下来我们需要在海盗1和海盗2中选一个即可，那么问题来了，该给海盗1和海盗2他们多少，他们才愿意同意你的方案？

显然，如果我们给海盗1分配 3 个金币，海盗2分配 0 个，显然海盗1一定会同意。

但是，真的需要给海盗1分配 3 个吗？如果我给他 2 个金币，他会同意吗？

答是会的，为什么呢？因为在海盗5的方案中，要么是海盗1获得2个，要么是海盗2获得2个，所以对于海盗1来说，海盗5会不会贿赂他，存在不确定性，因此作为一个理智的海盗，海盗1是会同意海盗6给他2个金币的方案的。

因此海盗6可以提出如下方案

事实上，也可以从概率上来证明，在海盗5的方案中，由于海盗1和海盗2存在不确定性，我们可以进行折算，折算成海盗1和海盗2各自获得一个金币，所以我们给他两个金币，他必须得同意

当然，如果海盗6要给海盗2分配2个金币，然后给海盗1分配 0 个金币，也是可以的。**总的来说就是，我们可以从海盗1，海盗2，海盗3中选出两个人，然后每人给他两个金币即可以，这样的组合有三种，因此海盗6可以由如下 3 种方案：

分析到这里，就已经结束了，如果又蹦出一个海盗呢？也就是说一共有 7 个海盗呢？

剩下的就交给你了，鉴于篇幅，我就不继续分析了。

最后

这么多年以来，今年的春节，估计是最特殊的春节了，想必大家都在家里呆着，今天这道题也是我花了整整一个上午写的，希望能够让你有所收获，或者能够可以给给解解闷，我们下期再见！

老铁，要不点个赞再走可好？么么哒

1、给俺点个赞呗，可以让更多的人看到这篇文章，顺便激励下我，嘻嘻。

2、老铁们，关注我的原创微信公众号「帅地玩编程」，专注于写算法 + 计算机基础知识（计算机网络+ 操作系统+数据库+Linux）。

保存让你看完有所收获，不信你打我。后台回复『电子书』送你一份精选电子书大礼包，包含各类技能的优质电子书。

作者简洁

作者：大家好，我是帅地，从大学、校招一路走来，深知算法，计算机基础知识的重要性，所以申请了一个微星公众号『帅地玩编程』，专业于写这些底层知识，提升我们的内功，帅地期待你的关注，和我一起学习。 转载说明：未获得授权，禁止转载

TypeScript 源码详细解读(4)语法1-语法树