用3单位和5单位的桶量出4单位的水
这个问题比较古老吧，看少年包青天--天芒传奇里面的公孙策就给出了答案了，其实很多人自己乱画一下，2，3分钟就得出结果了。
这里用py写出来，使用了广度优先搜索策略，之后又调试，总共用了40多分钟，惭愧。只是想练习一下py的使用而已。
#coding=utf-8 #如果你有一个3夸脱的水桶和一个5夸脱的水桶，如何准确量出4夸脱的水？ def getTransduction(m,n): trans = [] trans.append( lambda a,b:(0,b) ) #把第1个桶倒空 trans.append( lambda a,b:(a,0) ) #把第2个桶倒空
trans.append( lambda a,b:(m,b) ) #把第1个桶装满 trans.append( lambda a,b:(a,n) ) #把第2个桶装满
trans.append( lambda a,b:( min(m,a+b), a+b-min(m,a+b) ) ) #把桶2倒向桶1，倒满为止 trans.append( lambda a,b:( a+b-min(n,a+b), min(n,a+b) ) ) #把桶1倒向桶2，倒满为止 return trans
def print_track(paths, curr ): if curr['root'] != -1: print_track( paths, paths[ curr['root'] ] ) print curr['status']
def main(m,n,dest): paths = [] #广度搜索队列 paths.append( {'status':(0,0),'root':-1,'cost':0 } ) #添加初始点 allstatus = {} #保存已经找到的状态 allstatus[(0,0)]=True
index = 0 trans = getTransduction(m,n) #获取所有的状态转换函数 result = False #标记查找结果
while index < len(paths): #开始广度搜索 here = paths[index] for fx in trans:
newstatus = fx( here['status'][0], here['status'][1] ) if allstatus.has_key( newstatus ) : #判断新状态是否有记录 continue else: allstatus[newstatus] = True
newone = {} newone['status'] = newstatus newone['root'] = index newone['cost'] = here['cost']+1 paths.append( newone ) #保存进路径表
if dest in newstatus: result = True break if result: break index += 1
if result: #输出结果 print_track( paths, paths[-1] ) else: print '无法到达'
if __name__ == '__main__': main(3,5,4) |
运行结果：
E:\Python相关工具\pythonTEst>python 354.py (0, 0) (0, 5) (3, 2) (0, 2) (2, 0) (2, 5) (3, 4) |
最新评论