密室逃脱游戏-第12届蓝桥杯省赛Python真题精选

[导读]：超平老师的Scratch蓝桥杯真题解读系列在推出之后，受到了广大老师和家长的好评，非常感谢各位的认可和厚爱。作为回馈，超平老师计划推出《Python蓝桥杯真题解析100讲》，这是解读系列的第58讲。

密室逃脱游戏，本题是2021年4月24日举办的第12届蓝桥杯青少组Python编程省赛真题，第12届一共有两场省赛，这是第二场。题目要求计算在100间密室中，按照游戏规则进入M号密室有多少种路线方案。

先来看看题目的要求吧。

一.题目说明

提示信息：

有一个密室逃脱游戏，有100间密室连在一排。密室编号是从1开始连续排列一直排到第100间密室，如下图：

游戏规则：

1. 玩家初始位置在1号密室；

2. 每次玩家可以进入右边的一个密室，也可以跳过一个密室进入下个密室（如：当玩家当前在3号密室，他可以进入4号密室也可以进入5号密室）；

3. 有毒气的密室不能进入需要避开。

编程实现：

给定三个正整数X，Y，M（X < Y < M ≤ 100），表示三个密室编号，X号密室和Y号密室有毒气泄漏，不能进入，玩家需要进入到M号密室。按照游戏规则进入M号密室有多少种路线方案。

例如：X = 2，Y = 4，M = 7，进入M号密室有2种路线方案，分别是1->3->5->6->7路线和1->3->5->7路线。

输入描述：

输入三个正整数X，Y，M（X < Y < M），X和Y表示有毒气密室编号，M表示需要进入的密室编号，且三个正整数之间以英文逗号隔开

输出描述：

输出进入M号密室有多少种路线方案

样例输入：

2,4,7

样例输出：

2

二.思路分析

这是一道算法题，考查的知识点涉及循环、递归、列表和斐波那契数列等。

题目所描述的场景看起来是不是有似曾相识的感觉，但是又感觉有点怪怪的？实际上，这就是斐波那契数列（兔子数列）的变种问题，其本质仍然是斐波那契数列。

还记得斐波那契数列的递推公式吗：

针对本题，我们可以运算分解思维将题目需求拆分成两步：

1). 假定没有毒气密室；

2). 增加X和Y两个毒气密室。

如果不考虑毒气密室，这就是我们熟悉的斐波那契数列，我们可以使用f(m)表示进入M号密室的路线数量。

当m = 3时，也就是3号密室，可以从1号密室过来，也可以从2号密室过来，根据加法原理，f(3) = f(1) + f(2)。

对于2号密室，它前面只有1号密室，因此路线数量为1，即f(2) = 1。

对于1号密室，它是玩家的初始位置，应该设置为多少呢？

如果只看1号密室本身，我们可以设置为0，也可以设置为1。但是从3号密室的角度来看，设置为1显然更合适。

所以，递推公式如下所示：

f(m) = 1 当m = 1 或 m = 2时f(m) = f(m - 1) + f(m - 2) 当m > 2时

如下图所示，这是在没有毒气密室时1~8号密室的路线数量：

接下来，我们再增加两个毒气密室X和Y，以题目给的样例数据X = 2，Y = 4，M = 7来说明。

X号密室和Y号密室有毒气泄漏，是不能进入的，这就意味着f(x)和f(y)都为0，即f(2) = f(4) = 0。

所以，在计算f(m)的时候，除了要单独考虑f(1)和f(2)之外，还需要考虑m = x、m = y的情况，如果 m = x 或者 m = y，那么f(m) = 0。

对应的，进入1~8号密室的路线数量如图所示：

这就意味着在计算每个密室的路线数量时，需要判断房间号是否为x或y，递推公式如下：​​​​​​​

f(m) = 0  当m = x 或 m = yf(m) = 1  当m = 1 或 m = 2f(m) = f(m - 1) + f(m - 2) 当m > 2时

针对斐波那契数列问题，通常有如下三种解决方案：

1). 递归

2). 动态规划

3). 迭代

这3种方案，都有一个共同点，那就是都需要用到递推公式。

思路有了，接下来，我们就进入具体的编程实现环节。

三.编程实现

根据上面的思路分析，我们分别使用3种方案来编写程序：

• 递归

• 动态规划

• 递推

1. 递归

递归算法的核心是要定义递归函数，递归的3要素如下：

• 自定义函数，并且带有参数

• 在函数中调用自己

• 有结束条件

根据前面思路分析中的递推的公式，编写代码如下：

