Java第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 左右，否则输出行数爆炸。

完整程序

public class Main {
    static void hanoi(int n, char fr, char to, char aux) {
        if (n == 1) {
            System.out.println(fr + "->" + to);
            return;
        }
        hanoi(n - 1, fr, aux, to);
        System.out.println(fr + "->" + to);
        hanoi(n - 1, aux, to, fr);
    }
    public static void main(String[] args) {
        hanoi(2, 'A', 'C', 'B');
    }
}

运行示例

输出：

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