本文始发于个人公众号: TechFlow
最近看到一道很有意思的问题, 分享给大家.
还是老规矩, 在我们聊算法问题之前, 先来看一个故事.
传说中, 有 5 个海盗组成了一支无敌的海盗舰队, 他们在最后一次的寻宝当中找寻到了 100 枚价值连城的金币. 于是, 很自然的, 这群海盗面临分赃的问题. 为了防止海盗内讧, 残忍的海盗们制定了一个奇怪的规则:
他们决定按照功劳大小对五个人进行编号, 由编号小的海盗先提出分配方案. 如果方案能够得到大多数人的同意, 那么就按照他提出的方案进行分配. 如果不能通过, 说明他已经失去了威望, 海盗们会残忍地将他投入海中喂鲨鱼.
在一个朦胧的早上你一觉醒来, 突然发现自己成了一号海盗, 那么你应该如何分配才能获得最多的金币, 又不会被喂鲨鱼呢?
在我们思考之前, 我们先完善一下题意, 增加几个条件.
首先, 每一个海盗都非常残忍. 这意味着, 在不影响收益的情况下, 他们会更倾向于杀人.
其次, 每一个海盗都极其聪明, 都能想到最佳答案.
这两个条件一出来, 问题就比较明显了, 这是博弈论题目才有的架势.
既然这是一道博弈论的问题, 那么我们通过常规的思路是无法找到答案的, 我们需要另辟蹊径才行.
那么, 怎么另辟蹊径呢?
一个比较常规的做法是先不考虑原问题, 先假设一个和原问题差不多, 但是规模小很多的子问题. 通过对子问题的求解来摸索原问题的解法.
举个例子, 在这题当中, 我们需要计算 5 个海盗分金币的情况. 一时之间我们有些无从下手, 那么我们简化问题, 问题的规则还是不变, 但是我们把海盗的数量减少, 减少到只有一个海盗. 那么根据规则, 很显然, 最后的结果是这个海盗独吞所有的金币.
这个时候的分配方案是:[0, 0, 0, 0, 100]
我们从这个点开始往回倒推, 假设这个时候多了一个海盗, 一共是 4 号和 5 号两个海盗的时候, 会怎么样?
显然因为要求要一半以上同意提案, 提案才可以通过. 所以在这个时候, 无论 4 号海盗如何提议, 5 号都不会同意, 要将他投下海喂鲨鱼. 所以如果只剩下 4 和 5 的时候, 4 号海盗必死无疑.
这个时候的分配方案是: [0, 0, 0, -1, 100],-1 表示必死无疑.
那如果再加一个海盗呢?
再加一个海盗的话, 是 3,4,5 三个海盗的情况. 因为只剩 4 和 5 的时候 4 号必死, 所以他为了活命一定会同意 3 号的提案 (海盗对其他人残忍, 对自己不残忍). 这个时候, 3 号不论如何提议, 都一定可以通过. 因为算上他自己的一票, 和 4 号的一票, 已经过半了, 所以他的提案一定可以通过.
这个时候的分配方案是: [0, 0, 100, 0, 0]
我们再加入一个海盗, 考虑一共剩下 4 个海盗的情况. 如果 2 号死去, 那么 3 号可以独吞所有金币, 所以显然 3 号一定不会同意 2 号的方案. 4 个人的时候, 至少需要 3 个人同意才可以通过方案, 那么 2 号必须要争取 4 号和 5 号. 如果 2 号死去, 4 号和 5 号一无所有, 所以 2 号只需要分配给 4 号和 5 号一枚金币, 就可以拉拢他们.
这个时候的分配方案是: [0, 98, 0, 1, 1]
最后, 我们再加入 1 号海盗. 同理, 1 号海盗的提案需要至少 3 个人通过. 算上他自己, 他还需要争取 2 票. 由于 1 号死去 2 号可以获得 98 枚金币, 所以 1 号一定无法争取 2 号, 还是只能从 3,4,5 三个人下手. 可以给 3 号 1 枚, 4 号两枚 (比 2 号的方案多一枚), 也可以给 3 号 1 没, 5 号两枚.
这个时候的分配方案是: [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)
我们调用一下这个方法, 进行一下测试:
结果和我们的预期一致, 说明我们的算法是正确的.
最后, 我们再回到海盗问题, 又该怎么用代码实现呢? 感兴趣的同学不妨亲自动手试试, 如果实在写不出代码, 在公众号回复关键词 "海盗分金" 查看我写的代码.
来源: https://www.cnblogs.com/techflow/p/12230180.html