Java SE如何求解汉诺塔问题

1.问题描述

汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。

并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。 问应该如何操作？ 

2.画图分析

一个圆盘的情况：移动前

移动后

1个盘子：A直接移动到C

二个圆盘的情况：移动前

移动后

2个圆盘：A->B  A->C B->C

三个圆盘的情况：移动前

移动后

三个圆盘：A->C A->B C->B A->C B->A  B->C A-C

3.问题讲解  

当有3个盘子的时候，你就会发现一个问题，你肯定是要先将上面的两个盘子移动到B柱，再把最底下的一个盘子移动到C柱，最后再把B柱的盘子移动到C柱。4个盘子的话也是一样，要先将上面的3个盘子移动到B柱，在把最底下的一个盘子移动到C柱，最后再把B柱的盘子移动到C柱。这样我们就有了一个思路，不管多少个盘子，都要先将n - 1个盘子移动到B柱，最底下的一个盘子移动到C柱，最后再把B柱的盘子移动到C柱。

我们先来看一下规律：

1个盘子：A->C       1次

2个盘子：A->B  A->C B->C      3次

3个盘子：A->C A->B C->B A->C B->A  B->C A-C   7次

这样你就能看出移动的次数其实就是2^n - 1(n是盘子的数量）

4.代码实现

ublic class TestDemo {
    //首先要写个模拟鼠标移动过程的函数，我们要打印出移动的全部过程
    //这个move函数做到的就是从1位置移动到2位置，有可能是A->B,A->C,C-B......等各种可能
    public static void move(char pos1,char pos2){//所以说这里只需要传对应的位置就可以了
        System.out.print(pos1+"->"+pos2+" ");//pos1移动到pos2
    }
 
    /**
     *
     * @param n  n代表你盘子的个数
     * @param pos1 盘子所在的位置
     * @param pos2 盘子的中转位置
     * @param pos3 盘子的结束位置
     */
    public static void hanio(int n,char pos1,char pos2,char pos3){
        if(n == 1){
            move(pos1,pos3);//如果只有一个盘子那就从A柱挪到C柱上
        }else{
            hanio(n-1,pos1,pos3,pos2);//这里是把n-1个盘子从A柱借助C柱移动到B柱
            move(pos1,pos3);//底下剩下的最后一个盘子从A柱移动到C柱
            hanio(n-1,pos2,pos1,pos3);//这里是把n-1个盘子从B柱借助A柱移动到C柱
 
        }
 
 
    }
    public static void main(String[] args) {
        hanio(1,'A','B','C');//一开始我们的汉诺塔要规定一下，我们第一次给它传过去的位置
        System.out.println();
        hanio(2,'A','B','C');
        System.out.println();
        hanio(3,'A','B','C');
        System.out.println();
    }
 
 
 
 
}

打印结果：