萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 遞迴解決河內塔(漢諾塔)問題完整範例

問題簡介

河內塔是經典遞迴問題:將 N 個圓盤從柱子 A 移至柱子 C,借用柱子 B,規則:一次只能移一個圓盤,大盤不能放在小盤上方。

遞迴解法核心邏輯

<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);           // 將 n-1 個盤從 aux 移到 dst
  }
};

// 測試:10 個圓盤
han(10, "src", "aux", "dst");
</script>

執行流程圖解(以 3 盤為例)

han(3, A, B, C)
├─ han(2, A, C, B)
│  ├─ han(1, A, B, C) → move disc 1 from A to C
│  ├─ move disc 2 from A to B
│  └─ han(1, C, A, B) → move disc 1 from C to B
├─ move disc 3 from A to C
└─ han(2, B, A, C)
   ├─ han(1, B, C, A) → move disc 1 from B to A
   ├─ move disc 2 from B to C
   └─ han(1, A, B, C) → move disc 1 from A to C

複雜度分析

  • 移動次數:2^n - 1(n 為圓盤數)
  • 時間複雜度:O(2^n)
  • 空間複雜度:O(n)(遞迴呼叫堆疊深度)

此範例展示遞迴解決分治問題的典型模式:將大問題分解為相同結構的子問題,配合終止條件(disc === 0)完成求解。

copyright © 萬盛學電腦網 all rights reserved