C 语言第60题：汉诺塔：打印移动步骤（递归）

题目

求解经典汉诺塔问题（Hanoi Tower）：有三个柱子 A、B、C，将 n 个盘子从 A 柱借助 B 柱移动到 C 柱，每次只能移动一个盘子且大盘不能压在小盘上方，使用递归打印出全部移动步骤。

输入格式：一行输入一个正整数 n，表示盘子总数。

输出格式：按步输出形如 A->C 的移动路径，每步占一行。

数据范围与约定：1 ≤ n ≤ 10。

思路与算法

1. 经典分治递推三步法
要将 n 个盘从 from 移到 to（借助 aux）：
① 递归将上面 n-1 个盘从 from 移到 aux；
② 直接将底部最大的第 n 号盘从 from 移到 to；
③ 递归将 n-1 个盘从 aux 移到 to。

2. 移动步数规律
n 个盘子的总移动步数精确为 2ⁿ - 1 步。当 n=1 时为递归基，直接输出移动并返回。

完整程序

#include <stdio.h>

// 经典汉诺塔递归：
// from: 起始柱, to: 目标柱, aux: 辅助柱
static void hanoi(int n, char from, char to, char aux)
{
    // 递归出口：只有 1 个圆盘时，直接一步移到目标柱
    if (n == 1) {
        printf("%c->%c\n", from, to);
        return;
    }
    // 第一步：借助 to 柱，将上面 n-1 个盘子从 from 移到 aux
    hanoi(n - 1, from, aux, to);
    // 第二步：将最底下最大的盘子从 from 移到 to
    printf("%c->%c\n", from, to);
    // 第三步：借助 from 柱，将 aux 上的 n-1 个盘子移到 to
    hanoi(n - 1, aux, to, from);
}

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1 || n < 1 || n > 10) {
        return 1;
    }
    hanoi(n, 'A', 'C', 'B');
    return 0;
}

运行示例

输入：

2

输出：

A->B
A->C
B->C