Java Reference
In-Depth Information
18.21
Will the program work if lines 20-21 is replaced by the following code?
for
(File file: files)
size += getSize(file);
// Recursive call
The Tower of Hanoi problem is a classic problem that can be solved easily using
recursion, but it is difficult to solve otherwise.
Key
Point
The problem involves moving a specified number of disks of distinct sizes from one tower to
another while observing the following rules:
There are
n
disks labeled 1, 2, 3, . . . ,
n
and three towers labeled A, B, and C.
■
No disk can be on top of a smaller disk at any time.
■
All the disks are initially placed on tower A.
■
Only one disk can be moved at a time, and it must be the smallest disk on a tower.
■
The objective of the problem is to move all the disks from A to B with the assistance of C. For
example, if you have three disks, the steps to move all of the disks from A to B are shown in
Figure 18.6.
0
4
2
3
1
2
3
A
B
C
A
B
C
Original position
Step 4: Move disk 3 from A to B
1
5
2
3
1
1
3
2
A
B
C
A
B
C
Step 1: Move disk 1 from A to B
Step 5: Move disk 1 from C to A
2
6
2
3
3
1
2
1
A
B
C
A
B
C
Step 2: Move disk 2 from A to C
Step 6: Move disk 2 from C to B
3
7
1
1
2
3
2
3
A
B
C
A
B
C
Step 3: Move disk 1 from B to C
Step 7: Move disk 1 from A to B
F
IGURE
18.6
The goal of the Tower of Hanoi problem is to move disks from tower A to
tower B without breaking the rules.
Search WWH ::
Custom Search