[原]用DFS解决水桶问题

[原]用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; i++) {
   //只寻找未做标记的节点
   if (!node.child[i].marked) {
    DFS(node.child[i]);
   }
  }
 }
 /**
  * 标记不需要寻找的节点
  * @param node
  */
 public void mark(Node node) {
  node.marked = true;
  for (int i = 0; i < node.child.length; i++) {
   if (!node.child[i].marked) {
    Node findLinkedList; //节点指针
    findLinkedList = FNode;
    boolean finded = false;
    while (findLinkedList.child != null) {
     //在已经找到的节点中寻找,是否本节点已经存在,如果
是,则以后不在重复寻找
     findLinkedList = findLinkedList.child[0];
     if (node.child[i].c3V == findLinkedList.c3V
       && node.child[i].c5V ==
findLinkedList.c5V
       && node.child[i].c8V ==
findLinkedList.c8V) {
      node.child[i].marked = true;
      finded = true;
     }
    }
    if (!finded) {
     //如果没有这个节点值的记录,则加入到记录节点中
     findLinkedList.child = new Node[1];
     Node tmp = new Node();
     tmp.c3V = node.child[i].c3V;
     tmp.c5V = node.child[i].c5V;
     tmp.c8V = node.child[i].c8V;
     findLinkedList.child[0] = tmp;
    }
   }
  }
 }
 /**
  * 对节点进行处理,进行水桶倒水过程
  * @param node
  * @return
  */
 public boolean process(Node node) {
  System.out.println("3V=" + node.c3V);
  System.out.println("5V=" + node.c5V);
  System.out.println("8V=" + node.c8V);
  if (node.c3V == 0 && node.c5V == 4 && node.c8V == 4) {
   return true;
  }
  Node[] tmpN = new Node[6];
  // System.out.println("put 3-> 5");
  tmpN[0] = new Node();
  tmpN[0].parent = node;
  byte sumV = (byte) Math.abs(node.c3V + node.c5V);
  byte nV = sumV > 5 ? 5 : sumV;
  tmpN[0].c3V = (byte) (sumV – nV);
  tmpN[0].c5V = nV;
  tmpN[0].c8V = node.c8V;
  // System.out.println("3V=" + tmpN[0].c3V);
  // System.out.println("5V=" + tmpN[0].c5V);
  // System.out.println("8V=" + tmpN[0].c8V);
  // System.out.println("put 3-> 8");
  tmpN[1] = new Node();
  tmpN[1].parent = node;
  sumV = (byte) Math.abs(node.c3V + node.c8V);
  nV = sumV > 8 ? 8 : sumV;
  tmpN[1].c3V = (byte) (sumV – nV);
  tmpN[1].c5V = node.c5V;
  tmpN[1].c8V = nV;
  // System.out.println("3V=" + tmpN[1].c3V);
  // System.out.println("5V=" + tmpN[1].c5V);
  // System.out.println("8V=" + tmpN[1].c8V);
  // System.out.println("put 5-> 3");
  tmpN[2] = new Node();
  tmpN[2].parent = node;
  sumV = (byte) Math.abs(node.c3V + node.c5V);
  nV = sumV > 3 ? 3 : sumV;
  tmpN[2].c3V = nV;
  tmpN[2].c5V = (byte) (sumV – nV);
  tmpN[2].c8V = node.c8V;
  // System.out.println("3V=" + tmpN[2].c3V);
  // System.out.println("5V=" + tmpN[2].c5V);
  // System.out.println("8V=" + tmpN[2].c8V);
  // System.out.println("put 5-> 8");
  tmpN[3] = new Node();
  tmpN[3].parent = node;
  sumV = (byte) Math.abs(node.c5V + node.c8V);
  nV = sumV > 8 ? 8 : sumV;
  tmpN[3].c3V = node.c3V;
  tmpN[3].c5V = (byte) (sumV – nV);
  tmpN[3].c8V = nV;
  // System.out.println("3V=" + tmpN[3].c3V);
  // System.out.println("5V=" + tmpN[3].c5V);
  // System.out.println("8V=" + tmpN[3].c8V);
  // System.out.println("put 8-> 3");
  tmpN[4] = new Node();
  tmpN[4].parent = node;
  sumV = (byte) Math.abs(node.c3V + node.c8V);
  nV = sumV > 3 ? 3 : sumV;
  tmpN[4].c3V = nV;
  tmpN[4].c5V = node.c5V;
  tmpN[4].c8V = (byte) (sumV – nV);
  // System.out.println("3V=" + tmpN[4].c3V);
  // System.out.println("5V=" + tmpN[4].c5V);
  // System.out.println("8V=" + tmpN[4].c8V);
  // System.out.println("put 8-> 5");
  tmpN[5] = new Node();
  tmpN[5].parent = node;
  sumV = (byte) Math.abs(node.c5V + node.c8V);
  nV = sumV > 5 ? 5 : sumV;
  tmpN[5].c3V = node.c3V;
  tmpN[5].c5V = nV;
  tmpN[5].c8V = (byte) (sumV – nV);
  // System.out.println("3V=" + tmpN[5].c3V);
  // System.out.println("5V=" + tmpN[5].c5V);
  // System.out.println("8V=" + tmpN[5].c8V);
  node.child = tmpN;
  return false;
 }
}
/**
 * 节点类
 *
 * @author roye
 *
 */
