問題：有一個充滿水的8品脫的水壺和兩個空水壺（容積分別是5品脫和3品脫）。通過將水壺完全倒滿水和將水壺的水完全倒空這兩種方式，在其中的一個水壺中得到4品脫的水。

解法：可以把每次三個水壺中水的量組成一個狀態，比如初始狀態為008，對應第一個水壺0品脫水，第二個水壺0品脫水，第三個水壺8品脫水。對題目的狀態空間圖進行廣度優先遍歷。當表示狀態的數字中出現4時，即求出答案。

1、為了打印出倒水的過程，需要聲明一個前置狀態保存當前狀態由哪個狀態轉換而來，然后就可以回溯到初始狀態，打印出倒水過程。相當于樹中的父結點。

2、可以聲明一個map表，保存已有的狀態，對已有的狀態，就不再向下繼續遍歷，這樣可以節省求解時間。

3、因為是廣度優先遍歷，所以第一次解得的答案所需的倒水的次數最少，解為最優解。

#include <iostream> #include <vector> #include <map> #define MaxFirst 3 #define MaxSecond 5 #define MaxThird 8 using namespace std;class State { public:int second;int num[3];State* preState;static map<int,int> mapping;public:State(int first,int second,int third){num[0]=first;num[1]=second;num[2]=third; }void init(){ mapping[0]=MaxFirst;mapping[1]=MaxSecond;mapping[2]=MaxThird;}bool canPour(int from,int to)//判斷是否可以從from水壺中倒水到to水壺中{if(num[from]==0){return false;}if(num[to]==mapping[to]){return false;}else {return true;}}void pour(int from,int to)//倒水過程{if(num[from]+num[to]>mapping[to]){num[from]=num[from]-(mapping[to]-num[to]);num[to]=mapping[to];}else{num[to]=num[to]+num[from];num[from]=0;}}}; map<int,int> State::mapping;int main() {map<int,int> states;State *start=new State(0,0,8);start->init();State *state=start;State *endState=new State(8,8,8);//只有獲得解endState才會改變，賦值全為8為了方便判斷是否獲得最終解vector<State> action;//保存所有狀態對象action.push_back(*start);//把初始狀態先加入隊列中int n=0;do{for(int i=0;i<3;i++)//雙層循環為從i水壺中倒水入j水壺中{for(int j=0;j<3;j++){if(i!=j){if(state->canPour(i,j)){state->pour(i,j);if(states[state->num[0]*100+state->num[1]*10+state->num[2]]==0)//如果該狀態不在hash表中，即為第一次出現該狀態{states[state->num[0]*100+state->num[1]*10+state->num[2]]++;(state->preState)=new State(action[n]);action.push_back(*state);if(state->num[0]==4||state->num[1]==4||state->num[2]==4)//獲得解{endState=state;i=4;break; }}}}*state=action[n];} }n++;}while(endState->num[0]==8&&endState->num[1]==8&& n<action.size());cout<<endState->num[0]<<" "<<endState->num[1]<<" "<<endState->num[2]<<endl;state=endState;do{state=state->preState;cout<<state->num[0]<<" "<<state->num[1]<<" "<<state->num[2]<<endl; }while(state->num[2]!=8);return 0; }

運行結果如圖，從下往上即為倒水的過程

如果需要倒出水壺含7品脫的情況，把

if(state->num[0]==4||state->num[1]==4||state->num[2]==4)中的4改成7，運行出結果如下：

總結

以上是生活随笔為你收集整理的算法谜题——三个水壶问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。