hanoi塔问题

汉诺塔问题是一个很经典的一个递归算法问题。

说在古代印度的贝拿勒斯圣庙里，安放了一块黄铜板，板上插了三根宝石柱(不妨设A、B、C柱)，在A宝石柱上，自上而下按由小到大的顺序串有64个金盘。要求将A柱子上的64个金盘按照下面的规则移到C柱上。

规则：

①一次只能移一个盘子；

②盘子只能在三个柱子上存放；

③任何时候大盘不能放在小盘上面。

任务：输入正整数n(A柱上的盘子数)，输出移动到C柱上的移动过程。

解答

这题的答案相信大家都知道是要移动2n−1$2^n-1$次 那么这是怎么算出来的呢？

算法分析

我们用 A 、B、C 来代表三个柱子上的移动。

1.当n =1 时  我们直接    A->B
2.当n =2 时 
        A->B
        A->C
        B->C
3.当n=3时
        A->C
        A->B
        C->B
        A->C
        B->A
        B->C
        A->C

分析了前3个我们就可以找出一定的规律了。

我们可以吧递归的过程看成栈。先进后出的思想理解上面的图

当我们有n个圆盘时
递归程序如下：

①首先把他的n-1个圆盘 由第一个柱子移动到第二个柱子。以第三跟柱子为中转轴
②输出第n个盘（即最大的那个盘），把第n个盘放到第三柱子中
③把第n-1个盘由第二个柱子移动到第三个柱子中去。以第一个为中转轴

这就是递归的思路
java代码如下

public static void main(String[] args) {
        int n = sc.nextInt();
        hanoi(n,'A','B','C');//'A','B','C'代表3个柱子
    }
    private static void hanoi(int n, char c, char d, char e) {
        if(n==1)
        {
            System.out.println(c+"->"+e);
            return;
        }
        hanoi(n-1,c,e,d);//递归第一步 将前n-1个由第一个柱子移动到第二根柱子
        System.out.println(c+"->"+e);//第二步 将最大的圆盘移动到第三个柱子上去
        hanoi(n-1,d,c,e);//第三步  将前n-1个由第二根柱子移动到第3根柱子；
    }