代码比较简单，这也是递归函数的特点，强调两点：

1). m = x或y的条件，要先于m == 1或2；

2). 在if语句中有return语句，因此不需要使用elif和else，代码更加简洁。

但是，这个代码是有问题的，如果m比较大的话，会存在超时的情况，你可以测试一下m为100的情况。

为什么会超时呢，原因在于进行了大量重复的计算，比如在计算f(x, y,10)的时候，需要计算f(x, y, 9)和f(x, y, 8)，而在计算f(x, y, 9)的时候，需要计算f(x, y, 8)和f(x, y, 7)，很显然，f(x, y, 8)计算了两次。

实际上，随着m的增加，计算的次数会以指数的形式增加。能否将这些已经计算过的值保存起来，从而避免重复计算呢。

这就是带备忘录的递归算法，可以增加一个列表，用于保存f(x, y, m)的值。

修改代码如下：

说明两点：

1). 递归函数中增加了一个参数memo，这就是备忘录列表；

2). 将列表的初始值设为-1，然后判断memo[m]的值，如果为-1，则说明是第一次计算，将计算的结果保存到memo列表中。

有了带备忘录的递归算法，时间复杂度将大大降低，效率会得到极大的提升，这是典型的用空间换时间的策略。

2. 动态规划

递归算法是自顶向下的策略，而动态规划则是自底向上的思想，可以从第1项和第2项开始，逐个计算后续的每一项。

动态规划有两个关键点：

• 定义dp列表

• 找出推导公式（状态转移方程）

我们可以定义dp[i]表示到i号密室的路线数量，由于列表的下标是从0开始的，为了方便，将dp[0]设为0，表示0号房间，可以理解为是虚拟的一个房间，dp[1]设置为1，表示1号房间，依此类推...

对应的代码如下：

代码也不算多，说明两点：

1). 在计算dp[1]的时候，使用了带条件的赋值语句，这体现了Python的简洁性；

2). 虽然列表有第0项，但它是虚拟的，实际上我们是从第1项开始算的，即下标为1的列表项表示1号密室，因此对于m号密室，就是dp[m]。

3. 递推

仔细分析动态规划中的代码，可以发现在计算dp[i]的时候，实际上只用到了dp[i - 1]和dp[i - 2]。

于是，一些追求完美的同学开始有想法了，能否不用列表呢，这样还可以节省不少空间呢。

确实可以，实际上，我们只需要3个变量就够了，不妨用fm表示当前项，f2表示第m -1项，f1表示第m - 2项。

接下来使用循环从第3项开始，一步一步的计算每一项，这就是递推的算法思想，也叫迭代，对应的代码如下所示：

代码不多，说明两点：

1). 在计算第1项和第2项的时候，需要考虑x和y的取值；

2). 每次在计算好当前项fm的值后，需要重新设置f1和f2，可以理解为f1和f2都右移一位。

至此，整个程序就全部完成了，你也可以输入不同的数字来测试效果啦

四.总结与思考

本题代码在10行左右，涉及到的知识点包括：

• 循环语句，主要是for...in；

• 条件语句；

• 输入处理，尤其是多个数据的输入；

• 列表的使用；

• 带条件的赋值语句；

• 斐波那契数列；

作为本次省赛的倒数第二题，难度较大，难点在于如何找到突破点，将问题拆分成两个小问题，然后逐一解决。

将复杂问题拆分成多个简单问题，进而逐个解决，这是我们在学习编程时要重点培养和训练的一种思维。

任何复杂问题，只要能分解，我们就可以找到解决问题的方法。

号称硅谷钢铁侠的埃隆·马斯克曾经说过：“一个人最大的本事是拥有拆解思维，掌握它，你将活力四射”，由此可见，拆解思维是多么的强大和重要。

斐波那契数列，这是我们学习算法的必备经典问题，本文给出了3种解决方案，分别是递归、动态规划和递推（迭代）。相比较而言，递推算法是最优的，时间复杂度和空间复杂度都是最低的。

当我们彻底理解了斐波那契数列问题，就可以解决一系列相关题目，基本上都是它的变种问题。

超平老师给你留一道思考题，这里给出了动态规划的解决方案，你认为斐波那契数列是一个真正的DP问题吗，为什么呢？

你还有什么好的想法和创意吗，也非常欢迎和超平老师分享探讨。

如果你觉得文章对你有帮助，别忘了点赞和转发，予人玫瑰，手有余香😄

需要源码的，可以移步至“超平的编程课”gzh。