043. 使用递归解决汉诺塔问题
汉诺塔问题是一个经典的递归问题。它的规则如下：有三根柱子（通常标记为 A、B 和 C），在 A 柱上有若干个大小不一的盘子，盘子的大小从上到下依次增大。目标是将所有盘子从 A 柱移动到 C 柱，过程中可以借助 B 柱作为辅助，但必须满足以下规则：
- 每次只能移动一个盘子。
- 每次移动时，只能将一个盘子从顶部移动到另一根柱子的顶部。
- 任何时候，在三根柱子的任何一根上，较大的盘子不能放在较小的盘子上面。
解题思路
汉诺塔问题可以通过递归方法解决。递归的核心思想是将问题分解为更小的子问题：
- 将 n−1 个盘子从 A 柱移动到 B 柱（借助 C 柱）。
- 将第 n 个盘子（最大的盘子）从 A 柱直接移动到 C 柱。
- 再将 n−1 个盘子从 B 柱移动到 C 柱（借助 A 柱）。
C语言实现
以下是使用递归解决汉诺塔问题的完整代码：
#include <stdio.h>
// 定义递归函数解决汉诺塔问题
void hanoi(int n, char fromPeg, char toPeg, char auxPeg) {
if (n == 1) { // 递归终止条件：只有一个盘子时直接移动
printf("将盘子 1 从 %c 移动到 %c\n", fromPeg, toPeg);
return;
}
// 将 n-1 个盘子从 fromPeg 移动到 auxPeg，借助 toPeg
hanoi(n - 1, fromPeg, auxPeg, toPeg);
// 将第 n 个盘子从 fromPeg 移动到 toPeg
printf("将盘子 %d 从 %c 移动到 %c\n", n, fromPeg, toPeg);
// 将 n-1 个盘子从 auxPeg 移动到 toPeg，借助 fromPeg
hanoi(n - 1, auxPeg, toPeg, fromPeg);
}
int main() {
int n;
printf("请输入盘子的数量：");
scanf("%d", &n);
if (n <= 0) {
printf("盘子数量必须是正整数！\n");
return 1;
}
// 调用汉诺塔递归函数
hanoi(n, 'A', 'C', 'B');
return 0;
}
代码说明
-
递归函数
hanoi： -
参数：
-
n：当前需要移动的盘子数量。 -
fromPeg：起始柱子。 -
toPeg：目标柱子。 -
auxPeg：辅助柱子。 -
递归终止条件：当
n == 1时，直接将盘子从起始柱子移动到目标柱子。 -
递归步骤：
-
先将
n-1个盘子从fromPeg移动到auxPeg。 -
将第
n个盘子从fromPeg移动到toPeg。 -
再将
n-1个盘子从auxPeg移动到toPeg。 -
主函数
main： -
提示用户输入盘子的数量。
-
调用
hanoi函数，初始时从 A 柱移动到 C 柱，借助 B 柱。
示例运行
输入：
请输入盘子的数量：3
输出：
将盘子 1 从 A 移动到 C
将盘子 2 从 A 移动到 B
将盘子 1 从 C 移动到 B
将盘子 3 从 A 移动到 C
将盘子 1 从 B 移动到 A
将盘子 2 从 B 移动到 C
将盘子 1 从 A 移动到 C
注意事项
-
递归深度：
-
汉诺塔问题的递归深度为 2n−1，对于较大的
n，递归调用次数会非常多，可能会导致栈溢出。在实际应用中，通常限制n的大小（如 n≤20）。 -
输出格式：
-
输出的移动步骤清晰地展示了每一步的操作，有助于理解汉诺塔问题的解决过程。
视频讲解
BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)