河内塔递归算法 [英] Tower of Hanoi Recursion Algorithm

问题描述

我在理解此河内塔递归算法时遇到问题：

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);
    }
  }
}

输出为：

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

有人可以解释吗？

谢谢。

推荐答案

从钉子中移出N个磁盘塔通过将N-1个塔（除最后一个以外的所有磁盘）从A移到B，然后将第N个磁盘从A移到C，最后将先前移到B的塔从B移到C，可以实现A到C。每当移动一个以上磁盘的塔时，都应应用此方法；对于1磁盘塔的情况，只需移动其唯一的磁盘即可。

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.

这篇关于河内塔递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！