首页 > 代码库 > 分酒问题
分酒问题
一个装满8升酒的瓶子，另外只有一个5升的空瓶子和一个3升的空瓶子，问怎样倒可以把酒一丝不差的分成两个4升?
学习MIT的公开课计算机科学入门课程6.001x和6.002x将近一个学期了，我几乎把它当作第一重要的事情，每天早晨第一件事就是学习这门公开课。我确信我有很大的收获，正如他们的宗旨用计算思维解决真实问题using computation to solve real problem，我想计算思维是学习这门课最大的收获。
最近看书，碰巧看到一个题目
“一个装满8升酒的瓶子，另外只有一个5升的空瓶子和一个3升的空瓶子，问怎样倒可以把酒一丝不差的分成两个4升?”
像是一道小学的奥数题，没准当年我遇到过，让我苦恼过。
现在看来题目还是趣味十足，但也难度十足，如果真要我做，我想我肯定能做出来，因为我这么多年的学习让我感到，面对再困难的问题，去尝试就有可能得到解答。
但现在嘛，我变得更不一样了，我可以用算法来解决这个问题。现在我知道这可以看成是一个图搜索问题，每一个节点是酒的一种状态，每一条边是倒酒所导致状态的切换。
选择广度优先搜索，第一个给出的答案是操作次数最短的，同时根据搜索过程动态产生节点。
没想到总共找到了16种结果，但每一种看起来都不太一样。最少的一种需要操作7次，quite FUN!
1 volume = [8, 5, 3] 2 3 class state(object): 4 def __init__(self, one, two, three): 5 self.v = [one, two, three] 6 7 def transition(self, src, to): 8 newV = self.v[:] #caution list is mutable 9 if self.v[src] < volume[to] - self.v[to]:10 pour = self.v[src]11 else:12 pour = volume[to] - self.v[to]13 newV[src] = self.v[src] - pour14 newV[to] = self.v[to] + pour15 return state(newV[0],newV[1],newV[2])16 17 def __eq__(self, other):18 return self.v == other.v19 20 def __str__(self):21 return "%s %s %s" % (self.v[0], self.v[1], self.v[2])22 23 24 def BFSWithGeneratorAll(start, end, q=[]):25 initPath = [start]26 q.append(initPath)27 paths = []28 while len(q) > 0:29 tmpPath = q.pop(0)30 lastNode = tmpPath[-1]31 if lastNode == end:32 paths.append(tmpPath)33 for (src, to) in zip([0,0,1,1,2,2],[1,2,0,2,0,1]):34 new = lastNode.transition(src,to)35 if new not in tmpPath:36 newPath = tmpPath + [new]37 q.append(newPath)38 return paths39 40 def printSolution(path):41 for elt in path:42 print elt43 44 start = state(8,0,0)45 end = state(4,4,0)46 47 paths = BFSWithGeneratorAll(start,end)48 for path in paths:49 printSolution(path)50 print
找到的全部结果
8 0 0
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
4 4 0
8 0 0
5 0 3
5 3 0
2 3 3
2 5 1
7 0 1
7 1 0
4 1 3
4 4 0
8 0 0
5 0 3
0 5 3
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
4 4 0
8 0 0
5 0 3
5 3 0
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
4 4 0
8 0 0
3 5 0
0 5 3
5 0 3
5 3 0
2 3 3
2 5 1
7 0 1
7 1 0
4 1 3
4 4 0
8 0 0
3 5 0
3 2 3
5 0 3
5 3 0
2 3 3
2 5 1
7 0 1
7 1 0
4 1 3
4 4 0
8 0 0
3 5 0
3 2 3
0 5 3
5 0 3
5 3 0
2 3 3
2 5 1
7 0 1
7 1 0
4 1 3
4 4 0
8 0 0
5 0 3
5 3 0
2 3 3
0 5 3
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
4 4 0
8 0 0
5 0 3
5 3 0
2 3 3
2 5 1
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
4 4 0
8 0 0
3 5 0
3 2 3
6 2 0
6 0 2
5 0 3
5 3 0
2 3 3
2 5 1
7 0 1
7 1 0
4 1 3
4 4 0
8 0 0
5 0 3
5 3 0
2 3 3
2 5 1
0 5 3
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
4 4 0
8 0 0
5 0 3
5 3 0
2 3 3
2 5 1
7 0 1
7 1 0
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
4 4 0
8 0 0
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
0 5 3
5 0 3
5 3 0
2 3 3
2 5 1
7 0 1
7 1 0
4 1 3
4 4 0
8 0 0
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
5 0 3
5 3 0
2 3 3
2 5 1
7 0 1
7 1 0
4 1 3
4 4 0
8 0 0
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
0 5 3
5 0 3
5 3 0
2 3 3
2 5 1
7 0 1
7 1 0
4 1 3
4 4 0
8 0 0
5 0 3
5 3 0
2 3 3
2 5 1
7 0 1
7 1 0
4 1 3
0 5 3
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
4 4 0
分酒问题