资讯专栏INFORMATION COLUMN

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

asce1885 / 987人阅读

摘要:不断地穷举下一步的可能性,直到最终达成目标。表示船在左边表示船在右边打印答案妖怪过河数僧人过河数船上是否安全左岸是否安全右岸是否安全过河后的数据过河后的数据简单地看下深度优先搜索的函数,每次根据船所在的位置,枚举下个状态值。

无意中看到这么一道题,觉得很有意思,题目如下:

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

看完题目,首先想到的是暴力搜索。不断地穷举下一步的可能性,直到最终达成目标。因为搜索过程中可能会有重复的状态,所以需要对状态进行哈希。

如何表示当前的状态?首先想到的是用多维数组进行哈希。我们可以用一个四维数组(其实完全可以用二维,左边僧人妖怪的数量确定后,相应地就能计算右边了,需要多一步运算),假设左岸僧人和妖怪数量分别是 a 和 b,右岸僧人妖怪数量分别是 c 和 d,那么我们可以用 [a][b][c][d]=true 表示这种情况,也就是该状态已经被搜索过了。这样做还有个漏洞,船在左右两边是不同的情况,所以还需要一个维度来表示船的位置,那么可以这样,增加一维,用 [a][b][c][d][1]=true 表示船在左边的情况,用 [a][b][c][d][0]=true 表示船在右边的情况。这样来表示状态是完全可以的,但是众所周知 JavaScript 下表示多维数组非常的麻烦,所以进一步思考能不能将状态压缩。

继续看,最开始时的状态,如上可以表示为 [3][3][0][0][1],之后的搜索过程中,状态中的数字不可能大于 3,也就是数字的范围在 0~3 中,这不是赤裸裸的四进制数吗?于是我们可以将该状态压缩到一个四进制数 330001 中,但是四进制毕竟操作起来不大方便,能不能转为二进制?答案很明显,一个四进制数可以拆成两个二进制,这样就好办了,将四进制的 33001 可以转成二进制 1111000001,二进制的各种运算就方便多了!

考虑到最后一个维度的特殊情况,最终我决定将前四个维度用一个二进制来处理,第五个维度(船的位置)多带带处理,用一个二维数组进行状态哈希。

很显然,我们需要能将数组和二进制数互换的函数。

简单写了两个互换函数,将数组转为数字的。比如将 [3, 3, 0, 0] 转为二进制大小为 11110000 的数字:

// array to number
function aton(a) {
  var sum = 0;
  for (var i = a.length; i--; ) {
    var index = 3 - i
      , item = a[i];

    (item & 1) && (sum |= (1 << (index << 1)));
    (item & 2) && (sum |= (1 << ((index << 1) | 1))); 
  }

  return sum;
}

将数字转为数组的,为以上函数的逆运算:

// number to array
function ntoa(n) {
  var a = [];

  for (var i = 0; i < 4; i++) {
    var num = 0
      , index = 3 - i;

    num |= n & (1 << (index << 1)) ? 1 : 0;
    num |= n & ((1 << ((index << 1) | 1))) ? 2 : 0;
    a.push(num);
  }

  return a;
}

接下去就非常简单了,进行深度优先搜索,每次搜索枚举下一个可能的状态,对该状态进行哈希,并把该状态存入答案数组中,枚举完进行回溯。

// pos == 1 表示船在左边
// pos == 0 表示船在右边
function dfs(num, pos) {

  if (hash[num][pos])
    return;

  hash[num][pos] = true;

  var a = ntoa(num);

  var l_sNum = a[0];
  var l_yNum = a[1];
  var r_sNum = a[2];
  var r_yNum = a[3];

  pos ? a.push("left") : a.push("right");

  ans.push(a);  

  if (num === 15) { // [0, 0, 3, 3]
    // 打印答案
    ans.concat().forEach(function(item) {
      console.log(item.toString() + "->");
    });

    console.log("------------------");

    // backtrace
    hash[num][pos] = false;
    ans.pop();

    return;
  }

  // left to right
  if (pos) {
    for (var i = 0; i <= l_yNum; i++) // 妖怪过河数
      for (var j = 0; j <= l_sNum; j++) {  // 僧人过河数

        if (i + j === 0)
          continue;

        // 船上是否安全
        if (!checkIfSafe(j, i))
          continue;

        // 左岸是否安全
        if (!checkIfSafe(l_sNum - j, l_yNum - i))
          continue;

        // 右岸是否安全
        if (!checkIfSafe(r_sNum + j, r_yNum + i))
          continue;

        if (i + j > 2)
          break;

        // 过河后的数据
        var b = [l_sNum - j, l_yNum - i, r_sNum + j, r_yNum + i];
        dfs(aton(b), 0);
      }
  } else {  // right to left
    for (var i = 0; i <= r_yNum; i++)
      for (var j = 0; j <= r_sNum; j++) { 

        if (i + j === 0)
          continue;

        if (!checkIfSafe(j, i))
          continue;

        if (!checkIfSafe(r_sNum - j, r_yNum - i))
          continue;

        if (!checkIfSafe(l_sNum + j, l_yNum + i))
          continue;

        if (i + j > 2)
          break;

        // 过河后的数据
        var b = [l_sNum + j, l_yNum + i, r_sNum - j, r_yNum - i];
        dfs(aton(b), 1);
      }
  }

  // backtrace
  hash[num][pos] = false;
  ans.pop();
}

