用java方法实现汉诺塔问题

描述

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

将一个塔上的所有圆盘移动到另一个塔上，每次仅能移动一个圆盘，且每次移动需要保持大的圆盘在下、小的圆盘在上

汉诺塔问题

分析

圆盘移动的次数与圆盘的个数满足一种函数关系，在这里设定：
f(n) = m;
其中n为圆盘的个数，m为完成整个过程所用的次数。
当只有一个圆盘的时候，只需要移动一次即可：
f(1) = 1;
当有两个圆盘的时候，移动方法比较简单，需要移动三次：
f(2) = 3;
当有三个圆盘时，所涉及的移动过程较为复杂：

以上，f(3) = 7;

根据以上流程，可以总结出汉诺塔的移动规律：

stage01阶段，移动了f(n-1)次圆盘；
stage02阶段，移动了1次圆盘；
stage03阶段，移动了f(n-1)次圆盘；

即f(n) = 2f(n-1) + 1;

实现代码

    // 汉诺塔
    public int hannoi(int n){
        if(n == 1){
            return 1;
        }else if(n == 2){
            return 3;
        }else{
            return 2*hannoi(n-1)+1;
        }
    }