题目（算法课第八课）

古代有一个梵塔,塔内有三个座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上(如图)。有一个和尚想把这64个盘子从A座移到C座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。在移动过程中可以利用B座,要求输出移动的步骤 。

分析

递归。
划分为子问题。

步骤

所以整个步骤:
1.搬运n-1个碟子到中间针（from -> help）(递归)
2.搬运第n个碟子到目的针 （from -> to）
3.搬运中间针的n-1个碟子到目的针（help -> to）(递归)

递归调用只要有整体观念就行了,在写代码的过程中可以把移动n-1个塔看作一步完成的

代码

public class Hanoi {
    static int b = 0;
    public static void hanoi(int n, String from, String help, String to) {
        if (n == 1) {//base case
            System.out.printf("%d号盘：%s-->%s\n", n, from, to);
            b++;
        } else {
        //1.搬运n-1个碟子到中间针（from -> help）(递归) 
            hanoi(n - 1, from, to, help);
        //2.单独搬运第n个碟子到目的针 （from -> to）
            System.out.printf("%d号盘：%s-->%s\n", n, from, to);
        //3.搬运中间针的n-1个碟子到目的针（help -> to）(递归) 
            hanoi(n - 1, help, from, to);
            b++;
        }
    }

    public static void main(String[] args) {
        int n = 4;
        hanoi(n, "A", "B", "C");
        System.out.println("一共搬运的次数"+b);
    }
}

输出：

1号盘：A-->B
2号盘：A-->C
1号盘：B-->C
3号盘：A-->B
1号盘：C-->A
2号盘：C-->B
1号盘：A-->B
4号盘：A-->C
1号盘：B-->C
2号盘：B-->A
1号盘：C-->A
3号盘：B-->C
1号盘：A-->B
2号盘：A-->C
1号盘：B-->C
15