泊松是法国数学家、物理学家和力学家。他一生致力科学事业，成果颇多。有许多著名的公式定理以他的名字命名，比如概率论中著名的泊松分布。
有一次闲暇时，他提出过一个有趣的问题，后称为：“泊松分酒”。在我国古代也提出过类似问题，遗憾的是没有进行彻底探索，其中流传较多是：“韩信走马分油”问题。
有3个容器，容量分别为12升，8升，5升。其中12升中装满油，另外两个空着。要求你只用3个容器操作，最后使得某个容器中正好有6升油。
下面的列表是可能的操作状态记录：
12,0,0
4,8,0
4,3,5
9,3,0
9,0,3
1,8,3
1,6,5
每行3个数据，分别表示12，8，6升容器中的油量
第一行表示初始状态，第二行表示把12升倒入8升容器后的状态，第三行是8升倒入5升，...
当然，同一个题目可能有多种不同的正确操作步骤。
本题目的要求是，请你编写程序，由用户输入：各个容器的容量，开始的状态，和要求的目标油量，程序则通过计算输出一种实现的步骤（不需要找到所有可能的方法）。如果没有可能实现，则输出：“不可能”。
例如，用户输入：
12,8,5
12,0,0,6
用户输入的前三个数是容器容量（由大到小），接下来三个数是三个容器开始时的油量配置，最后一个数是要求得到的油量（放在哪个容器里得到都可以）
则程序可以输出（答案不唯一，只验证操作可行性）：
12,0,0
4,8,0
4,3,5
9,3,0
9,0,3
1,8,3
1,6,5
每一行表示一个操作过程中的油量状态。
注意：
请仔细调试！您的程序只有能运行出正确结果的时候才有机会得分！
请把所有类写在同一个文件中，调试好后，存入与【考生文件夹】下对应题号的“解答.txt”中即可。
相关的工程文件不要拷入。
请不要使用package语句。
源程序中只能出现JDK1.5中允许的语法或调用。不能使用1.6或更高版本。
虽说这是一道java的题目但是还是拿来做了练习，和“分酒”那题几乎是一样的，但这次是要求输出每一次倒酒的状态。
这就一点，我感觉我的做法还是有点麻烦，不知道有没有大牛有更简单的方法。
望赐教。
View Code 1 #include<iostream> 2 #include<queue> 3 using namespace std; 4 5 6 int full[3]; //容器容量 7 int end; //要求得到的容量 8 typedef struct 9 { 10 int num[3]; 11 int step; 12 }state; //目前状态 13 typedef struct //将所有状态都存储起来 14 { 15 state ss; 16 int father; 17 }Solve; 18 Solve solve[100000]; 19 int Count; //指向solve数组 20 int vis[20][20][20]; 21 int find_father(state temp2); 22 void print(state temp); 23 int bfs(state &temp , int i , int j) 24 { 25 if(i == j) return 0; 26 if(temp.num[i] == 0) return 0; //i中没有酒 27 if(temp.num[j] == full[j]) return 0; //j中已满 28 if(temp.num[i] + temp.num[j] <= full[j]) // 将i中全部倒入j中 29 { 30 temp.num[j] += temp.num[i]; 31 temp.num[i] = 0; 32 } 33 else //i没有全部倒完 34 { 35 temp.num[i] -= full[j] - temp.num[j]; 36 temp.num[j] = full[j]; 37 } 38 if(vis[temp.num[0]][temp.num[1]][temp.num[2]]) return 0; //此状态已访问 39 else vis[temp.num[0]][temp.num[1]][temp.num[2]] = 1; //此状态已标记 40 temp.step++; 41 return 1; 42 } 43 int main() 44 { 45 int flag , temp_father; 46 cin>>full[0]>>full[1]>>full[2]; 47 state start; 48 cin>>start.num[0]>>start.num[1]>>start.num[2]; 49 cin>>end; 50 start.step=0; 51 vis[start.num[0]][start.num[1]][start.num[2]] = 1; 52 queue<state>q; 53 q.push(start); 54 Count = 0; 55 solve[Count].ss.num[0] = start.num[0]; //将状态存储起来 56 solve[Count].ss.num[1] = start.num[1]; 57 solve[Count].ss.num[2] = start.num[2]; 58 solve[Count].father = -1; 59 Count++; 60 while(!q.empty()) 61 { 62 int i , j; 63 flag = 0; 64 state temp1; 65 temp1 = q.front(); 66 q.pop(); 67 if(temp1.num[0] == end || temp1.num[1] == end || temp1.num[2] == end) 68 { 69 flag = 1; 70 print(temp1); 71 break; 72 } 73 for(i = 0; i < 3; i++) 74 { 75 for(j = 0; j < 3; j++) 76 { 77 state temp2 = temp1; 78 temp_father = find_father(temp2); 79 if(bfs(temp2 , i , j)) 80 { 81 q.push(temp2); 82 solve[Count].ss.num[0] = temp2.num[0]; //将状态存储起来 83 solve[Count].ss.num[1] = temp2.num[1]; 84 solve[Count].ss.num[2] = temp2.num[2]; 85 solve[Count].father = temp_father; 86 Count++; 87 } 88 } 89 } 90 } 91 if(!flag) cout<<"不可能"<<endl; 92 return 0; 93 } 94 95 int find_father(state temp2) 96 { 97 int i; 98 for(i = 0; i < Count; i++) 99 { 100 if(solve[i].ss.num[0] == temp2.num[0]) 101 { 102 if(solve[i].ss.num[1] == temp2.num[1]) 103 { 104 if(solve[i].ss.num[2] == temp2.num[2]) 105 {return i;} 106 } 107 } 108 } 109 return 0; 110 } 111 void print(state temp) 112 { 113 int i; 114 int n; 115 state pri[1000]; 116 for(i = Count-1; i >=0; i--) //查找 最后一步倒酒所在的位置 117 { 118 if(solve[i].ss.num[0] == temp.num[0]) 119 { 120 if(solve[i].ss.num[1] == temp.num[1]) 121 { 122 if(solve[i].ss.num[2] == temp.num[2]) 123 {n = i; break;} 124 } 125 } 126 } 127 for(i = 0; i <= temp.step; i++) //将倒酒的步骤存入数组，以便逆序输出 128 { 129 pri[i].num[0] = solve[n].ss.num[0]; 130 pri[i].num[1] = solve[n].ss.num[1]; 131 pri[i].num[2] = solve[n].ss.num[2]; 132 n = solve[n].father; 133 } 134 for(i = temp.step; i >=0; i--) //逆序输出 135 { 136 cout<<pri[i].num[0]<<' '<<pri[i].num[1]<<' '<<pri[i].num[2]<<endl; 137 } 138 }
