这个题目的版本非常之多，有微软版的，腾讯版的，新浪版的等等，最常见的是:
有容量为a,b的2个水桶,需要得到c升的水.
UPDATE:
1.重新实现了方案b,要么a->b不停的倒,要么b->a不停的倒,直到目标出现或者水量重复(无解).
2.比较两种方案可以获得最佳方案.
3.根据checkio题目要求,输出倒水步骤:01表示填满a,12表示从a倒入b,20表示倒空b.(0,水源,1,第一个水桶,2,第二个水桶)
def checkio(a,b,c):
print '------------------------------------------------'
print '[A=%d] [B=%d] [C=%d] (target is C)' % (a,b,c)
history = [] # pour history
wlist = [(0,0)] # water of a,b
# a->b repeadily
while 1:
# full a
if wlist[-1][0]==0:
wlist.append((a,wlist[-1][1]))
history.append('01')
if c in wlist[-1] or wlist[-1] in wlist[:-1]: break
# empty b
if wlist[-1][1]==b:
wlist.append((wlist[-1][0],0))
history.append('20')
if c in wlist[-1] or wlist[-1] in wlist[:-1]: break
# a->b
if sum(wlist[-1])<=b:
wlist.append((0,sum(wlist[-1])))
else:
wlist.append((sum(wlist[-1])-b,b))
history.append('12')
if c in wlist[-1] or wlist[-1] in wlist[:-1]: break
print 'A->B:',wlist
list1 = [] # solution1
hist1 = []
if c in wlist[-1]: # found solution
list1 = wlist[:]
hist1 = history[:]
else: # no solution
list1 = []
hist1 = []
# exchange a,b
history = []
wlist = [(0,0)]
# b->a repeadily
while 1:
# full b
if wlist[-1][1]==0:
wlist.append((wlist[-1][0],b))
history.append('02')
if c in wlist[-1] or wlist[-1] in wlist[:-1]: break
# empty a
if wlist[-1][0]==a:
wlist.append((0,wlist[-1][1]))
history.append('10')
if c in wlist[-1] or wlist[-1] in wlist[:-1]: break
# b->a
if sum(wlist[-1])<=a:
wlist.append((sum(wlist[-1]),0))
else:
wlist.append((a,sum(wlist[-1])-a))
history.append('21')
if c in wlist[-1] or wlist[-1] in wlist[:-1]: break
print 'B->A:',wlist
list2 = [] # solution2
hist2 = []
if c in wlist[-1]: # found solution
list2 = wlist[:]
hist2 = history[:]
else:
list2 = []
hist2 = []
# compare the solutions to have minimal steps
result = []
if not list1 and not list2:
result = []
print 'No solution'
return result
elif not list1:
wlist = list2
result = hist2
elif not list2:
wlist = list1
result = hist1
else:
wlist = len(list1)<len(list2) and list1 or list2
result = len(list1)<len(list2) and hist1 or hist2
# print the result
for item in wlist[1:]:
print item[0],item[1]
# return the result
print 'Optimal solution:',wlist
print 'Done'
print '------------------------------------------------'
return result
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
print(checkio(5, 7, 6)) # ['02', '21', '10', '21', '02', '21', '10', '21', '02', '21']
print(checkio(3, 4, 1)) # ["02", "21"]
print(checkio(2, 1, 1)) # ["02"]
print(checkio(2, 7, 1))
结果:>>> ================================ RESTART ================================ >>> ------------------------------------------------ [A=5] [B=7] [C=6] (target is C) A->B: [(0, 0), (5, 0), (0, 5), (5, 5), (3, 7), (3, 0), (0, 3), (5, 3), (1, 7), (1, 0), (0, 1), (5, 1), (0, 6)] B->A: [(0, 0), (0, 7), (5, 2), (0, 2), (2, 0), (2, 7), (5, 4), (0, 4), (4, 0), (4, 7), (5, 6)] 0 7 5 2 0 2 2 0 2 7 5 4 0 4 4 0 4 7 5 6 Optimal solution: [(0, 0), (0, 7), (5, 2), (0, 2), (2, 0), (2, 7), (5, 4), (0, 4), (4, 0), (4, 7), (5, 6)] Done ------------------------------------------------ ['02', '21', '10', '21', '02', '21', '10', '21', '02', '21'] ------------------------------------------------ [A=3] [B=4] [C=1] (target is C) A->B: [(0, 0), (3, 0), (0, 3), (3, 3), (2, 4), (2, 0), (0, 2), (3, 2), (1, 4)] B->A: [(0, 0), (0, 4), (3, 1)] 0 4 3 1 Optimal solution: [(0, 0), (0, 4), (3, 1)] Done ------------------------------------------------ ['02', '21'] ------------------------------------------------ [A=2] [B=1] [C=1] (target is C) A->B: [(0, 0), (2, 0), (1, 1)] B->A: [(0, 0), (0, 1)] 0 1 Optimal solution: [(0, 0), (0, 1)] Done ------------------------------------------------ ['02'] ------------------------------------------------ [A=2] [B=7] [C=1] (target is C) A->B: [(0, 0), (2, 0), (0, 2), (2, 2), (0, 4), (2, 4), (0, 6), (2, 6), (1, 7)] B->A: [(0, 0), (0, 7), (2, 5), (0, 5), (2, 3), (0, 3), (2, 1)] 0 7 2 5 0 5 2 3 0 3 2 1 Optimal solution: [(0, 0), (0, 7), (2, 5), (0, 5), (2, 3), (0, 3), (2, 1)] Done ------------------------------------------------ ['02', '21', '10', '21', '10', '21'] >>>
解法肯定有很多，可以用宽度优先搜索（BFS），也可以用穷举法。
这里列2个很有意思的解决方案,第一个很巧妙,可以手动解决,第二个则是终极(不一定是最优)解决办法,特别适合计算机完成.
# 解决思路:
# a,有限状态机 ,可以画图解决
# http://www.cnblogs.com/wisdomqq/archive/2009/09/22/1571520.html
# b,不断取余,不一定是最优解. 基本思想是用：用一个桶容量的倍数对另一个桶的容量取余。
# http://blog.csdn.net/morewindows/article/details/7481851
方案B的实现代码:
#! /usr/bin/env python
# coding=utf-8
# 倒水问题, 有容量为a,b的2个水桶,需要得到c升的水
# 解决思路:
# a,有限状态机 ,可以画图解决
# http://www.cnblogs.com/wisdomqq/archive/2009/09/22/1571520.html
# b,不断取余,不一定是最优解
# http://blog.csdn.net/morewindows/article/details/7481851
# 使用b方法,不停取余
def solve_2(a,b,c):
wlist = [(0,0)] # 水量
qlist = [] # 余数列表,如果不管怎么倒都循环,无解决方案
t = a # a的倍数
while 1:
# 装满A
wlist.append((a,wlist[-1][1]))
# A倒入B
if sum(wlist[-1])<=b:
wlist.append((0,wlist[-1][0]+wlist[-1][1]))
else:
wlist.append((sum(wlist[-1])-b,b))
if t%b in qlist:
break
else:
qlist.append(t%b)
# 倒空B后A倒入B
if wlist[-1][1]==b:
wlist.append((wlist[-1][0],0))
wlist.append((0,wlist[-1][0]))
# 判断余数是否循环
if t%b==c:
break
t += a
# 无方案,交换a,b再来一次
if c not in wlist[-1]:
wlist = [(0,0)]
qlist = []
a,b = b,a
t = a
while 1:
# 装满A
wlist.append((a,wlist[-1][1]))
# A倒入B
if sum(wlist[-1])<=b:
wlist.append((0,wlist[-1][0]+wlist[-1][1]))
else:
wlist.append((sum(wlist[-1])-b,b))
if t%b in qlist:
break
else:
qlist.append(t%b)
# 倒空B后A倒入B
if wlist[-1][1]==b:
wlist.append((wlist[-1][0],0))
wlist.append((0,wlist[-1][0]))
# 判断余数是否循环
if t%b==c:
break
t += a
# 交换后还是无法解决
if c not in wlist[-1]:
print '[A=%d] [B=%d] [C=%d] (target is C)' % (b,a,c)
print 'No possible solution'
else:
print '[A=%d] [B=%d] [C=%d] (target is C)' % (b,a,c)
print '------------------------------------------------'
print 'One possible solution is (not necessaryly to be optimal):'
for item in wlist[1:]:
if item[0]==a:
print '%8s A : %d B : %d' % ('Full B',item[1],item[0])
elif item[0]<a and item[1]!=0:
print '%8s A : %d B : %d' % ('B -> A',item[1],item[0])
elif item[1]==0:
print '%8s A : %d B : %d' % ('Empty A',item[1],item[0])
print 'Done'
print '------------------------------------------------'
else:
print '[A=%d] [B=%d] [C=%d] (target is C)' % (a,b,c)
print '------------------------------------------------'
print 'One possible solution is (not necessary to be optimal):'
for item in wlist[1:]:
if item[0]==a:
print '%8s A : %d B : %d' % ('Full A',item[0],item[1])
elif item[0]<a and item[1]!=0:
print '%8s A : %d B : %d' % ('A -> B',item[0],item[1])
elif item[1]==0:
print '%8s A : %d B : %d' % ('Empty B',item[0],item[1])
print 'Done'
print '------------------------------------------------'
def main():
solve_2(5,8,6)
if __name__ == '__main__':
main()
测试结果:>>> ================================ RESTART ================================ >>> [A=5] [B=8] [C=6] (target is C) ------------------------------------------------ One possible solution is (not necessary to be optimal): Full A A : 5 B : 0 A -> B A : 0 B : 5 Full A A : 5 B : 5 A -> B A : 2 B : 8 Empty B A : 2 B : 0 A -> B A : 0 B : 2 Full A A : 5 B : 2 A -> B A : 0 B : 7 Full A A : 5 B : 7 A -> B A : 4 B : 8 Empty B A : 4 B : 0 A -> B A : 0 B : 4 Full A A : 5 B : 4 A -> B A : 1 B : 8 Empty B A : 1 B : 0 A -> B A : 0 B : 1 Full A A : 5 B : 1 A -> B A : 0 B : 6 Done ------------------------------------------------
No comments :
Post a Comment