引言初次學習遞歸時漢諾塔作為典型例題難倒了不少初學者。這是因為初學者們總是想細致地、一步一步地觀察出其移動步驟這顯然是難以做到的。因此我們可以先從宏觀上入手。漢諾塔http://ybt.ssoier.cn:8088/problem_show.php?pid1205漢諾塔介紹漢諾塔Tower of Hanoi是源于印度古老傳說的益智玩具由法國數(shù)學家愛德華·盧卡斯于1883年正式提出。它不僅是經(jīng)典的智力游戲更是計算機科學中講解遞歸算法最經(jīng)典的案例之一。傳說在世界中心貝拿勒斯的圣廟里一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界時在其中一根針上從下到上穿好了由大到小的64片金片。僧侶們按照以下法則日夜不停地移動這些金片一次只移動一片不管在哪根針上小片必須在大片上面。預言說當所有的金片都移到另一根針上時世界就將在一聲霹靂中消滅。漢諾塔問題可以抽象為有三根柱子通常標記為 A、B、C初始時 A 柱上從下到上按大小順序疊放著 n 個圓盤。目標是將所有圓盤移動到 C 柱上移動過程中必須遵守以下規(guī)則每次只能移動一個圓盤每次只能移動柱子最頂層的圓盤任何時刻大盤不得置于小盤之上。解決問題我們可以先從簡單的例子入手當 n1 時步驟如下圖只需要一步 A → B當 n2 時步驟如下圖需要 3 步 A → C A → B C → B當 n3 時我們可以將積木拆解成 n 與 n-1 當成只有兩塊積木時來做。先將 n-1 A → C類似于 n2將 B C 柱子互換完成再將 n A - B最后 n-1 C → B代碼實現(xiàn)#define _CRT_SECURE_NO_WARNINGS #include stdio.h void dfs(int n, char a, char c, char b)//將 n 從 a 借助 c 移動到 b { if (n 0) // 如果沒有積木則直接返回 return; dfs(n - 1, a, b, c); // 將 n-1 從 a 借助 b 移動到 c printf(%c-%d-%c\n, a, n, c); // 輸出 n 從 a 移動到 c 的過程 dfs(n - 1, c, a, b); // 再將 n-1 從 c 借助 a 移動到 b } int main() { int n 0; scanf(%d, n); dfs(n, a, c, b);// 將 n 從 a 借助 c 移動到 b return 0; }通過宏觀方式我們只需要了解函數(shù)原理不去探討每一步具體如何移動更加適合初學者來理解漢諾塔的原理。