Go语言视频零基础入门到精通

javalearner

两个小孩去打油，一人带了一个一斤的空瓶，另一个带了一个七两、一个三两的空瓶。原计划各打一斤油，可是由于所带的钱不够，只好两人合打了一斤油，在回家的路上，二人想平分这一斤油，可是又没有其它工具。试仅用三个瓶子(一斤、七两、三两)精确地分出两个半斤油来。

1. import java.util.*;
   
2. class Bottle {      //瓶子类
   
3.   int volume = 0;   //总容量
   
4.   int oil = 0;     //瓶中油的量
   
5. public Bottle(int v, int o) {
   
6.    if( o <= v) {
   
7.     volume = v;
   
8.     oil = o;
   
9.    }
   
10.    else
    
11.     System.out.println("Bottle init error oil > volume");
    
12. }
    
13. public boolean isEmpty() {    //瓶子是否空
    
14.    if(oil == 0)
    
15.     return true;
    
16.    else
    
17.     return false;
    
18. }
    
19. public boolean isFull() {    //瓶子是否满
    
20.    if(oil == volume)
    
21.     return true;
    
22.    else
    
23.     return false;
    
24. }
    
25. public int needForFull() {    //还需多少才能满
    
26.    return volume - oil;
    
27. }
    
28. public String toString() {
    
29.    return "Bottle_v="+ volume+" Oil="+oil;
    
30. }
    
31. }
    
32. class StateNode {      //状态节点类
    
33. Bottle bottle1;     
    
34. Bottle bottle2;
    
35. Bottle bottle3;
    
36. StateNode parentState;   //父节点
    
37. public StateNode(int b1, int b2, int b3, StateNode parent) {
    
38.    bottle1 = new Bottle(10, b1);    //容量为10的瓶子
    
39.    bottle2 = new Bottle(7, b2);    //容量为7的瓶子
    
40.    bottle3 = new Bottle(3, b3);    //容量为3的瓶子
    
41.    parentState = parent;
    
42. }
    
43. public String toString() {
    
44.    return "[" + bottle1.oil +" "+ bottle2.oil +" "+ bottle3.oil + "]";
    
45. }
    
46. public boolean isTargetState() {     //判断是否为目标节点
    
47.    if(bottle1.oil == 5 && bottle2.oil == 5 )
    
48.     return true;
    
49.    else
    
50.     return false;
    
51. }
    
52. public boolean eqauls(StateNode s) {     //判断是否为同一状态
    
53.    if( s.bottle1.oil == this.bottle1.oil &&
    
54.     s.bottle2.oil == this.bottle2.oil &&
    
55.     s.bottle3.oil == this.bottle3.oil)
    
56.     return true;
    
57.    else
    
58.     return false;
    
59. }
    
60. public void printStep(){       //打印从起始状态到当前状态的转换步骤
    
61.    if(parentState != null)
    
62.     parentState.printStep();
    
63.    
    
64.    System.out.println(toString());
    
65. }
    
66. public StateNode expandStateNode(int n) {   //广度优先扩展状态节点
    
67.    StateNode newState = null;
    
68.    boolean isExpand = false;
    
69.   
    
70.    //分六种情况扩展节点状态
    
71.    //可以扩展则返回扩展后的新状态节点
    
72.    //如不能扩展则返回null
    
73.   
    
74.   switch(n) {
    
75.    case 1:             //瓶子1向瓶子2倒油
    
76.     if(!bottle1.isEmpty() && !bottle2.isFull()) {
    
77.      n = bottle2.needForFull() <= bottle1.oil ? bottle2.needForFull() : bottle1.oil;
    
78.      newState = new StateNode(bottle1.oil-n, bottle2.oil+n, bottle3.oil, this);
    
79.     }
    
80.     break;
    
81.    case 2:          //瓶子1向瓶子3倒油
    
82.     if(!bottle1.isEmpty() && !bottle3.isFull()) {
    
83.      n = bottle3.needForFull() <= bottle1.oil ? bottle3.needForFull() : bottle1.oil;
    
84.      newState = new StateNode(bottle1.oil-n, bottle2.oil, bottle3.oil+n, this);
    
85.     }
    
86.     break;
    
87.    case 3:      //瓶子2向瓶子1倒油
    
88.     if(!bottle2.isEmpty() && !bottle1.isFull()) {
    
89.      n = bottle1.needForFull() <= bottle2.oil ? bottle1.needForFull() : bottle2.oil;
    
90.      newState = new StateNode(bottle1.oil+n, bottle2.oil-n, bottle3.oil, this);
    
91.     }
    
92.     break;
    
93.    case 4:      //瓶子2向瓶子3倒油
    
94.     if(!bottle2.isEmpty() && !bottle3.isFull()) {
    
95.      n = bottle3.needForFull() <= bottle2.oil ? bottle3.needForFull() : bottle2.oil;
    
96.      newState = new StateNode(bottle1.oil, bottle2.oil-n, bottle3.oil+n, this);
    
97.     }
    
98.     break;
    
99.    case 5:     //瓶子3向瓶子1倒油
    
100.     if(!bottle3.isEmpty() && !bottle1.isFull()) {
     
101.      n = bottle1.needForFull() <= bottle3.oil ? bottle1.needForFull() : bottle3.oil;
     
102.      newState = new StateNode(bottle1.oil+n, bottle2.oil, bottle3.oil-n, this);
     
103.     }
     
104.     break;
     
105.    case 6:     //瓶子3向瓶子2倒油
     
106.     if(!bottle3.isEmpty() && !bottle2.isFull()) {
     
107.      n = bottle2.needForFull() <= bottle3.oil ? bottle2.needForFull() : bottle3.oil;
     
108.      newState = new StateNode(bottle1.oil, bottle2.oil+n, bottle3.oil-n, this);
     
109.     }
     
110.     break;
     
111.    }
     
112.    return newState;
     
113. }
     
114. }
     
