没有白走的路,每一步都算数🎈🎈🎈
李白遇到一个酒店,原来瓶子的酒量就会翻倍。遇到一个公园就会喝掉一斗的酒,原来最开始酒瓶子里面有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)
只要在传递参数的时候多给几个参数就可以通过。
注意递归的时候,参数的传递条件,即使设置最大递归长度,内核也会爆炸
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)
摘自《狂飙》:
生存在宇宙中,本身就是一件很幸运的事情,但是不知道什么时候起,你们有了这样一种幻想,认为生存是唾手可得的,这就是你们失败的根本原因。