妖怪和和尚過(guò)河問(wèn)題(javascript實(shí)現(xiàn))

junnplus 發(fā)布于2019-08-19 18:05 / 1169人閱讀

摘要：?jiǎn)栴}描述有三個(gè)和尚和三個(gè)妖怪要利用唯一的一條小船過(guò)河，這條小船一次只能載兩個(gè)人，同時(shí)，無(wú)論是在河的兩岸還是在船上，只要妖怪的數(shù)量大于和尚的數(shù)量，妖怪們就會(huì)將和尚吃掉?，F(xiàn)在需要選擇一種過(guò)河的安排，保證和尚和妖怪都能過(guò)河且和尚不能被妖怪吃掉。

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

敝人拙見(jiàn)

此題作者實(shí)現(xiàn)得過(guò)于復(fù)雜，我將初始狀態(tài)定義為：[3,3,0,0,true]，釋義：依次表示，此岸和尚數(shù)量、此岸妖怪?jǐn)?shù)量、彼岸和尚數(shù)量、彼岸妖怪?jǐn)?shù)量、船在此岸否。有了以上定義，完全可以將這個(gè)題目看成與上一章桶等分水那個(gè)題目是一樣的問(wèn)題，兩岸是兩個(gè)“桶"，和尚和妖怪是"水"，"水"在兩個(gè)”桶“中回來(lái)倒，最后全部倒到彼岸那個(gè)桶中。

問(wèn)題描述

有三個(gè)和尚和三個(gè)妖怪要利用唯一的一條小船過(guò)河，這條小船一次只能載兩個(gè)人，同時(shí)，無(wú)論是在河的兩岸還是在船上，只要妖怪的數(shù)量大于和尚的數(shù)量，妖怪們就會(huì)將和尚吃掉。現(xiàn)在需要選擇一種過(guò)河的安排，保證和尚和妖怪都能過(guò)河且和尚不能被妖怪吃掉。

變量定義

var states = [[3,3,0,0,true]];          //初值，順序?yàn)椋罕镜睾蜕?、妖?對(duì)岸和尚、妖怪、船在此岸        
var IsLocal = true;                     //是否在此岸，是為真，在對(duì)岸為假

檢測(cè)乘船安排是否可行（倒水方法合理？）

function CanTakeDumpAction(curr,local,from,to){
    //檢測(cè)船上，和尚數(shù)量大于等于妖怪或者和尚為零且總數(shù)為1或2
    if((from >= to || from === 0 && to > 0) && (from + to <= 2) && (from + to > 0)){
        if(local){            //此岸與彼岸是不同的
            //船過(guò)岸后，兩岸都要滿足要么和尚為0,要么和尚數(shù)量大于等于妖怪
            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;
}

船到岸后（過(guò)河）操作（倒水）

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    //船到對(duì)岸
    return next;
}

檢測(cè)狀態(tài)是否出現(xiàn)過(guò)

這個(gè)函數(shù)是保證不會(huì)進(jìn)入死循環(huán)。

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;
}

狀態(tài)搜索主函數(shù)

(function SearchState(states,local){
    var curr = states[states.length - 1];              //取初始狀態(tài)
    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表示乘船的和尚數(shù)量，0~2
        for(var j = 0; j < 3; j++){                     //j表示乘船的妖怪?jǐn)?shù)量，0~2
            if(CanTakeDumpAction(curr,local,i,j)){      //乘船安排合理
                var next = DumpWater(curr,local,i,j);   //過(guò)河
                if(!IsStateExist(next)){       
                    states.push(next);
                    SearchState(states,!local);
                    states.pop();
                }
            }
        }
    }
})(states,IsLocal);

四組結(jié)果

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

GPU云服務(wù)器云服務(wù)器妖怪 javascript問(wèn)題和尚小和尚

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/79180.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

junnplus

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

mxnet

閱讀 2332·2023-04-26 01:50
云主機(jī)怎么安裝-云主機(jī)怎么配置環(huán)境？

閱讀 765·2021-09-22 15:20
圖片加載相關(guān)技術(shù)

閱讀 2667·2019-08-30 15:53
【移動(dòng)適配】一個(gè)像素的border怎么實(shí)現(xiàn)

閱讀 1659·2019-08-30 12:49
Blockstack-2 ：Blockstack ID注冊(cè)

閱讀 1764·2019-08-26 14:05
阿里云上到底能運(yùn)行SAP哪些產(chǎn)品?

閱讀 2782·2019-08-26 11:42
學(xué)習(xí) underscore 源碼整體架構(gòu)，打造屬于自己的函數(shù)式編程類庫(kù)

閱讀 2396·2019-08-26 10:40
JS之閉包及其作用

閱讀 2667·2019-08-26 10:38

亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

妖怪和和尚過(guò)河問(wèn)題(javascript實(shí)現(xiàn))

相關(guān)文章

**一道有意思的編程思考題：【妖怪和和尚過(guò)河問(wèn)題】**

做開(kāi)發(fā)十年，我總結(jié)出了這些開(kāi)發(fā)經(jīng)驗(yàn)

**備戰(zhàn)藍(lán)橋杯——算法訓(xùn)練之過(guò)河馬**

一名非典型二流學(xué)生的自述 | 我是如何從菜鳥(niǎo)進(jìn)化到辣雞的

一名非典型二流學(xué)生的自述 | 我是如何從菜鳥(niǎo)進(jìn)化到辣雞的

發(fā)表評(píng)論

0條評(píng)論

junnplus

男|高級(jí)講師

TA的文章

mxnet

云主機(jī)怎么安裝-云主機(jī)怎么配置環(huán)境？

圖片加載相關(guān)技術(shù)

【移動(dòng)適配】一個(gè)像素的border怎么實(shí)現(xiàn)

Blockstack-2 ：Blockstack ID注冊(cè)

阿里云上到底能運(yùn)行SAP哪些產(chǎn)品?

學(xué)習(xí) underscore 源碼整體架構(gòu)，打造屬于自己的函數(shù)式編程類庫(kù)

JS之閉包及其作用

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

妖怪和和尚過(guò)河問(wèn)題(javascript實(shí)現(xiàn))

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！