[原]用DFS解决水桶问题
问题的引入：有三个没有刻度的桶，容量分别为3升、5升、8升。现在8升的桶是满的，你可以将水在桶中倒来倒去。 例如，首先8->3，那么8升桶内将会有5升水，3升桶会被装满；然后3->5，那么3升桶将被倒空，5升桶 内将有3升水。你的目标是平分这8升水，即使5升桶和8升桶内均有4升水。(ps：据说这是一个中学生的题目，大大的伤感了半天。) 按照题目的设计，可以尝试采用DFS来搜索结果。 于是有了一下的程序，过程没有做优化，而且作为DFS的尝试，应该有很多地方不太合理。(注：程序采用java编 写) /**************************DFSSloveTankProblem.java***************************/public class DFSSloveTankProblem { //记录找到的节点，避免重复节点出现 Node recordFinded; //找到的节点记录的初始节点 Node FNode; DFSSloveTankProblem() { //寻找的第一个节点 Node firstNode = new Node(); firstNode.c3V = 0; firstNode.c5V = 0; firstNode.c8V = 8; //记录找到的节点 recordFinded = new Node(); recordFinded.c3V = 0; recordFinded.c5V = 0; recordFinded.c8V = 8; FNode = new Node(); FNode.child = new Node[1]; FNode.child[0] = recordFinded; //开始寻找 DFS(firstNode); } /** * 按照深度搜索的方法 * @param node */ public void DFS(Node node) { if (process(node)) { //输出结果 System.out.println("find result!"); Node nodeIdx; nodeIdx = node; while (nodeIdx.parent != null) { System.out.println("nodeIdx=" + nodeIdx); System.out.println("3V=" + nodeIdx.c3V); System.out.println("5V=" + nodeIdx.c5V); System.out.println("8V=" + nodeIdx.c8V); nodeIdx = nodeIdx.parent; } return; } //标记 mark(node); //寻找其子节点 for (int i = 0; i < node.child.length;…