115. public class PartitionOil {
     
116. public static void main(String[] args) {
     
117.    Queue< StateNode> stateQueue = new LinkedList< StateNode>();   //存放要扩展的状态节点的队列
     
118.     //存放所有出现过的状态的数组 用来判断某个状态是否出现过
     
119.    ArrayList< StateNode> stateList = new ArrayList< StateNode>();  
     
120.   
     
121.    StateNode initialState = new StateNode(10, 0, 0, null);     //初始状态10 0 0
     
122.   
     
123.    stateQueue.offer(initialState);
     
124.    stateList.add(initialState);
     
125.   
     
126.    while(!stateQueue.isEmpty()) {     
     
127.     StateNode temp = stateQueue.poll();    //取队列头节点
     
128.    for(int i = 1; i <= 6; i++) {       //每个节点分六种情况进行扩展
     
129.      StateNode newState = temp.expandStateNode(i); //扩展节点
     
130.      if(newState != null) {
     
131.       if(newState.isTargetState()){     //是否为目标状态
     
132.        System.out.println("----------Find target!!!---------");
     
133.        newState.printStep();
     
134.        return;
     
135.       }
     
136.      
     
137.       boolean tag = false;        //判断状态是否出现过
     
138.      for(int j = 0; j < stateList.size(); j++){   //如出现过 跳过
     
139.        if(newState.eqauls(stateList.get(j))){   
     
140.         tag = true;
     
141.         break;
     
142.        }
     
143.       }
     
144.      
     
145.       if(!tag) {         //如没出现过 加入状态队列和数组
     
146.        stateQueue.offer(newState);  
     
147.        stateList.add(newState);
     
148.       }
     
149.      }
     
150.     }
     
151.    }
     
152. }
     
153. }
     

复制代码

C:java>java PartitionOil
----------Find target!!!---------
[10 0 0]
[3 7 0]
[3 4 3]
[6 4 0]
[6 1 3]
[9 1 0]
[9 0 1]
[2 7 1]
[2 5 3]
[5 5 0]

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/12/7/000715921.zip