用栈模拟汉诺塔问题
描述
在经典的汉诺塔问题中，有 3 个塔和 N 个可用来堆砌成塔的不同大小的盘子。要求盘子必须按照从小到大的顺序从上往下堆 （如：任意一个盘子，其必须堆在比它大的盘子上面）。同时，你必须满足以下限制条件：
- 每次只能移动一个盘子。
- 每个盘子从堆的顶部被移动后，只能置放于下一个堆中。
- 每个盘子只能放在比它大的盘子上面。
请写一段程序，实现将第一个堆的盘子移动到最后一个堆中。
样例
输入
3
输出
towers[0]: []
towers[1]: []
towers[2]: [2,1,0]
思路
因为自己以前没玩过，也没有纸和笔，另外一直在想知道每个步骤到底应该怎么做，应该从哪个移到哪个，所以到最后也没有想出一个可行的办法，最后迫不得已去搜了一下，结果才发现自己一直在钻牛角尖：
当只有一个盘子的时候，只需要从将A塔上的一个盘子移到C塔上。
当A塔上有两个盘子是，先将A塔上的1号盘子（编号从上到下）移动到B塔上，再将A塔上的2号盘子移动的C塔上，最后将B塔上的小盘子移动到C塔上。
当A塔上有3个盘子时，先将A塔上编号1至2的盘子（共2个）移动到B塔上（需借助C塔），然后将A塔上的3号最大的盘子移动到C塔，最后将B塔上的两个盘子借助A塔移动到C塔上。
当A塔上有n个盘子是，先将A塔上编号1至n-1的盘子（共n-1个）移动到B塔上（借助C塔），然后将A塔上最大的n号盘子移动到C塔上，最后将B塔上的n-1个盘子借助A塔移动到C塔上。
综上所述，除了只有一个盘子时不需要借助其他塔外，其余情况均一样（只是事件的复杂程度不一样）。
看过上面这段话，应该都能写出来代码了，不过为了照顾以后的自己，我还是把我自己的思路写下来吧：
三个塔：A，B，C。需要把盘子从A中移动到C中。
三个塔在每次移动时每个都有一个身份，分别为“源塔”（最开始盘子最多的塔）、“目标塔”（最后要把所有的盘子堆起来的塔）、“辅助塔”（与前面两个相对而言），每个塔与身份并不固定。
当只有一个盘子的时候：直接把A（源塔）中的盘子放到C（目标塔）中。结束！
当有两个盘子的时候【目标：把A（源塔）的两个盘子放到C（目标塔）中】：只用三步：
- 把A（源塔）中最小的盘子放到B（辅助塔）中
- 再将A（源塔）中的第二个盘子放到C（目标塔）中
- 最后再把B（辅助塔）中的最小的盘子放到C（目标塔）中
结束！
当有三个盘子的时候：用两个盘子时的思维，只用三步：
- 我们只用将A（源塔）中的前两个盘子放到B（辅助塔）中
- 再将A（源塔）中第三个盘子放到C（目标塔）中
- 最后再把B（辅助塔）中的两个盘子放到C（目标塔）中
结束——就怪了。因为还没考虑怎么将A的两个盘子放到B中，所以这个时候的目标就变了，变成了把A中的前两个盘子放到B中，这时候就很明显了，只要把塔的身份变换一下，就和两个盘子时的操作一模一样了。之后第二步也很简单。到了第三步，这个时候，A没有盘子，B有两个盘子，C有一个最大的盘子，这个时候的目标是把B中的两个盘子放到C中。是的，和两个盘子时的目标又是类似，所以替换一下身份再来一次，问题就真的解决了！
所以，当有N个盘子的时候，我们也只要三步：
- 把A的N-1个盘子放到B中
- 把A所剩下唯一的也是最大的盘子放到C中
- 把B中所有的盘子都放到C中
对于第一步，我们又可以转化为这三步：
此时的目标是把盘子从A放到B中
- 把A的N-2个盘子放到C中
- 把A最大的盘子（对于那N-1个盘子来说）放到B中
- 把C中所有的盘子都放到B中
对于这个的第一步，我们又可以……
由此，我们就可以写出代码：
代码
其中的moveTopTo和moveDisks方法为需要填补的内容
public class Tower {
private Stack<Integer> disks;
// create three towers (i from 0 to 2)
public Tower(int i) {
disks = new Stack<Integer>();
}
// Add a disk into this tower
public void add(int d) {
if (!disks.isEmpty() && disks.peek() <= d) {
System.out.println("Error placing disk " + d);
} else {
disks.push(d);
}
}
// @param t a tower
// Move the top disk of this tower to the top of t.
public void moveTopTo(Tower t) {
// Write your code here
if (t.disks.isEmpty() || (!disks.isEmpty() && t.disks.peek() >= disks.peek())) {
t.disks.push(disks.pop());
}
}
// @param n an integer
// @param destination a tower
// @param buffer a tower
// Move n Disks from this tower to destination by buffer tower
public void moveDisks(int n, Tower destination, Tower buffer) {
// Write your code here
if (n <= 0) {
return;
} else if (n == 1) {
moveTopTo(destination);
} else {
moveDisks(n - 1, buffer, destination); //将源塔前几个盘子都放到辅助塔中
moveDisks(1, destination, buffer); //此时源塔只剩下一个最大的盘子，将它放到目标塔中
buffer.moveDisks(n - 1, destination, this); //最后再将辅助塔的全部盘子（因为此时目标塔上已经有了一个盘子，故辅助塔的盘子数为n-1）都放到目标塔上
}
}
public Stack<Integer> getDisks() {
return disks;
}
}
/**
* Your Tower object will be instantiated and called as such:
* Tower[] towers = new Tower[3];
* for (int i = 0; i < 3; i++) towers[i] = new Tower(i);
* for (int i = n - 1; i >= 0; i--) towers[0].add(i);
* towers[0].moveDisks(n, towers[2], towers[1]);
* print towers[0], towers[1], towers[2]
*/
写在最后
这次可能写的思路有点啰嗦，不过自己感觉理了一遍以后思路更加清晰了，这个方法是用的递归，我也看了非递归的方法，不过感觉非递归的思想感觉比这个更难理解，所以就放弃了，先把思路复制到这里，等以后有空的话再试着理一理吧。
其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n – 1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；若n为奇数，按顺时针方向依次摆放 A C B。
⑴按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
⑵接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
⑶反复进行⑴⑵操作，最后就能按规定完成汉诺塔的移动。
所以结果非常简单，就是按照移动规则向一个方向移动金片：
如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
来自汉诺塔_百度百科