妖怪和和尚過河問題(javascript實現(xiàn))

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

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

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

敝人拙見

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

問題描述

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

變量定義

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

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

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

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

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

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

這個函數(shù)是保證不會進入死循環(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表示乘船的妖怪數(shù)量，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);

四組結(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云服務器妖怪 javascript問題和尚小和尚

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

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/79180.html

一道有意思的編程思考題：【妖怪和和尚過河問題】

摘要：不斷地窮舉下一步的可能性，直到最終達成目標。表示船在左邊表示船在右邊打印答案妖怪過河數(shù)僧人過河數(shù)船上是否安全左岸是否安全右岸是否安全過河后的數(shù)據(jù)過河后的數(shù)據(jù)簡單地看下深度優(yōu)先搜索的函數(shù)，每次根據(jù)船所在的位置，枚舉下個狀態(tài)值。無意中看到這么一道題，覺得很有意思，題目如下：有三個和尚和三個妖怪要利用唯一的一條小船過河，這條小船一次只能載兩個人，同時，無論是在河的兩岸還是在船上，只要妖怪...

asce1885 2019-08-21 13:44 評論0 收藏0
做開發(fā)十年，我總結(jié)出了這些開發(fā)經(jīng)驗

摘要：本文由云社區(qū)發(fā)表在一線做了十年的開發(fā)，經(jīng)歷了網(wǎng)易百度騰訊研究院等幾個地方，陸續(xù)做過游戲頁游瀏覽器移動端翻譯等。四既要有攻城之力，也要有熬戰(zhàn)之氣產(chǎn)品開發(fā)完成后，必然有。功能開發(fā)完成后，就要開始守城了。本文由云+社區(qū)發(fā)表在一線做了十年的開發(fā)，經(jīng)歷了網(wǎng)易、百度、騰訊研究院、MIG 等幾個地方，陸續(xù)做過 3D 游戲、2D 頁游、瀏覽器、移動端翻譯 app 等。積累了一些感悟。必然有依然幼...

warmcheng 2019-08-16 14:10 評論0 收藏0
備戰(zhàn)藍橋杯——算法訓練之過河馬

摘要：而眾所周知，馬是要走日子格的。輸出格式輸出有一行，一個數(shù)表示走法數(shù)。那為了防止爆掉，我們每加完一條路的總步數(shù)之后就取一遍余。題目解法思路如上述，但是這里有一個我之前從來沒有注意過的問題，導致我一直只有分。三題解四題目鏈接過河馬 ...

xorpay 2021-11-15 11:38 評論0 收藏0
一名非典型二流學生的自述 | 我是如何從菜鳥進化到辣雞的

摘要：嗨，我是積極廢人，我是摩卡先生，現(xiàn)在是一所二流學院的大二學生。我不反感他，因為他說的沒錯，我就是個菜鳥啊。一個徹頭徹尾的菜鳥。保持對成功的渴望，繼續(xù)當自己的傻瓜我是摩卡先生，謝謝你的閱讀，期待我后續(xù)的文章吧 showImg(https://segmentfault.com/img/bVbbjDc); 人們總是一邊不相信雞湯，一邊又奢望雞湯在關鍵時刻能夠拉自己一把。事先說明，這是一碗有...

molyzzx 2019-08-15 17:59 評論0 收藏0
一名非典型二流學生的自述 | 我是如何從菜鳥進化到辣雞的

摘要：嗨，我是積極廢人，我是摩卡先生，現(xiàn)在是一所二流學院的大二學生。我不反感他，因為他說的沒錯，我就是個菜鳥啊。一個徹頭徹尾的菜鳥。保持對成功的渴望，繼續(xù)當自己的傻瓜我是摩卡先生，謝謝你的閱讀，期待我后續(xù)的文章吧 showImg(https://segmentfault.com/img/bVbbjDc); 人們總是一邊不相信雞湯，一邊又奢望雞湯在關鍵時刻能夠拉自己一把。事先說明，這是一碗有...

khs1994 2019-07-30 16:39 評論0 收藏0