简单地看下深度优先搜索的函数,每次根据船所在的位置,枚举下个状态值。这里我写了个 checkIfSafe 函数来判断当前数量的僧人和妖怪在一起,会不会有危险。函数非常简单:

function checkIfSafe(sNum, yNum) {
  return sNum === 0 || sNum >= yNum;
}

最后的最后,解法有四种,大概是这个样子:

3,3,0,0,left->
2,2,1,1,right->
3,2,0,1,left->
3,0,0,3,right->
3,1,0,2,left->
1,1,2,2,right->
2,2,1,1,left->
0,2,3,1,right->
0,3,3,0,left->
0,1,3,2,right->
1,1,2,2,left->
0,0,3,3,right->
------------------
3,3,0,0,left->
2,2,1,1,right->
3,2,0,1,left->
3,0,0,3,right->
3,1,0,2,left->
1,1,2,2,right->
2,2,1,1,left->
0,2,3,1,right->
0,3,3,0,left->
0,1,3,2,right->
0,2,3,1,left->
0,0,3,3,right->
------------------
3,3,0,0,left->
3,1,0,2,right->
3,2,0,1,left->
3,0,0,3,right->
3,1,0,2,left->
1,1,2,2,right->
2,2,1,1,left->
0,2,3,1,right->
0,3,3,0,left->
0,1,3,2,right->
1,1,2,2,left->
0,0,3,3,right->
------------------
3,3,0,0,left->
3,1,0,2,right->
3,2,0,1,left->
3,0,0,3,right->
3,1,0,2,left->
1,1,2,2,right->
2,2,1,1,left->
0,2,3,1,right->
0,3,3,0,left->
0,1,3,2,right->
0,2,3,1,left->
0,0,3,3,right->
------------------

完整代码点 这里。

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

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

相关文章

  • 妖怪过河问题(javascript实现)

    摘要:问题描述有三个和尚和三个妖怪要利用唯一的一条小船过河,这条小船一次只能载两个人,同时,无论是在河的两岸还是在船上,只要妖怪的数量大于和尚的数量,妖怪们就会将和尚吃掉。现在需要选择一种过河的安排,保证和尚和妖怪都能过河且和尚不能被妖怪吃掉。 此为《算法的乐趣》读书笔记,我用javascript重新实现算法。 敝人拙见 此题作者实现得过于复杂,我将初始状态定义为:[3,3,0,0,true...

    junnplus 评论0 收藏0
  • 一名非典型二流学生自述 | 我是如何从菜鸟进化到辣鸡

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

    molyzzx 评论0 收藏0
  • 一名非典型二流学生自述 | 我是如何从菜鸟进化到辣鸡

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

    khs1994 评论0 收藏0
  • 一道面试题引发思考

    摘要:下面我们来使用面向对象类图这里就不再画了首先面试题中所提到的我们都可以看成类,比如停车场是一个类吧,它里面的车位是一个类吧,摄像头,屏幕。。。 以下是某场的一道面试题(大概): 1、一个停车场,车辆入场时,摄像头记录下车辆信息2、屏幕上显示所接收的车辆的信息情况(车牌号)以及各层车位的车位余量3、停车场一共四层车位,其中的三层都为普通车位,还有一层为特殊车位(体现在停车计费价格上面的不...

    Apollo 评论0 收藏0

发表评论

0条评论

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