汉诺塔问题

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

问题1

试用java语言描述整个移动过程。

需要用到递归的思想：

理论上，用java代码可以表示为：

public static void hanoi(String a,String b, String c, int n){
  // 移动完毕
  if(n==0) {
    return;
  }  
  // 为了能够把a上的第n个盘子移动至c，必须先把前n-1个盘子从a移动至b
  hanoi(a, c, b, n-1);
  System.out.println("圆盘["+n+"]从["+a+"]移动至["+c+"]");
  // 还需要将n-1个盘子从b移动至c
  hanoi(b, a, c, n-1);  
}

实际上，由于栈内存的大小限制，无法满足n=64时递归的情况。

问题2

请问总共需要移动多少次？

递归解法：

分析：如果移动n个盘子的次数为hanoi(n)次，可以分解为： 移动最后一个盘子+移动前n-1个盘子+移动后n-1个盘子，如果n=1时只需要移动一次。

即:

hanoi(n)=2*hanoi(n-1)+1
hanoi(1)=1

写成java代码就是(注意必须使用BigInteger，会超过int甚至long的范围)：

public static BigInteger hanoi(BigInteger n) {
    if (BigInteger.ONE.equals(n)) { // n==1
        return BigInteger.ONE;
    }
    // 2*hanoi(n-1)+1
    return new BigInteger("2").multiply(hanoi(n.subtract(BigInteger.ONE))).add(BigInteger.ONE); 
}

执行：

System.out.println(hanoi(new BigInteger("64")));

输出：

18446744073709551615

非递归解法：

同样可以发现解实际为 2^64-1，同样因为范围的原因选用BigInteger：

System.out.println(new BigInteger("2").pow(64).subtract(BigInteger.ONE));

输出：

18446744073709551615