C语言递归思想实现汉诺塔详解

什么是汉诺塔问题？

汉诺塔问题是一个古老的数学谜题，也是递归思想的典型应用。问题由以下三个规则定义：

1. 有三根杆子，第一根杆子上有若干个直径大小不一的圆盘，第二根杆子上一个圆盘没有，第三根杆子上一个圆盘没有。

2. 每次只能移动一个盘子。

3. 大盘子不能放在小盘子上面。

目标是从初始状态移动所有圆盘到最后一根杆子上。我们可以用 A、B、C 三个字符来表示三个杆子。

思路

假设有 $n$ 个圆盘需要从 A 移动到 C，我们可以把问题拆分为以下三个子问题：

1. 先将 $n-1$ 个圆盘从 A 移动到 B
2. 将最后一个圆盘从 A 移动到 C
3. 最后将 $n-1$ 个圆盘从 B 移动到 C

以上思路可以递归地在子问题上进行处理，直到 $n=1$，此时直接把圆盘从 A 移动到 C 即可。

代码实现

以下是代码实现：

#include <stdio.h>

// 将 top 个圆盘从 begin 移动到 end，借助 auxiliary
void Hanoi(int top, char begin, char end, char auxiliary)
{
    if(top == 1)
    {
        // 当只剩下 1 个圆盘时，直接移动到 end
        printf("Move %d from %c to %c\n", top, begin, end);
        return;
    }

    // 将 top-1 个圆盘从 begin 移动到 auxiliary，借助 end
    Hanoi(top-1, begin, auxiliary, end);

    // 将第 top 个圆盘从 begin 移动到 end
    printf("Move %d from %c to %c\n", top, begin, end);

    // 将 top-1 个圆盘从 auxiliary 移动到 end，借助 begin
    Hanoi(top-1, auxiliary, end, begin);
}

int main()
{
    int n = 3; // 三个圆盘
    Hanoi(n, 'A', 'C', 'B');
    return 0;
}

以上代码中，函数 Hanoi() 接受三个参数：需移动的圆盘数量 top、起始杆子 begin、目标杆子 end 和中间杆子 auxiliary。

函数中使用了递归思想，将问题分解为子问题处理。当 top=1 时，直接将圆盘从起始杆子移动到目标杆子。如果 top 不为 1，递归调用函数，将 $top-1$ 个圆盘从起始杆子 A 移动到中间杆子 B，再将第 top 个圆盘从 A 移动到 C，最后将 $top-1$ 个圆盘从 B 移动到 C，借助 A。

示例说明

接下来，我们来看一下 n=3 的两个示例：

示例一

将 ${1, 2, 3}$ 三个圆盘从 A 移到 C，借助 B：

1. 将 ${1, 2}$ 两个圆盘从 A 移到 B，借助 C：

   1. 将 ${1}$ 圆盘从 A 移动到 C
   2. 将 ${2}$ 圆盘从 A 移动到 B
   3. 将 ${1}$ 圆盘从 C 移动到 B

2. 将最后一个圆盘 ${3}$ 从 A 移到 C

3. 将 ${1, 2}$ 两个圆盘从 B 移到 C，借助 A：

   1. 将 ${1}$ 圆盘从 B 移动到 A
   2. 将 ${2}$ 圆盘从 B 移动到 C
   3. 将 ${1}$ 圆盘从 A 移动到 C

示例二

将 ${1, 2, 3}$ 三个圆盘从 A 移到 B，借助 C：

1. 将 ${1, 2}$ 两个圆盘从 A 移到 C，借助 B：

   1. 将 ${1}$ 圆盘从 A 移动到 B
   2. 将 ${2}$ 圆盘从 A 移动到 C
   3. 将 ${1}$ 圆盘从 B 移动到 C

2. 将最后一个圆盘 ${3}$ 从 A 移到 B

3. 将 ${1, 2}$ 两个圆盘从 C 移到 B，借助 A：

   1. 将 ${1}$ 圆盘从 C 移动到 A
   2. 将 ${2}$ 圆盘从 C 移动到 B
   3. 将 ${1}$ 圆盘从 A 移动到 B

以上示例说明了在递归过程中，如何按照预定规则移动圆盘，直到所有圆盘从起始位置移动至目标位置。