妖怪和和尚过河问题(javascript实现)

junnplus 发布于2019-08-19 18:05 / 1003人阅读

摘要：问题描述有三个和尚和三个妖怪要利用唯一的一条小船过河，这条小船一次只能载两个人，同时，无论是在河的两岸还是在船上，只要妖怪的数量大于和尚的数量，妖怪们就会将和尚吃掉。现在需要选择一种过河的安排，保证和尚和妖怪都能过河且和尚不能被妖怪吃掉。

此为《算法的乐趣》读书笔记，我用javascript重新实现算法。

敝人拙见

此题作者实现得过于复杂，我将初始状态定义为：[3,3,0,0,true]，释义：依次表示，此岸和尚数量、此岸妖怪数量、彼岸和尚数量、彼岸妖怪数量、船在此岸否。有了以上定义，完全可以将这个题目看成与上一章桶等分水那个题目是一样的问题，两岸是两个“桶"，和尚和妖怪是"水"，"水"在两个”桶“中回来倒，最后全部倒到彼岸那个桶中。

问题描述

有三个和尚和三个妖怪要利用唯一的一条小船过河，这条小船一次只能载两个人，同时，无论是在河的两岸还是在船上，只要妖怪的数量大于和尚的数量，妖怪们就会将和尚吃掉。现在需要选择一种过河的安排，保证和尚和妖怪都能过河且和尚不能被妖怪吃掉。

变量定义

var states = [[3,3,0,0,true]];          //初值，顺序为：本地和尚、妖怪;对岸和尚、妖怪、船在此岸        
var IsLocal = true;                     //是否在此岸，是为真，在对岸为假

检测乘船安排是否可行（倒水方法合理？）

function CanTakeDumpAction(curr,local,from,to){
    //检测船上，和尚数量大于等于妖怪或者和尚为零且总数为1或2
    if((from >= to || from === 0 && to > 0) && (from + to <= 2) && (from + to > 0)){
        if(local){            //此岸与彼岸是不同的
            //船过岸后，两岸都要满足要么和尚为0,要么和尚数量大于等于妖怪
            if((curr[0] >= from && curr[1] >= to && (curr[0] - from == 0 || curr[0] - from >= curr[1] - to)) && (curr[2] + from == 0 || curr[2] + from >= curr[3] + to)){
                return true;
            }
        }else{
            if((curr[2] >= from && curr[3] >= to && (curr[2] - from == 0 || curr[2] - from >= curr[3] - to)) && (curr[0] + from == 0 || curr[0] + from >= curr[1] + to)){
                return true;
            }
        }
    }
    return false;
}

船到岸后（过河）操作（倒水）

function DumpWater(curr,local,from,to){
    var next = curr.slice();       
    if(local){        //此岸与彼岸有不同的操作
        next[0] -= from;
        next[1] -= to;
        next[2] += from;
        next[3] += to;
    }else{
        next[0] += from;
        next[1] += to;
        next[2] -= from;
        next[3] -= to;
    }
    next[4] = !local    //船到对岸
    return next;
}

检测状态是否出现过

这个函数是保证不会进入死循环。

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] && state[3] == states[i][3] && state[4] == states[i][4]){
            return true;
        }
    }
    return false;
}

状态搜索主函数

(function SearchState(states,local){
    var curr = states[states.length - 1];              //取初始状态
    if(curr[2] == 3 && curr[3] == 3){                  //找到解   
        var rs = ""
        states.forEach(function(al){
            rs += al.join(",") + " -> ";
        });
        console.log(rs.substr(0,rs.length - 4))
    }

    for(var i = 0; i < 3; i++){                         //i表示乘船的和尚数量，0~2
        for(var j = 0; j < 3; j++){                     //j表示乘船的妖怪数量，0~2
            if(CanTakeDumpAction(curr,local,i,j)){      //乘船安排合理
                var next = DumpWater(curr,local,i,j);   //过河
                if(!IsStateExist(next)){       
                    states.push(next);
                    SearchState(states,!local);
                    states.pop();
                }
            }
        }
    }
})(states,IsLocal);

四组结果

