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

2024-03-21 14:48

本文主要是介绍算法浅谈——递归算法与海盗分金问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文始发于个人公众号: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)

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

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


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


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

这篇关于算法浅谈——递归算法与海盗分金问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/832945

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景:问题描述原因分析:解决方案:第一种:修改后,只有当前生效,若是mysql服务重启,就会失效;

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码