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

candc++ 发表于 2018-4-8 21:33:47

666

yulu0lu0 发表于 2018-9-23 14:03:47

学习！感谢！

jjjjhahahah 发表于 2018-10-14 06:01:22

aaaaaaaaaaaaaa

Legend丶Hu 发表于 2018-10-14 11:55:45

我只想看答案

pavelgu1991 发表于 2018-10-15 11:13:27

看答案

grf1973 发表于 2018-10-15 15:18:07

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

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

    if b<maxv:
      yield ]   
      tmp=maxv-b   #差值
      if a>=tmp:            
            yield ]
      else:
            yield

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 == 2 or state==2:
                n+=1               
                print('第%d种，共%d步：' %(n,len(ways)),ways)    #输出结果               
                res.append(deque(ways))
            else:
                findway(ways)#递归搜索
            ways.pop()   #去除当前循环中添加的状态（回归上一级，搜索另一支线。）
   

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

grf1973 发表于 2018-10-15 16:35:23

改一下，不超过30行代码。。。。。。
state0 =    #勺子的初始状态
maxv =     #每个勺子的对应的容积
def nextstate(state0):    #对于状态state0，推出所有可能的下一状态
    a,b=state0,state0
    res=[(0,b),(a,0),(maxv,b),(a,maxv)]    #清空，加满      
    delta=maxv-a if b>=maxv-a else b   #b-->a
    res.append((a+delta,b-delta))
    delta=maxv-b if a>=maxv-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 == 2 or state==2:               
                res.append(deque(ways))
            else:
                findway(ways)#递归搜索
            ways.pop()   #去除当前循环中添加的状态（回归上一级，搜索另一支线。）   

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

zhangjk19841984 发表于 2018-10-22 19:45:15

学习虚席

Cysonix 发表于 2018-11-1 20:21:52

WOZHISHIWEILEANDAN

卡卡西998 发表于 2018-12-28 11:07:01

不懂得东西，来学习了

晓屁屁 发表于 2018-12-28 14:35:28

算法不会

咕咕鸡鸽鸽 发表于 2018-12-28 20:48:29

kankan

红旗下的黑蛋 发表于 2018-12-29 08:22:29

我只是为了看答案

acherat 发表于 2018-12-29 11:21:11

探究下代码中的秘密

GeminiJay 发表于 2019-4-12 10:19:41

nihao

kaka6k66kjie 发表于 2019-4-12 11:30:56

帅

guojinnan 发表于 2019-11-18 15:13:58

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

Spirit_zoro 发表于 2019-11-27 15:55:57

da

xgq789 发表于 2020-2-4 23:58:43

标记

dulefei 发表于 2020-2-9 21:30:41

KKK

查看完整版本: python小练习（065）：探索法（广度优先搜索）30行代码求解倒酒问题