【LintCode·容易】用栈模拟汉诺塔问题

用栈模拟汉诺塔问题

描述

在经典的汉诺塔问题中,有 3 个塔和 N 个可用来堆砌成塔的不同大小的盘子。要求盘子必须按照从小到大的顺序从上往下堆 (如:任意一个盘子,其必须堆在比它大的盘子上面)。同时,你必须满足以下限制条件:

  1. 每次只能移动一个盘子。
  2. 每个盘子从堆的顶部被移动后,只能置放于下一个堆中。
  3. 每个盘子只能放在比它大的盘子上面。

请写一段程序,实现将第一个堆的盘子移动到最后一个堆中。

样例

输入

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(目标塔)中】:只用三步:

  1. 把A(源塔)中最小的盘子放到B(辅助塔)中
  2. 再将A(源塔)中的第二个盘子放到C(目标塔)中
  3. 最后再把B(辅助塔)中的最小的盘子放到C(目标塔)中

结束!

当有三个盘子的时候:用两个盘子时的思维,只用三步:

  1. 我们只用将A(源塔)中的前两个盘子放到B(辅助塔)中
  2. 再将A(源塔)中第三个盘子放到C(目标塔)中
  3. 最后再把B(辅助塔)中的两个盘子放到C(目标塔)中

结束——就怪了。因为还没考虑怎么将A的两个盘子放到B中,所以这个时候的目标就变了,变成了把A中的前两个盘子放到B中,这时候就很明显了,只要把塔的身份变换一下,就和两个盘子时的操作一模一样了。之后第二步也很简单。到了第三步,这个时候,A没有盘子,B有两个盘子,C有一个最大的盘子,这个时候的目标是把B中的两个盘子放到C中。是的,和两个盘子时的目标又是类似,所以替换一下身份再来一次,问题就真的解决了!

所以,当有N个盘子的时候,我们也只要三步:

  1. 把A的N-1个盘子放到B中
  2. 把A所剩下唯一的也是最大的盘子放到C中
  3. 把B中所有的盘子都放到C中

对于第一步,我们又可以转化为这三步:

此时的目标是把盘子从A放到B中

  1. 把A的N-2个盘子放到C中
  2. 把A最大的盘子(对于那N-1个盘子来说)放到B中
  3. 把C中所有的盘子都放到B中

对于这个的第一步,我们又可以……

由此,我们就可以写出代码:

代码

其中的moveTopTomoveDisks方法为需要填补的内容

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

来自汉诺塔_百度百科

上一篇:HTML转义字符&npsp;表示non-breaking space,unicode编码为u'\xa0',超出gbk编码范围?


下一篇:邮件江湖群狼环伺 U-Mail邮件系统防狼有术