DIV CSS 佈局教程網

一道有趣的程式思考題:妖怪與和尚過河問題
編輯:JavaScript基礎知識     

無意間看到這麼一道題,覺得很有意思:

有三個和尚與三個妖怪要利用唯一的一條小船過河,小船一次最多載兩人。無論在河的哪一岸或船上,只要妖怪數量大於和尚數量,和尚就會被吃掉。請設計一種過河安排,讓所有和尚與妖怪都能安全過河。

一、最直覺的想法:暴力枚舉

第一反應通常是暴力搜尋——不斷枚舉下一步的所有可能,直到抵達目標狀態。由於過程中會出現重複的狀態,必須做狀態哈希來避免無限繞圈。

二、狀態怎麼表示

最樸素的作法是用多維陣列。用四維陣列分别表示左岸僧人 a、左岸妖怪 b、右岸僧人 c、右岸妖怪 d,以 [a][b][c][d] = true 表示該狀態走過了。其實二維就夠——左岸確定後右岸自然可推得,只是多一步計算。

但這裡有個漏洞:船在左岸或在右岸是兩種不同情況,所以還得多一維,用 [a][b][c][d][1] 表示船在左、[a][b][c][d][0] 表示船在右。邏輯上完全可行,問題是 JavaScript 操作多維陣列實在麻煩,於是繼續思考能否壓縮。

三、把狀態壓成一個數字

觀察初始狀態 [3, 3, 0, 0, 1]:搜尋過程中每個數字都不會超過 3,取值範圍只有 0 到 3——這不就是四進位嗎?於是可以把狀態壓縮成一個四進位數。但四進位算起來還是不順手,而每一位四進位恰好可拆成兩位二進位,於是 3300 這類狀態就能轉成二進位來處理,位運算瞬間變得方便許多。

考量到船的位置比較特殊,最後決定前四維用一個二進位數表示,船的位置另外用一維處理,整體以二維陣列做哈希。

四、陣列與數字互轉

先把 [3, 3, 0, 0] 轉成二進位為 11110000 的數字:

// 陣列轉數字
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;
}

反過來的逆運算:

// 數字轉陣列
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('------------------');

    // 回溯
    hash[num][pos] = false;
    ans.pop();
    return;
  }

  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 {
    // 右岸到左岸
    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);
      }
    }
  }

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

每次依船的位置枚舉下一個狀態,並用一個小函數判斷某岸的僧人與妖怪數量組合是否安全:

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

這道題有意思的地方在於:它同時考了狀態設計、位運算壓縮與搜尋回溯。把狀態壓成一個整數之後,哈希的實作與效能都清爽很多,這是在其他語言中比較少有機會練習到的技巧。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved