2021-04-24 蓝桥杯 Python 第五题--密室逃脱

2021-04-24 蓝桥杯Python 省赛前面四道题小朋友轻松解决。 最后一道题小朋友没有思路。昨天,我和儿子一起分析了下这个题目。发现挺有意思。

第五题解题思路

密室逃脱

提示信息:

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

游戏规则:

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

  2. 每次玩家可以进入右边的一个密室,也可以跳过一个密室进入下个密室(如:当玩家当前在3号密室,他可以进入4号密室也可以进入5号密室);

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

编程实现:

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

例如:X=2,Y=4,M=7,2号和4号有毒气泄露,避开2号和4号毒气密室,进入7号密室有2种路线方案,分别是1->3->5->6->7路线和1->3->5->7路线。

输入描述

输入三个正整数X,Y,M(1<X<Y≤M),并以英文逗号隔开

输出描述

输出从1号密室开始避开X、Y号毒气密室,进入M号密室有多少种路线方案

解题思路

解法一

先求解出所有从1->M 所有路径, 如果路径中包含X和Y则去除此路径。如下代码可以解出所有可能路径。
解法的缺点:要先找出所有路径放入列表中,因此,M值不能太大。 否则会出现内存不足的情况。

import time
all_solutions = []
def printSteps(preSteps: str, leftSteps: int):  # 用递归原理来找出所有路径存入变量all_solutions。
    global all_solutions
    if(leftSteps < 0):
        print("台阶数不能小于0")
    if(leftSteps == 1):
        # print(preSteps + " 1")
        all_solutions.append(preSteps + " 1")
        return
    elif(leftSteps == 0):
        all_solutions.append(preSteps)
        # print(preSteps)
        return
    for i in range(1, 3):# 每次可以走1,走2步.
        printSteps(preSteps + " " + str(i), leftSteps - i)


def all_path(all_solutions: list) -> list:
    steps = []
    for i in all_solutions:
        steps.append(list(map(int, i.split())))  # 生成列表并将数据类型转成int。
    all_result = []
    for i in steps:
        a = [1]
        temp = 1
        for j in i:
            temp += j
            a.append(temp)
        all_result.append(a)
    return all_result

def mishi_path(X: int, Y: int, M=5) -> list:
    # 递归解法算出所有走法,返回到所有all_solutions(str list)
    printSteps(preSteps='', leftSteps=M-1)
    l = all_path(all_solutions)  # 从1->M 的所有路径。
    result = []
    for i in l:
        if (X in i) or (Y in i):
            continue
        else:
            result.append(i)
    return result
    
if __name__ == "__main__":
    t1 = time.time()
    result = mishi_path(X=2, Y=4, M=7)
    for i in range(len(result)):
        print(f"第{i+1}: {result[i]}")
    print(f"共有{len(result)}种路径。")
    t2 = time.time()
    print(t2-t1)

在这里插入图片描述

解法二

因为题目中只有要求求出一共有多少路径, 并没有要求把具体的路径给打印出来。此题利用递归算法来解决,原理上与斐波那契数列类似。我们需要注意在递归时把X和Y节点递归排除即可。

def Fibonacci_Recursion_tool(x,y,n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    elif n==x:
        return 0
    elif n==y:
        return 0
    else:
        return Fibonacci_Recursion_tool(x,y,n - 1) + Fibonacci_Recursion_tool(x,y,n - 2)


def main():
    print(Fibonacci_Recursion_tool(2,4,7))


if __name__ == "__main__":
    main()

解法三

此题利用递归算法来解决,理解起来虽然比较简单,代码容易上手,但是时间复杂度高,当输入Fibonacci_Recursion_tool(2,4,47)时,需要很久才能给出答案 。因此, 我们想到直接使用for循环来解决,直接在函数体内部进行计算,这样可以大大节省运算时间。

def Feibo(x=2,y=4,n=7):
	a=0
	b=1
	fb=0  
	for i in range(n-1):
		if i in [x-1,y-1]: #x,y跳过的单元格的数据要设置为0
			b=a+fb
			a=fb
		else:
			a,b=b,a+b
	return b


def main():
    print(Feibo())


if __name__ == "__main__":
    main()

更多相关推荐

2021-05-29 国赛蓝桥杯第五题-孙...

国赛蓝桥杯第五题-孙悟空的金箍棒一、题目:二、解法一(递归)1.解题思路2.解题代码:3.运行...

继续阅读

算法第五题:反转字符串 2021-08...

一、翻转字符串中的所有元音字符串,其中包括大小的原因字母。翻转字符串的算法用到双指针这一...

继续阅读

蓝桥python——九数组分数【2015...

蓝桥杯【九数组分数】题目描述:九数组分数【2015第五题】1,2,3…9这九个数字组成一个分数,其...

继续阅读

(python)题目 1431: 蓝桥杯2014...

题目描述有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果,然后进行下面的游戏:每...

继续阅读

project欧拉第五题

2520isthesmallestnumberthatcanbedividedbyeachofthenumbersfrom1to10withoutanyremainder.Wh...

继续阅读

python练习册第五题

目录目录题目解题思路解题代码题目你有一个目录,装了很多照片,把它们的尺寸变成都不大于iPho...

继续阅读

蓝桥杯每日一题(24):门牌制作...

Topic试题A:门牌制作本题总分:5分【问题描述】小蓝要为一条街的住户制作门牌号。这条街一共有...

继续阅读

Rosalind第五题:计算GC内容

问题DNA字符串的GC含量由字符串中“C”或“G”的符号百分比给出。例如,“AGCTATAG”的GC含量为37.5...

继续阅读

蓝桥杯第五天

双指针问题数组合并合并有序数组(合并后的数组也应该是有序的)二分查找二分查找法:折半查找...

继续阅读