参考文献

  • Classic Computer Science Problems in Java

汉诺塔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.Stack;

public class Hanoi {
	private final int numDiscs;
	public final Stack<Integer> towerA = new Stack<>();
	public final Stack<Integer> towerB = new Stack<>();
	public final Stack<Integer> towerC = new Stack<>();

	public Hanoi(int discs) {
		numDiscs = discs;
		for (int i = 1; i <= discs; i++) {
			towerA.push(i);
		}
	}

	private void move(Stack<Integer> begin, Stack<Integer> end, Stack<Integer> temp, int n) {
		if (n == 1) {
			end.push(begin.pop());
		} else {
			move(begin, temp, end, n - 1);
			move(begin, end, temp, 1);
			move(temp, end, begin, n - 1);
		}
	}
	// m(begin,end,temp,3)
	// m(begin,temp,end,2)
	// 		m(begin,end,temp,1) end.push(begin.pop)  begin(1,2) end(3) temp() a->c
	// 		m(begin,temp,end,1) temp.push(begin.pop) begin(1) end(3) temp(2)  a->b
	// 		m(end,temp,begin,1) temp.push(end.pop) begin(1) end() temp(2,3)	  c->b
	// m(begin,end,temp,1) end.push(begin.pop)  begin() end(1) temp(2,3)      a->c
	// m(temp,end,begin,2)
	// 		m(temp,begin,end,1) begin.push(temp.pop) begin(3) end(1) temp(2)  b->a
	// 		m(temp,end,begin,1) end.push(temp.pop) begin(3) end(1,2) temp()	  b->c
	// 		m(begin,end,temp,1) end.push(begin.pop) begin() end(1,2,3) temp() a->c

	public void solve() {
		move(towerA, towerC, towerB, numDiscs);
	}

	public static void main(String[] args) {
		Hanoi hanoi = new Hanoi(3);
		hanoi.solve();
		System.out.println(hanoi.towerA);
		System.out.println(hanoi.towerB);
		System.out.println(hanoi.towerC);
	}

}