3,3,0,0,true -> 3,1,0,2,false -> 3,2,0,1,true -> 3,0,0,3,false -> 3,1,0,2,true -> 1,1,2,2,false -> 2,2,1,1,true -> 0,2,3,1,false -> 0,3,3,0,true -> 0,1,3,2,false -> 0,2,3,1,true -> 0,0,3,3,false
3,3,0,0,true -> 3,1,0,2,false -> 3,2,0,1,true -> 3,0,0,3,false -> 3,1,0,2,true -> 1,1,2,2,false -> 2,2,1,1,true -> 0,2,3,1,false -> 0,3,3,0,true -> 0,1,3,2,false -> 1,1,2,2,true -> 0,0,3,3,false
3,3,0,0,true -> 2,2,1,1,false -> 3,2,0,1,true -> 3,0,0,3,false -> 3,1,0,2,true -> 1,1,2,2,false -> 2,2,1,1,true -> 0,2,3,1,false -> 0,3,3,0,true -> 0,1,3,2,false -> 0,2,3,1,true -> 0,0,3,3,false
3,3,0,0,true -> 2,2,1,1,false -> 3,2,0,1,true -> 3,0,0,3,false -> 3,1,0,2,true -> 1,1,2,2,false -> 2,2,1,1,true -> 0,2,3,1,false -> 0,3,3,0,true -> 0,1,3,2,false -> 1,1,2,2,true -> 0,0,3,3,false

云服务器服务器托管妖怪 javascript问题和尚小和尚

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

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

一道有意思的编程思考题：【妖怪和和尚过河问题】

摘要：不断地穷举下一步的可能性，直到最终达成目标。表示船在左边表示船在右边打印答案妖怪过河数僧人过河数船上是否安全左岸是否安全右岸是否安全过河后的数据过河后的数据简单地看下深度优先搜索的函数，每次根据船所在的位置，枚举下个状态值。无意中看到这么一道题，觉得很有意思，题目如下：有三个和尚和三个妖怪要利用唯一的一条小船过河，这条小船一次只能载两个人，同时，无论是在河的两岸还是在船上，只要妖怪...

asce1885 2019-08-21 13:44 评论0 收藏0
做开发十年，我总结出了这些开发经验

摘要：本文由云社区发表在一线做了十年的开发，经历了网易百度腾讯研究院等几个地方，陆续做过游戏页游浏览器移动端翻译等。四既要有攻城之力，也要有熬战之气产品开发完成后，必然有。功能开发完成后，就要开始守城了。本文由云+社区发表在一线做了十年的开发，经历了网易、百度、腾讯研究院、MIG 等几个地方，陆续做过 3D 游戏、2D 页游、浏览器、移动端翻译 app 等。积累了一些感悟。必然有依然幼...

warmcheng 2019-08-16 14:10 评论0 收藏0
备战蓝桥杯——算法训练之过河马

摘要：而众所周知，马是要走日子格的。输出格式输出有一行，一个数表示走法数。那为了防止爆掉，我们每加完一条路的总步数之后就取一遍余。题目解法思路如上述，但是这里有一个我之前从来没有注意过的问题，导致我一直只有分。三题解四题目链接过河马 ...

xorpay 2021-11-15 11:38 评论0 收藏0
一名非典型二流学生的自述 | 我是如何从菜鸟进化到辣鸡的

摘要：嗨，我是积极废人，我是摩卡先生，现在是一所二流学院的大二学生。我不反感他，因为他说的没错，我就是个菜鸟啊。一个彻头彻尾的菜鸟。保持对成功的渴望，继续当自己的傻瓜我是摩卡先生，谢谢你的阅读，期待我后续的文章吧 showImg(https://segmentfault.com/img/bVbbjDc); 人们总是一边不相信鸡汤，一边又奢望鸡汤在关键时刻能够拉自己一把。事先说明，这是一碗有...

molyzzx 2019-08-15 17:59 评论0 收藏0
一名非典型二流学生的自述 | 我是如何从菜鸟进化到辣鸡的

摘要：嗨，我是积极废人，我是摩卡先生，现在是一所二流学院的大二学生。我不反感他，因为他说的没错，我就是个菜鸟啊。一个彻头彻尾的菜鸟。保持对成功的渴望，继续当自己的傻瓜我是摩卡先生，谢谢你的阅读，期待我后续的文章吧 showImg(https://segmentfault.com/img/bVbbjDc); 人们总是一边不相信鸡汤，一边又奢望鸡汤在关键时刻能够拉自己一把。事先说明，这是一碗有...

khs1994 2019-07-30 16:39 评论0 收藏0