资讯专栏INFORMATION COLUMN

三水桶等分8升水(javascript实现)

Xufc / 3571人阅读

摘要:问题描述有三个容器分别是三升五升和八升的水桶,其中容积为八升的水桶装满了水,其余两桶为空。水桶没有刻度,除这三个桶外不能使用其它容器,将升水等分为两份升的水。

此为《算法的乐趣》读书笔记,我用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);
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

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/79162.html

相关文章

  • 三个水等分8升水的问题

    摘要:三个水桶都没有刻度,现在需要将大水桶中的升水等分成两份,每份都是升水,附加条件是只能这三个水桶,不能借助其他辅助容器。假设将每个状态下三个水桶中的水的体积作为。 智力题目 有三个容积分别为3升、5升、8升的水桶,其中容积为8升的水桶中装满了水,容积为3升和容积为5升的水桶都是空的。三个水桶都没有刻度,现在需要将大水桶中的8升水等分成两份,每份都是4升水,附加条件是只能这三个水桶,不能借...

    ShevaKuilin 评论0 收藏0
  • JavaScript 数据结构与算法之美 - 排序、计数排序、基数排序

    摘要:之所以把计数排序桶排序基数排序放在一起比较,是因为它们的平均时间复杂度都为。动画计数排序思想找出待排序的数组中最大和最小的元素。桶排序计数排序能派上用场吗手机号码有位,范围太大,显然不适合用这两种排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言 算法为王。 想学好前端,先练好内功,只有内功深厚者...

    Awbeci 评论0 收藏0
  • JavaScript 数据结构与算法之美 - 十大经典排序算法汇总

    摘要:笔者写的数据结构与算法之美系列用的语言是,旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面,而,排序之后,在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法为王。想学好前端,先练好内功,内功不行,就...

    zsy888 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<