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

题目

汉诺塔：打印移动步骤（递归）

思路

void hanoi(int n,char from,char aux,char to)：若 n==1 打印移动；否则先 n-1 到 aux，最大到 to，再 n-1 aux→to；柱名用字符区分。

解题分析

汉诺塔递归结构固定：要把 n 盘从 A 移到 C，先把上面 n-1 盘经 B 挪到 C，再移最大盘，再把 n-1 盘从 C 经 B 回到 A。每层只多两次递归和一个打印，盘数为 n 时步数是 2^n-1。

• 三柱名字用参数传递，不要写死全局，方便打印 A->C 这类步骤。
• n 不要超过 10 左右，否则输出行数爆炸。

完整程序

#include <stdio.h>

static void hanoi(int n, char from, char to, char aux)
{
    if (n == 1) {
        printf("%c->%c\n", from, to);
        return;
    }
    hanoi(n - 1, from, aux, to);
    printf("%c->%c\n", from, 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