java 河内塔递归算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12483764/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Tower of Hanoi Recursion Algorithm
提问by user564927
I am having a problem understanding this Tower of Hanoi recursion algorithm:
我在理解这个河内塔递归算法时遇到问题：
public class MainClass {
public static void main(String[] args) {
int nDisks = 3;
doTowers(nDisks, 'A', 'B', 'C');
}
public static void doTowers(int topN, char from, char inter, char to) {
if (topN == 1){
System.out.println("Disk 1 from " + from + " to " + to);
}else {
doTowers(topN - 1, from, to, inter);
System.out.println("Disk " + topN + " from " + from + " to " + to);
doTowers(topN - 1, inter, from, to);
}
}
}
The output is:
输出是：
Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C
I don't understand how do we get:
我不明白我们如何得到：
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Can someone please explain?
有人可以解释一下吗？
Thank you.
谢谢你。
回答by Legna
Moving a N disks tower from peg A to C is achieved by moving a N-1 (all disks but the last one) tower from A to B, then moving the Nth disk from A to C, and finally moving the tower previously moved to B, from B to C. This shall be applied any time a tower with more than one disk is moved, in the case of a 1 disk tower, you just move its only disk.
将 N 个圆盘塔从挂钉 A 移到 C 是通过将 N-1（除最后一个圆盘外的所有圆盘）塔从 A 移到 B，然后将第 N 个圆盘从 A 移到 C，最后将先前移到的塔移到B，从 B 到 C。这适用于任何时候有一个以上磁盘的塔被移动，在 1 磁盘塔的情况下，你只需移动它唯一的磁盘。
回答by ajon
If I'm not mistaken you can move 1 disk one peg each turn correct? So you move the first disk from a to b then b to c. That is 2 moves. Then we can now move disk 2 from a to b. Now we can move disk 1 from c back to b. Right now disk 3 is on A and disk 2 and 1 are on a. Now we move disk 1 from a to b then to c. No we need to get disk 1 and 2 on disk 3 in the right order. So we clear disk 1 by moving it from B to A. This allows us to put disk 2 from B to C. Now we finish by moving disk 1 from a to b then to c and we are done.
如果我没记错的话，您可以每转一圈将 1 个圆盘移动一个钉子，对吗？因此，您将第一个磁盘从 a 移到 b，然后将 b 移到 c。那是2个动作。然后我们现在可以将磁盘 2 从 a 移动到 b。现在我们可以将磁盘 1 从 c 移回 b。现在磁盘 3 在 A 上，磁盘 2 和 1 在 a 上。现在我们将磁盘 1 从 a 移到 b 然后移到 c。不，我们需要以正确的顺序在磁盘 3 上获取磁盘 1 和 2。因此，我们通过将磁盘 1 从 B 移到 A 来清除磁盘 1。这允许我们将磁盘 2 从 B 移到 C。现在我们将磁盘 1 从 a 移到 b 然后移到 c，我们就完成了。
Does that answer your question?
这是否回答你的问题？
