Java第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 时为递归基，直接输出移动并返回。

完整程序

import java.util.Scanner;

public class Main {
    // 经典汉诺塔递归算法
    public static void hanoi(int n, char from, char aux, char to) {
        if (n == 1) {
            System.out.println(from + "->" + to);
            return;
        }
        // 1. 将前 n-1 个盘子从 from 借助 to 移动到 aux
        hanoi(n - 1, from, to, aux);
        // 2. 将第 n 个盘子从 from 移动到 to
        System.out.println(from + "->" + to);
        // 3. 将 n-1 个盘子从 aux 借助 from 移动到 to
        hanoi(n - 1, aux, from, to);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        hanoi(n, 'A', 'B', 'C');
    }
}

运行示例

输入：

2

输出：

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