汉诺塔

汉诺塔相信大家都听过，而且也知道用递归来求解。
今天面试，突然问到这个，并要求写出代码，至少是伪代码。
一下子比较晕。仔细想了下，差点把汉诺塔搞错了。一下来自百科
“汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。”




现在，我们考虑如何使用递归。递归有个特点，那就是，上层把问题交给下层，直到最后可以很快求解时，再递归返回上层，得到答案。这个问题，可以这么理解：
问： n 个圆盘如何移动？
答： 如果知道n-1个圆盘移动顺序，那么我就知道如何移动n个圆盘了

问： n-1个圆盘如何移动？
答： 如果知道 n-2 个圆盘移动顺序，那么我就知道如何移动n个圆盘了。

...
...
...

问： 2个圆盘如何移动？
答： 这个容易，A->C, A->B, B->C


这时，3个圆盘可以移动了，然后4个圆盘也知道移动了，5个……

看代码吧。

public class Hanno {
	/**
	 * 
	 * @param A 起始柱子
	 * @param B 临时柱子
	 * @param C 目的柱子
	 * @param n 未放好的圆盘数量。如果未放好的最大的一个圆盘放到C中最下面，则表示这个圆盘已经放好。
	 */
	public void move(char A , char B , char C ,int n){
		/**
		 * 小于2个圆盘，无意义。
		 */
		if(n < 2){
			return;
		}
		/**
		 * 当圆盘数是2时，我们已经可以轻松的计算出移动顺序了。
		 */
		if(n == 2){			
			System.out.println("move from "+A +" to " + B + " ");
			System.out.println("move from "+A +" to " + C + " ");
			System.out.println("move from "+B +" to " + C + " ");
			return;
		}
		/**
		 * 这里调整了一下，假设现在未放好的圆盘都在柱子A上。我们把目前圆盘看成两个，最下面的一个和
		 * 上面的所以看成一个。如何移动最上面的圆盘（被看做一个圆盘）我们不关心（通过递归求解，当最上面的圆盘数为2
		 * 时，我们可以递归）。我们的目的是把最上面的一个放到B，然后就可以把最下面一个放到C
		 * 这样就完成了最下面一个的放置。根据函数，我们可以如下表示。
		 */
		move(A,C,B,n-1);
		/**
		 * 把上面的一摞（或者一个，看做一个）圆盘移动到B以后，我们把A中最后一个圆盘移动到C
		 * 所以直接移动。
		 */
		System.out.println("move from " + A + " to " + C );
		
		/**
		 * 这时的情况是A柱子空了，B柱子变成n-1个圆盘，C柱子上是放好的圆盘了。
		 * 那么，我们继续移动，把B柱子上的圆盘，移动到C柱子，这里其实等于一开始时，把A和B换一下。
		 * 对于C柱子，最大的一个圆盘在下面了，所以无论什么圆盘，都可以放上面。可以看成是空的。
		 * 这样问题转换成求解n-1个圆盘。知道递归到不动点。 
		 */
		move(B,A,C,n-1);
		
	}
	public static void main(String args[]){
		Hanno hanno = new Hanno();
		hanno.move('A', 'B', 'C', 3);
	}

这里一个关键是，把柱子上的圆盘看成是两个，有些步骤，不用考虑如何移动，只需要递归到可以求解。

我一开始，也想到了，但是我还是想错了，不能把圆盘分成上面一个单独作为一个，下面的所有看做一个，这样是不行的。只有把下面的看成一个，然后上面的所有看成一个。

并且，移动的时候，按照简单的两个移动的思维，就组成了函数的逻辑。