素材网站可以做淘宝吗,北京 公司网站制作,湖南网站推广优化,资源网站如何做[导读]#xff1a;超平老师的Scratch蓝桥杯真题解读系列在推出之后#xff0c;受到了广大老师和家长的好评#xff0c;非常感谢各位的认可和厚爱。作为回馈#xff0c;超平老师计划推出《Python蓝桥杯真题解析100讲》#xff0c;这是解读系列的第58讲。
密室逃脱游戏超平老师的Scratch蓝桥杯真题解读系列在推出之后受到了广大老师和家长的好评非常感谢各位的认可和厚爱。作为回馈超平老师计划推出《Python蓝桥杯真题解析100讲》这是解读系列的第58讲。
密室逃脱游戏本题是2021年4月24日举办的第12届蓝桥杯青少组Python编程省赛真题第12届一共有两场省赛这是第二场。题目要求计算在100间密室中按照游戏规则进入M号密室有多少种路线方案。
先来看看题目的要求吧。
一.题目说明
提示信息
有一个密室逃脱游戏有100间密室连在一排。密室编号是从1开始连续排列一直排到第100间密室如下图 游戏规则
1. 玩家初始位置在1号密室
2. 每次玩家可以进入右边的一个密室也可以跳过一个密室进入下个密室如当玩家当前在3号密室他可以进入4号密室也可以进入5号密室
3. 有毒气的密室不能进入需要避开。
编程实现
给定三个正整数XYMX Y M ≤ 100表示三个密室编号X号密室和Y号密室有毒气泄漏不能进入玩家需要进入到M号密室。按照游戏规则进入M号密室有多少种路线方案。
例如X 2Y 4M 7进入M号密室有2种路线方案分别是1-3-5-6-7路线和1-3-5-7路线。
输入描述
输入三个正整数XYMX Y MX和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 2Y 4M 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。
