汉诺塔问题

发表于 | 分类于

题目（算法课第八课）

古代有一个梵塔,塔内有三个座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个塔看作一步完成的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
> >