汉诺塔是一个移动盘子的游戏：有3根柱子，把一叠从小到大叠放的盘子从一根柱子移到另一根柱子，每次只能移动一个盘子，且大盘子不能放在小盘子上面。

一、递归基

        只有一个盘子时，直接移动即可，所有递归都必须有明确的终止条件，否则陷入无限循环。

if (n == 1) {
    printf("将盘子 1 从 %c 移到 %c\n", a, c);
    return;
}

二、递归分解

        算法的核心是三个步骤的递归调用序列。

        第一步han(n - 1, a, c, b)将n-1个盘子从a柱借助c柱移到b柱，这个调用完成了前置清理工作，为最大盘子的移动创造了条件。注意参数位置的变化：原本的目标柱c在这里变成了辅助柱，而原本的辅助柱b变成了目标柱。

        第二步printf("将盘子 %d 从 %c 移到 %c\n", n, a, c)输出移动最大盘子的操作，这是唯一不需要递归的直接操作，因为经过第一步后，a柱上只剩下编号为n的最大盘子。

        第三步han(n - 1, b, a, c)将b柱上的n-1个盘子借助a柱移到c柱，完成整个转移过程。

        这三步形成了一个完整的递归分解，每一步都在解决规模更小的相同问题。

// 步骤1：将 n-1 个盘子从 a 借助 c 移到 b
han(n - 1, a, c, b);

// 步骤2：将第 n 个盘子从 a 移到 c
printf("将盘子 %d 从 %c 移到 %c\n", n, a, c);

// 步骤3：将 n-1 个盘子从 b 借助 a 移到 c
han(n - 1, b, a, c);

三、移动的最少步数

        在main函数中，long long total_moves = pow(2, n) - 1这行代码计算了移动n个盘子所需的最少步数。选择long long类型是为了容纳可能巨大的结果——当n=64时，结果约为1.84×10¹⁹，远远超过普通int类型的表示范围。使用数学库的pow函数计算2的n次方，再减去1，直接得到了汉诺塔问题的数学解。这个计算与递归过程本身无关，而是基于该问题的数学性质提前告知用户总的操作步数，为用户提供预期。

// 计算总步数：2^n - 1
long long total_moves = pow(2, n) - 1;
printf("\n总共需要 %lld 步。\n", total_moves);

四、完整代码

#include <stdio.h>
#include <math.h>

// 递归函数：将 n 个盘子从 a 借助 b 移到 c
void han(int n, char a, char b, char c) {
    if (n == 1) {
        printf("将盘子 1 从 %c 移到 %c\n", a, c);
        return;
    }
    
    // 步骤1：将 n-1 个盘子从 a 借助 c 移到 b
    han(n - 1, a, c, b);
    
    // 步骤2：将第 n 个盘子从 a 移到 c
    printf("将盘子 %d 从 %c 移到 %c\n", n, a, c);
    
    // 步骤3：将 n-1 个盘子从 b 借助 a 移到 c
    han(n - 1, b, a, c);
}

int main() {
    int n;
    printf("请输入汉诺塔盘子数量: ");
    scanf("%d", &n);
    
    // 计算总步数：2^n - 1
    long long total_moves = pow(2, n) - 1;
    printf("\n总共需要 %lld 步。\n", total_moves);

    return 0;
}