Java Reference
In-Depth Information
7.
You can get a solution to the Towers of Hanoi problem by using the following iterative algorithm. Beginning with
pole 1 and moving from pole to pole in the order pole 1, pole 3, pole 2, pole 1, and so on, make at most one move
per pole according to the following rules:
•
Move the topmost disk from a pole to the next possible pole in the specified order. Remember that
you cannot place a disk on top of a smaller one.
•
If the disk that you are about to move is the smallest of all the disks and you just moved it to the
present pole, do not move it. Instead, consider the next pole.
This algorithm should make the same moves as the recursive algorithms given in Segment 7.31 and pictured in
Figure 7-8. Thus, this iterative algorithm is O(2
n
) as well.
Implement this algorithm.
8.
Write an application or applet that animates the solution to the Towers of Hanoi problem. The problem asks you to
move
n
disks from one pole to another, one at a time. You move only the top disk on a pole, and you place a disk only
on top of larger disks on a pole. Since each disk has certain characteristics, such as its size, it is natural to define a
class of disks.
Design and implement an ADT tower that includes the following operations:
•
Add a disk to the top of the disks on the pole
•
Remove the topmost disk
Also, design and implement a class that includes a recursive method to solve the problem.
9.
Java's class
Graphics
has the following method to draw a line between two given points:
/** Draws a line between the points (x1, y1) and (x2, y2).*/
public
void
drawLine(
int
x1,
int
y1,
int
x2,
int
y2)
Graphics
uses a coordinate system that measures points from the top left corner of a window.
Write a recursive method that draws a picture of a 12-inch ruler. Mark inches, half inches, quarter inches, and
eighth inches. Mark the half inches with marks that are smaller than those that mark the inches. Mark the quarter
inches with marks that are smaller than those that mark the half inches, and so on. Your picture need not be full
size.
Hint
: Draw a mark in the middle of the ruler and then draw rulers to the left and right of this mark.
10.
Imagine a row of
n
lights that can be turned on or off only under certain conditions, as follows. The first light
can be turned on or off anytime. Each of the other lights can be turned on or off only when the preceding
light is on and all other lights before it are off. If all the lights are on initially, how can you turn them off?
For three lights numbered 1 to 3, you can take the following steps, where 1 is a light that is on and 0 is a light
that is off:
1 1 1
All on initially
0 1 1
Turn off light 1
0 1 0
Turn off light 3
1 1 0
Turn on light 1
1 0 0
Turn off light 2
0 0 0
Turn off light 1
You can solve this problem in general by using mutual recursion, as follows:
Algorithm
turnOff(n)
//
Turns off
n
lights that are initially on
.
if
(n == 1)
Turn off light 1
