蓝桥杯-李白打酒
没有白走的路，每一步都算数🎈🎈🎈
题目描述：
李白遇到一个酒店，原来瓶子的酒量就会翻倍。遇到一个公园就会喝掉一斗的酒，原来最开始酒瓶子里面有2斗水，最后一个经过的地方是公园，公园的个数有10个，酒店的个数为5个，例如babaabbabbabbbb就是一个行走过程，满足经过所有地方之后，李白恰好将所有的酒全部喝完。其中b表示遇到的是公园，a表示遇到的是酒店。求所有可行的方案数量，不需要记录每个方案到底是咋样。
输入描述：
很显然，此题没有显示输入
输出描述：
最后的方案数量
算法思路：
本人最开始的思路是用dfs，后面发现dfs貌似有约束条件，就是酒店，公园的个数是有限的。开始放弃，于是尝试用暴力法求解，但是暴力法求解的变量就很多，并且变量不好回溯。遂经过再次挣扎，选择使用dfs深度优先搜索来写，途中也写出很多bug
- 暴力法求解
- 暴力法求解当然是没有通过
import os
import sys
#错误代码
s = 2
m = 5
n = 10
cnt = 0
a = 'a'
b = 'b'
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
for i in [a,b]:
## print(i)
if i==a and m!=0:
s*=2
m-=1
elif i==b and n!=1:
s-=1
n-=1
if m==0 and n==1:
if s==1:
## print(1)
cnt+=1
m = 5
n = 10
s = 2
print(m,n,s)
print(cnt)- dfs遍历
只要在传递参数的时候多给几个参数就可以通过。
注意递归的时候，参数的传递条件，即使设置最大递归长度，内核也会爆炸
import os
import sys
##sys.setrecursionlimit(100000)
m = 5
n = 10
cnt = 0
a = 'a'
b = 'b'
def dfs(h,s,m,n):
global cnt
if h==14 and m==0 and n==1:
## print(s)
if s==1:
cnt+=1
return
## print(s)
for i in [a,b]:
if i==a:
if m-1>=0 and n>=0:
dfs(h+1,s*2,m-1,n)
## s = s/2
else:
s-=1
if n-1>=0 and m >=0:
dfs(h+1,s,m,n-1)
s+=1
return
dfs(0,2,m,n)
print(cnt)每日一句
摘自《狂飙》：
生存在宇宙中，本身就是一件很幸运的事情，但是不知道什么时候起，你们有了这样一种幻想，认为生存是唾手可得的，这就是你们失败的根本原因。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-02-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
