Java Reference
In-Depth Information
LISTING 12.4
continued
//-----------------------------------------------------------------
// Prints instructions to move one disk from the specified start
// tower to the specified end tower.
//-----------------------------------------------------------------
private void
moveOneDisk (
int
start,
int
end)
{
System.out.println ("Move one disk from " + start + " to " +
end);
}
}
Note that the parameters to
moveTower
describing the pegs are switched around
as needed to move the partial stacks. This code follows our general strategy and
uses the
moveTower
method to move all partial stacks. Trace the code carefully
for a stack of three disks to understand the processing. Compare the processing
steps to Figure 12.6.
Contrary to its short and elegant implementation, the solution
to the Towers of Hanoi puzzle is terribly inefficient. To solve the
puzzle with a stack of
N
disks, we have to make 2
KEY CONCEPT
The Towers of Hanoi solution has
exponential complexity, which is
very inefficient. Yet the implemen-
tation of the solution is incredibly
short and elegant.
N
−1 individual
disk moves. This situation is an example of
exponential complex-
ity.
As the number of disks increases, the number of required moves
increases exponentially.
Legend has it that priests of Brahma are working on this puzzle in a temple at
the center of the world. They are using 64 gold disks, moving them between pegs
of pure diamond. The downside is that when the priests finish the puzzle, the
world will end. The upside is that even if they move one disk every second of every
day, it will take them over 584 billion years to complete it. That's with a puzzle
of only 64 disks! It is certainly an indication of just how intractable exponential
algorithmic complexity is.
SELF-REVIEW QUESTIONS
(see answers in Appendix N)
SR 12.11
Under what conditions does the recursion stop in the
MazeSearch
program?
SR 12.12
Identify where in the
MazeSearch
program each of the following is
provided.
Search WWH ::
Custom Search