引言初次学习递归时汉诺塔作为典型例题难倒了不少初学者。这是因为初学者们总是想细致地、一步一步地观察出其移动步骤这显然是难以做到的。因此我们可以先从宏观上入手。汉诺塔http://ybt.ssoier.cn:8088/problem_show.php?pid1205汉诺塔介绍汉诺塔Tower of Hanoi是源于印度古老传说的益智玩具由法国数学家爱德华·卢卡斯于1883年正式提出。它不仅是经典的智力游戏更是计算机科学中讲解递归算法最经典的案例之一。传说在世界中心贝拿勒斯的圣庙里一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界时在其中一根针上从下到上穿好了由大到小的64片金片。僧侣们按照以下法则日夜不停地移动这些金片一次只移动一片不管在哪根针上小片必须在大片上面。预言说当所有的金片都移到另一根针上时世界就将在一声霹雳中消灭。汉诺塔问题可以抽象为有三根柱子通常标记为 A、B、C初始时 A 柱上从下到上按大小顺序叠放着 n 个圆盘。目标是将所有圆盘移动到 C 柱上移动过程中必须遵守以下规则每次只能移动一个圆盘每次只能移动柱子最顶层的圆盘任何时刻大盘不得置于小盘之上。解决问题我们可以先从简单的例子入手当 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代码实现#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; }通过宏观方式我们只需要了解函数原理不去探讨每一步具体如何移动更加适合初学者来理解汉诺塔的原理。
引言初次学习递归时汉诺塔作为典型例题难倒了不少初学者。这是因为初学者们总是想细致地、一步一步地观察出其移动步骤这显然是难以做到的。因此我们可以先从宏观上入手。汉诺塔http://ybt.ssoier.cn:8088/problem_show.php?pid1205汉诺塔介绍汉诺塔Tower of Hanoi是源于印度古老传说的益智玩具由法国数学家爱德华·卢卡斯于1883年正式提出。它不仅是经典的智力游戏更是计算机科学中讲解递归算法最经典的案例之一。传说在世界中心贝拿勒斯的圣庙里一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界时在其中一根针上从下到上穿好了由大到小的64片金片。僧侣们按照以下法则日夜不停地移动这些金片一次只移动一片不管在哪根针上小片必须在大片上面。预言说当所有的金片都移到另一根针上时世界就将在一声霹雳中消灭。汉诺塔问题可以抽象为有三根柱子通常标记为 A、B、C初始时 A 柱上从下到上按大小顺序叠放着 n 个圆盘。目标是将所有圆盘移动到 C 柱上移动过程中必须遵守以下规则每次只能移动一个圆盘每次只能移动柱子最顶层的圆盘任何时刻大盘不得置于小盘之上。解决问题我们可以先从简单的例子入手当 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代码实现#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; }通过宏观方式我们只需要了解函数原理不去探讨每一步具体如何移动更加适合初学者来理解汉诺塔的原理。
