JAVA汉诺塔递归

目标：将A上的圆盘移动到目标塔C上。

思路：

①首先将A上的n-1移动到B上，由C作为辅助；（剩下一个最大的盘子在A上）

②将A上的盘子移动到目标塔C上；（此时最大的盘子到达目标位置）

③将B上n-1个盘子依次移动到C上，由A作为辅助；（这个过程和①②一样只不过源塔是B目标依然是C，由此可以发现汉诺塔问题是一个典型的递归问题）

?例：n = 3时移动

A->C? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 首先将A上的n-1移动到B上，由C作为辅助

A->B

C->A

A->C? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 最大的盘子到目标塔C

B->A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 此时最大的盘子到达C塔，只需要将B上n-1个盘

B->C? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 子依次挪动到C上即可，A最为辅助

A->C

实现代码：

public class Homework {
    public static void main(String[] args) {
        char A = 'A',B = 'B',C = 'C';
        hanoiTower(3,A,B,C);
    }
    public static void hanoiTower(int nDisks,char A,char B,char C) {
        if (nDisks == 1) {
            //  A -> C
            move(nDisks,A,C);
            return;
        }
        // nDisks > 1时
        // 1.先将n - 1个盘子从A -> B ,C作为辅助
        hanoiTower(nDisks - 1,A,C,B);
        // 2.此时最大的盘子在A上，C为空，n - 1都在B上
        move(nDisks,A,C);
        // 3.只需将n - 1个盘子再从B -> C,A作为辅助
        hanoiTower(nDisks - 1,B,A,C);
    }
    // 将编号为n的盘子，从souce -> dist
    public static void move(int nDisks, char sourceTower, char distTower) {
        System.out.println("编号为"+nDisks+"的盘子从"+sourceTower+"->"+distTower);
    }
}