算法浅谈——递归算法与海盗分金问题

2019/04/10 10:10
阅读数 7

本文始发于个人公众号:TechFlow

<br>

最近看到一道很有意思的问题,分享给大家。

还是老规矩,在我们聊算法问题之前,先来看一个故事。

<br>

传说中,有5个海盗组成了一支无敌的海盗舰队,他们在最后一次的寻宝当中找寻到了100枚价值连城的金币。于是,很自然的,这群海盗面临分赃的问题。为了防止海盗内讧,残忍的海盗们制定了一个奇怪的规则:

<br>

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

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

<br>

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

<br>

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

其次,每一个海盗都极其聪明,都能想到最佳答案。

<br>

这两个条件一出来,问题就比较明显了,这是博弈论题目才有的架势。

既然这是一道博弈论的问题,那么我们通过常规的思路是无法找到答案的,我们需要另辟蹊径才行。

<br>

那么,怎么另辟蹊径呢?

<br>

一个比较常规的做法是先不考虑原问题,先假设一个和原问题差不多,但是规模小很多的子问题。通过对子问题的求解来摸索原问题的解法。

<br>

举个例子,在这题当中,我们需要计算5个海盗分金币的情况。一时之间我们有些无从下手,那么我们简化问题,问题的规则还是不变,但是我们把海盗的数量减少,减少到只有一个海盗。那么根据规则,很显然,最后的结果是这个海盗独吞所有的金币。

这个时候的分配方案是:[0, 0, 0, 0, 100]

<br>

我们从这个点开始往回倒推,假设这个时候多了一个海盗,一共是4号和5号两个海盗的时候,会怎么样?

<br>

显然因为要求要一半以上同意提案,提案才可以通过。所以在这个时候,无论4号海盗如何提议,5号都不会同意,要将他投下海喂鲨鱼。所以如果只剩下4和5的时候,4号海盗必死无疑。

这个时候的分配方案是: [0, 0, 0, -1, 100],-1表示必死无疑

<br>

那如果再加一个海盗呢?

<br>

再加一个海盗的话,是3,4,5三个海盗的情况。因为只剩4和5的时候4号必死,所以他为了活命一定会同意3号的提案(海盗对其他人残忍,对自己不残忍)。这个时候,3号不论如何提议,都一定可以通过。因为算上他自己的一票,和4号的一票,已经过半了,所以他的提案一定可以通过。

这个时候的分配方案是: [0, 0, 100, 0, 0]

<br>

我们再加入一个海盗,考虑一共剩下4个海盗的情况。如果2号死去,那么3号可以独吞所有金币,所以显然3号一定不会同意2号的方案。4个人的时候,至少需要3个人同意才可以通过方案,那么2号必须要争取4号和5号。如果2号死去,4号和5号一无所有,所以2号只需要分配给4号和5号一枚金币,就可以拉拢他们。

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

<br>

最后,我们再加入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]。

<br>

到这里,这个问题就结束了。但是我们的思考并没有结束,不知道大家从刚才的解法当中有没有看出规律。我们面临5个海盗这种错综复杂情况的时候根本无从下手,但是一旦当我们试着将问题的规模缩小,从简单的情况开始思考,那么问题一下子就豁然开朗了。

<br>

老子说:天下大事,必作于细,天下难事,必作于易。从这个问题来看,和这个道理相得益彰。

<br>

这种从最简单推导最复杂的算法就称为递归

<br>

假设,获取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这个方法内部是怎么实现的,单纯看这段代码,整个框架已经有了。

<br>

递归的精髓也就在这里,程序自己调用自己只是表象,内里的精髓其实是问题的分割。整个递归从上到下的过程,其实是一个大问题化解成小问题的过程。如果还不明白,我们再来看一个经典的例子来巩固一下,这个问题就是大名鼎鼎的汉诺塔问题:

<br>

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

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

<br>

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

<br>

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

<br>

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

<br>

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

<br>

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

<br>

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)

<br>

我们调用一下这个方法,进行一下测试:

结果和我们的预期一致,说明我们的算法是正确的。

<br>

最后,我们再回到海盗问题,又该怎么用代码实现呢?感兴趣的同学不妨亲自动手试试,如果实在写不出代码,在公众号回复关键词”海盗分金“查看我写的代码。

<br>

今天的文章就到这里,扫码关注我的公众号:TechFlow,获取更多文章

原文出处:https://www.cnblogs.com/techflow/p/12230180.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部