DIV CSS 佈局教程網

JavaScript 以遞迴求解河內塔問題
編輯:JavaScript綜合知識     

河內塔(Tower of Hanoi)是解釋遞迴最經典的例子。規則很簡單:有三根柱子,目標是把整疊圓盤從起始柱搬到目標柱,每次只能搬一個,而且小盤永遠不能疊在大盤上面。

它的優美之處在於:看似複雜的搬運,用遞迴只要三行就能寫完。

實作

<script language="javascript">
var han = function (disc, src, aux, dst) {
  if (disc > 0) {
    han(disc - 1, src, dst, aux);   // ① 把上面 n-1 個盤從 src 搬到 aux(暫存)
    document.writeln("move disc " + disc + " from " + src + " to " + dst + "<br/>");
    han(disc - 1, aux, src, dst);   // ② 把暫存在 aux 的 n-1 個盤搬到 dst
  }
};

han(10, "src", "aux", "dst");
</script>

遞迴思路拆解

要搬 n 個盤,直覺上沒人知道第一步該做什麼。但換個角度想:如果你能搬 n-1 個盤,那 n 個盤就解決了。

具體步驟只有三步:

  1. 把最上面 n-1 個盤,從起始柱搬到暫存柱(用目標柱當暫存)
  2. 把最大的第 n 號盤,從起始柱搬到目標柱
  3. 把暫存柱上的 n-1 個盤,搬到目標柱(用起始柱當暫存)

關鍵在於第 ① 步和第 ③ 步的參數順序:han(disc-1, src, dst, aux) 中,第三個參數(auxiliary)填的是 dst,第四個(目標)填的是 aux——也就是把目標與暫存對調。這個交換正是整個演算法能運作的核心。

終止條件為什麼是 disc > 0

當 disc 遞減到 0,代表「沒有盤要搬」,什麼都不做直接返回。這就是遞迴的 base case。少了它,函式會無限呼叫自己直到堆疊溢出。

幾個值得知道的性質

  • 搬動次數是 2ⁿ - 1。10 個盤需要 1023 次,20 個盤要 1048575 次,30 個盤超過十億次。這也是為什麼範例只跑到 10——再多的話瀏覽器會當住。
  • 第一次搬的一定是最小的盤。無論 n 是奇數或偶數,第一步都是把 1 號盤移到某根柱子,方向會依 n 的奇偶而異。
  • 解的步驟是唯一的最短解。在這些規則下,n 個盤的最少步驟就是 2ⁿ-1,沒有捷徑。

更完整的輸出

加上步驟計數與錯誤檢查,會更接近實用:

function hanoi(n, from, to, via) {
  var moves = [];

  (function move(disc, src, aux, dst) {
    if (disc <= 0) return;
    move(disc - 1, src, dst, aux);
    moves.push({ disc: disc, from: src, to: dst });
    move(disc - 1, aux, src, dst);
  })(n, from, to, via);

  return moves;
}

var steps = hanoi(3, 'A', 'C', 'B');
steps.forEach(function (s, i) {
  console.log((i + 1) + '. 將直徑 ' + s.disc + ' 的盤從 ' + s.from + ' 移到 ' + s.to);
});
console.log('共 ' + steps.length + ' 步');   // 共 7 步

這個版本把結果收集成陣列而非直接輸出,方便後續做動畫或其他處理——把每一步依序套用到視覺化的柱子上,就是一個河內塔動畫了。

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