目錄

一：起源

二：問題描述

三：規律

三：解決方案

遞歸算法

四：代碼實現

復雜度分析

---

一：起源

漢諾塔（Tower of Hanoi）問題起源于一個印度的古老傳說。在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的 64 片金片，這就是所謂的漢諾塔。

不論白天黑夜，總有一個僧侶按照下面的法則移動這些金片：

I. 一次只移動一片，不管在哪根針上

II. 小片必須在大片上面

僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

二：問題描述

有三根柱子（通常標記為 A、B、C），在其中一根柱子（如 A 柱）上從下到上按大小順序摞著?n?個圓盤，要求把這?n?個圓盤從起始柱移動到目標柱，每次只能移動一個圓盤，并且在移動過程中任何時候都不能出現大盤在小盤上面的情況。輔助柱用于在移動過程中臨時存放圓盤。

三：規律

• 移動次數規律：對于?n?個圓盤的漢諾塔問題，最少需要移動的次數為?\(2^n - 1\)?次。

例如:

當?(n = 1)?時，只需移動 1 次；

當?(n = 2)?時，需要移動?(2^2 - 1 = 3)?次；

當?(n = 3)?時，需要移動?(2^3 - 1 = 7)?次，

以此類推。

• 遞歸規律：可以將?n?個圓盤的漢諾塔問題分解為三個子問題：
  1. 把上面的?\(n - 1\)?個圓盤從起始柱借助目標柱移動到輔助柱。
  2. 把最大的第?n?個圓盤從起始柱移動到目標柱。
  3. 把?\(n - 1\)?個圓盤從輔助柱借助起始柱移動到目標柱。

三：解決方案

遞歸算法

遞歸是解決漢諾塔問題最常用的方法，其核心思想是將大問題分解為小問題。

說到這，小伙伴們是否會自然而然會想到分治算法呢？（C語言）算法復習總結2——分治算法-CSDN博客

四：代碼實現

#include <stdio.h>// 遞歸函數用于解決漢諾塔問題
void hanoi(int n, char source, char target, char auxiliary) {if (n == 1) {// 當只有一個圓盤時，直接從源柱移動到目標柱printf("Move disk 1 from %c to %c\n", source, target);return;}// 把 n-1 個圓盤從源柱借助目標柱移動到輔助柱hanoi(n - 1, source, auxiliary, target);// 把第 n 個圓盤從源柱移動到目標柱printf("Move disk %d from %c to %c\n", n, source, target);// 把 n-1 個圓盤從輔助柱借助源柱移動到目標柱hanoi(n - 1, auxiliary, target, source);
}int main() {int n = 3;  // 圓盤的數量// 調用 hanoi 函數開始移動圓盤hanoi(n, 'A', 'C', 'B');return 0;
}

復雜度分析

• 時間復雜度：由于每次遞歸調用都會將問題規模減小 1，且每次調用會產生兩個新的遞歸調用，所以時間復雜度為?(O(2^n))。
• 空間復雜度：遞歸調用棧的最大深度為?n，因此空間復雜度為?(O(n))。