河内递归算法塔

Question

我在理解这个河内塔递归算法时遇到了问题:

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

我不明白我们怎么做:

Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A

有人可以解释一下吗？

谢谢.

Answer 1

通过将N-1(所有磁盘,但最后一个)塔从A移动到B,然后将第N个磁盘从A移动到C,最后移动先前移动到的塔,实现将N个磁盘塔从挂钉A移动到C. B,从B到C.每当移动一个具有多个磁盘的塔时,都应该应用这种情况.对于1个磁盘塔,只需移动其唯一的磁盘.