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

此為《算法的樂趣》讀書筆記，我用javascript重新實(shí)現(xiàn)算法。

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

以三水桶盛水量為一個(gè)矢量狀態(tài)，倒水可以推動狀態(tài)的改變，這樣會形成一個(gè)狀態(tài)樹，我們采用深度優(yōu)先搜索方式進(jìn)行窮舉。
書中使用用了C++標(biāo)準(zhǔn)庫的雙端隊(duì)列，還用了結(jié)構(gòu)體，并將桶狀態(tài)封裝成了類，比較難看懂，我發(fā)現(xiàn)用javascript進(jìn)行合理的設(shè)計(jì)，代碼簡單易懂^_^。

桶的最大容量及狀態(tài)變化隊(duì)列

var FullBacket = [8,5,3]            //桶的最大容量
var states = [[8,0,0]];             //狀態(tài)隊(duì)列，js的數(shù)組已經(jīng)已經(jīng)有隊(duì)列和堆棧的支持

限制條件為：桶的序號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;
}

倒水量的計(jì)算要注意兩個(gè)方面，一是目標(biāo)桶的剩余容積；二是源桶的剩余水量，兩者取小。

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

這個(gè)函數(shù)是保證不會進(jìn)入死循環(huán)，注意：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;
}

邊界條件有兩個(gè)，一為找到了正確解，一為所有狀態(tài)都檢測完，并未找到正確解。

(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)){        //找到新狀態(tài)
                    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