转载

三水桶等分8升水（javascript实现）

此为《算法的乐趣》读书笔记，我用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(i === 0 && j === 0)                 continue;             if(CanTakeDumpAction(curr,i,j)){                 var next = DumpWater(curr,i,j);                 if(!IsStateExist(next)){        //找到新状态                     states.push(next);                     SearchState(states);                     states.pop();                 }             }         }     } })(states);

16组正确解

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

原文 http://hao.jser.com/archive/10075/

正文到此结束