python小练习（065）：探索法（广度优先搜索）30行代码求解倒酒问题

candc++

666

yulu0lu0

学习！感谢！

jjjjhahahah

aaaaaaaaaaaaaa

Legend丶Hu

我只想看答案

pavelgu1991

看答案

grf1973

1. state0 = [0,0]   #勺子的初始状态
   
2. maxv = [7,11]    #每个勺子的对应的容积
   
3. def nextstate(state0):    #对于状态state0，推出所有可能的下一状态
   
4.     a,b=state0[0],state0[1]   
   
5.     if a>0:   #倒空某个勺子
   
6.         yield [0,b]
   
7.     if b>0:
   
8.         yield [a,0]
   
9. 
   
10.     if a<maxv[0]:
    
11.         yield [maxv[0],b]  #从酒缸里装满某个勺子
    
12.         tmp=maxv[0]-a   #差值
    
13.         if b>=tmp:            
    
14.             yield [maxv[0],b-tmp]
    
15.         else:
    
16.             yield [a+b,0]
    
17. 
    
18.     if b<maxv[1]:
    
19.         yield [a,maxv[1]]   
    
20.         tmp=maxv[1]-b   #差值
    
21.         if a>=tmp:            
    
22.             yield [a-tmp,maxv[1]]
    
23.         else:
    
24.             yield [0,a+b]
    
25. 
    
26. n=0
    
27. from collections import deque
    
28. res =[]
    
29. def findway(ways):        
    
30.     global n  #多少种方法            
    
31.     for state in nextstate(ways[-1]):        #遍历下一状态（ways[-1]表示最后一个状态）
    
32.         if state not in ways:         #当前状态未出现过。
    
33.             ways.append(state)    #添加新结果
    
34.             if state[0] == 2 or state[1]==2:
    
35.                 n+=1               
    
36.                 print('第%d种，共%d步：' %(n,len(ways)),ways)    #输出结果               
    
37.                 res.append(deque(ways))
    
38.             else:
    
39.                 findway(ways)  #递归搜索
    
40.             ways.pop()   #去除当前循环中添加的状态（回归上一级，搜索另一支线。）
    
41.    
    
42. 
    
43. findway([state0])
    
44. bestway=sorted(res,key=lambda x:len(x))[0]
    
45. print("最佳路径(共"+str(len(bestway))+"步)：")
    
46. for x in bestway:
    
47.     print(x)

复制代码

grf1973

改一下，不超过30行代码。。。。。。

1. state0 = [0,0]   #勺子的初始状态
   
2. maxv = [7,11]    #每个勺子的对应的容积
   
3. def nextstate(state0):    #对于状态state0，推出所有可能的下一状态
   
4.     a,b=state0[0],state0[1]
   
5.     res=[(0,b),(a,0),(maxv[0],b),(a,maxv[1])]    #清空，加满        
   
6.     delta=maxv[0]-a if b>=maxv[0]-a else b   #b-->a
   
7.     res.append((a+delta,b-delta))
   
8.     delta=maxv[1]-b if a>=maxv[1]-b else a   #a-->b
   
9.     res.append((a-delta,b+delta))        
   
10.     res=list(set(res))
    
11.     if (a,b) in res:
    
12.         res.remove((a,b))
    
13.     return res
    
14. 
    
15. from collections import deque
    
16. res =[]
    
17. def findway(ways):            
    
18.     for state in nextstate(ways[-1]):        #遍历下一状态（ways[-1]表示最后一个状态）
    
19.         if state not in ways:         #当前状态未出现过。
    
20.             ways.append(state)    #添加新结果
    
21.             if state[0] == 2 or state[1]==2:               
    
22.                 res.append(deque(ways))
    
23.             else:
    
24.                 findway(ways)  #递归搜索
    
25.             ways.pop()   #去除当前循环中添加的状态（回归上一级，搜索另一支线。）   
    
26. 
    
27. findway([state0])
    
28. bestway=sorted(res,key=lambda x:len(x))[0]
    
29. print("最佳路径(共"+str(len(bestway))+"步)：",[x for x in bestway])

复制代码

zhangjk19841984

学习虚席

Cysonix

WOZHISHIWEILEANDAN

卡卡西998

不懂得东西，来学习了

晓屁屁

算法不会

咕咕鸡鸽鸽

kankan

红旗下的黑蛋

我只是为了看答案

acherat

探究下代码中的秘密

GeminiJay

nihao

kaka6k66kjie

帅

guojinnan

看看答案，最近有点不太会

Spirit_zoro

da

xgq789

标记

dulefei

KKK