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

candc++

666

yulu0lu0

学习！感谢！

jjjjhahahah

aaaaaaaaaaaaaa

Legend丶Hu

我只想看答案

pavelgu1991

看答案

grf1973

state0 = [0,0]   #勺子的初始状态
maxv = [7,11]    #每个勺子的对应的容积
def nextstate(state0):    #对于状态state0，推出所有可能的下一状态
    a,b=state0[0],state0[1]    
    if a>0:   #倒空某个勺子
        yield [0,b]
    if b>0:
        yield [a,0]

    if a<maxv[0]:
        yield [maxv[0],b]  #从酒缸里装满某个勺子
        tmp=maxv[0]-a   #差值
        if b>=tmp:            
            yield [maxv[0],b-tmp]
        else:
            yield [a+b,0]

    if b<maxv[1]:
        yield [a,maxv[1]]    
        tmp=maxv[1]-b   #差值
        if a>=tmp:            
            yield [a-tmp,maxv[1]]
        else:
            yield [0,a+b]
 
n=0
from collections import deque
res =[]
def findway(ways):        
    global n  #多少种方法            
    for state in nextstate(ways[-1]):        #遍历下一状态（ways[-1]表示最后一个状态）
        if state not in ways:         #当前状态未出现过。
            ways.append(state)    #添加新结果
            if state[0] == 2 or state[1]==2:
                n+=1                
                print('第%d种，共%d步：' %(n,len(ways)),ways)    #输出结果                
                res.append(deque(ways))
            else:
                findway(ways)  #递归搜索
            ways.pop()   #去除当前循环中添加的状态（回归上一级，搜索另一支线。）
    

findway([state0])
bestway=sorted(res,key=lambda x:len(x))[0]
print("最佳路径(共"+str(len(bestway))+"步)：")
for x in bestway:
    print(x)

grf1973

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

state0 = [0,0]   #勺子的初始状态
maxv = [7,11]    #每个勺子的对应的容积
def nextstate(state0):    #对于状态state0，推出所有可能的下一状态
    a,b=state0[0],state0[1]
    res=[(0,b),(a,0),(maxv[0],b),(a,maxv[1])]    #清空，加满        
    delta=maxv[0]-a if b>=maxv[0]-a else b   #b-->a
    res.append((a+delta,b-delta)) 
    delta=maxv[1]-b if a>=maxv[1]-b else a   #a-->b
    res.append((a-delta,b+delta))        
    res=list(set(res))
    if (a,b) in res:
        res.remove((a,b))
    return res
 
from collections import deque
res =[]
def findway(ways):            
    for state in nextstate(ways[-1]):        #遍历下一状态（ways[-1]表示最后一个状态）
        if state not in ways:         #当前状态未出现过。
            ways.append(state)    #添加新结果
            if state[0] == 2 or state[1]==2:                
                res.append(deque(ways))
            else:
                findway(ways)  #递归搜索
            ways.pop()   #去除当前循环中添加的状态（回归上一级，搜索另一支线。）    

findway([state0])
bestway=sorted(res,key=lambda x:len(x))[0]
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