题目（算法课第八课）
古代有一个梵塔,塔内有三个座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
