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

注意,在收益相等的情况下,海盗们会倾向把提出者扔到海里,所以海盗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 个海盗呢?

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

最后

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wsxxyz.html