class Node {
 boolean marked; // 是否已经寻找过
 Node[] child; //结点的child
 Node parent; //节点的parent
 byte c3V; // 3L桶容量
 byte c5V; // 5L桶容量
 byte c8V; // 8L桶容量
}
/**************************DFSSloveTankProblem.java***************************/
执行程序后输出的结果(从后面的节点往前输出)
find result!
nodeIdx=Node@47858e
3V=0
5V=4
8V=4
nodeIdx=Node@19134f4
3V=3
5V=1
8V=4
nodeIdx=Node@2bbd86
3V=0
5V=1
8V=7
nodeIdx=Node@1a7bf11
3V=1
5V=0
8V=7
nodeIdx=Node@1f12c4e
3V=1
5V=5
8V=2
nodeIdx=Node@93dee9
3V=3
5V=3
8V=2
nodeIdx=Node@fabe9
3V=0
5V=3
8V=5
nodeIdx=Node@df6ccd
3V=3
5V=0
8V=5

6 thoughts on “[原]用DFS解决水桶问题

  1. wow gold
    lotro gold
    wow gold
    World of Warcraft gold
    wow power leveling
    wow power leveling
    wow power leveling
    Watch Rolex
    Rolex Watch
    rs gold
    power leveling
    power leveling
    power leveling
    power leveling
    power leveling
    power leveling
    cheap wow gold
    cheap wow gold
    cheap wow gold
    World of Warcraft power leveling
    World of Warcraft power leveling
    World of Warcraft power leveling
    World of Warcraft power leveling
    World of Warcraft power leveling
    World of Warcraft power leveling
    World of Warcraft power leveling
    World of Warcraft power leveling
    gold wow
    gold wow
    gold wow
    gold wow
    gold wow
    gold wow -132260965195266

  2. Hi,Do you need advertising displays, digital signages, advertising player and LCD displays? Please go Here:www.amberdigital.com.hk(Amberdigital).we have explored and developed the international market with professionalism. We have built a widespread marketing network, and set up a capable management team dedicated to provide beyond-expectation services to our customers.
    amberdigital Contact Us
    E-mail:sstar@netvigator.com
    website:www.amberdigital.com.hk
    alibaba:amberdigital.en.alibaba.com[i

  3. Hi,Do you have second hand lcds, used laptop lcds and used LCD displays? Please go here:www.sstar-hk.com(Southern Stars).We are constantly buying re-usable LCD panels.We recycled LCDs.The re-usable panels go through strictly designed process of categorizing, checking, testing, repairing and refurbishing before they are re-used to make remanufactured LCD displays and TV sets.Due to our recent breakthrough in testing and repairing technology of LCD, we can improve the value for your LCD panels.
    website:www.sstar-hk.com[bcfbhdifechghhh]

  4. wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling
    wow power leveling -228974317503016

  5. Hi,Do you need digital signages, advertising displays, digital sign, advertisement displays and advertising players? Please go Here:www.amberdigital.com.hk(Amberdigital).we have explored and developed the international market with professionalism. We have built a widespread marketing network, and set up a capable management team dedicated to provide beyond-expectation services to our customers.
    amberdigital Contact Us
    website:www.amberdigital.com.hk
    alibaba:amberdigital.en.alibaba.com[igafgfhggadbic]

Leave a Reply

Your email address will not be published. Required fields are marked *