摘要：問題描述有三個容器分別是三升五升和八升的水桶，其中容積為八升的水桶裝滿了水，其余兩桶為空。水桶沒有刻度，除這三個桶外不能使用其它容器，將升水等分為兩份升的水。

此為《算法的樂趣》讀書筆記，我用javascript重新實現算法。

有三個容器分別是三升、五升和八升的水桶，其中容積為八升的水桶裝滿了水，其余兩桶為空。水桶沒有刻度，除這三個桶外不能使用其它容器，將8升水等分為兩份4升的水。

以三水桶盛水量為一個矢量狀態，倒水可以推動狀態的改變，這樣會形成一個狀態樹，我們采用深度優先搜索方式進行窮舉。
書中使用用了C++標準庫的雙端隊列，還用了結構體，并將桶狀態封裝成了類，比較難看懂，我發現用javascript進行合理的設計，代碼簡單易懂^_^。

桶的最大容量及狀態變化隊列

var FullBacket = [8,5,3]            //桶的最大容量
var states = [[8,0,0]];             //狀態隊列，js的數組已經已經有隊列和堆棧的支持

限制條件為：桶的序號0~2；倒出水的桶不能為空；倒入水的桶不能是滿的。

function CanTakeDumpAction(curr,from,to){
    if(from >= 0 && from < 3 && to >= 0 && to < 3){
        if(from != to && curr[from] > 0 && curr[to] < FullBacket[to]){
            return true;
        }
    }
    return false;
}

倒水量的計算要注意兩個方面，一是目標桶的剩余容積；二是源桶的剩余水量，兩者取小。

function DumpWater(curr,from,to){
    var next = curr.slice();        //js對象為引用傳值，這里要復制一份
    var dump_water = FullBacket[to] - curr[to] > curr[from] ? curr[from] : FullBacket[to] - curr[to]            //倒水量的計算
    next[from] -= dump_water;
    next[to] += dump_water;
    return next;
}

這個函數是保證不會進入死循環，注意：foreach中途不能退出，此處不能用它。

function IsStateExist(state){
    for(var i = 0; i < states.length; i++){
        if(state[0] == states[i][0] && state[1] == states[i][1] && state[2] == states[i][2]){
            return true;
        }
    }
    return false;
}

邊界條件有兩個，一為找到了正確解，一為所有狀態都檢測完，并未找到正確解。

(function SearchState(states){
    var curr = states[states.length - 1];
    if(curr[0] == 4 && curr[1] == 4){            //找到正確解
        var rs = ""
        states.forEach(function(al){
            rs += al.join(",") + " -> ";
        });
        console.log(rs.substr(0,rs.length - 4))
    }

    for(var j = 0; j < 3; j++){                //所有的倒水方案即為桶編號的全排列
        for(var i = 0; i < 3; i++){
            if(CanTakeDumpAction(curr,i,j)){
                var next = DumpWater(curr,i,j);
                if(!IsStateExist(next)){        //找到新狀態
                    states.push(next);
                    SearchState(states);
                    states.pop();
                }
            }
        }
    }
})(states);

8,0,0 -> 3,5,0 -> 0,5,3 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0
8,0,0 -> 3,5,0 -> 3,2,3 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0
8,0,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 0,5,3 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0
8,0,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0
8,0,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0
8,0,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 0,5,3 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0
8,0,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0
8,0,0 -> 3,5,0 -> 3,2,3 -> 0,5,3 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0
8,0,0 -> 5,0,3 -> 0,5,3 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0
8,0,0 -> 5,0,3 -> 5,3,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0
8,0,0 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 0,5,3 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0
8,0,0 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0
8,0,0 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 0,5,3 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0
8,0,0 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 7,0,1 -> 7,1,0 -> 4,1,3 -> 4,4,0
8,0,0 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0
8,0,0 -> 5,0,3 -> 5,3,0 -> 2,3,3 -> 2,5,1 -> 0,5,3 -> 3,5,0 -> 3,2,3 -> 6,2,0 -> 6,0,2 -> 1,5,2 -> 1,4,3 -> 4,4,0