Java Reference
In-Depth Information
We need to replace
t
(
n
/
2). If our guess
t
(
n
)
=
1
+
log
2
n
were true for all values of
n
<
k,
we
would have
t
(
k
/
2)
=
1
+
log
2
(
k
/
2), since
k
/
2
<
k
. Thus,
t
(
k
)
=
1
+
t
(
k
/
2)
=
1
+
(1
+
log
2
(
k
/
2))
=
2
+
log
2
(
k
/
2)
=
log
2
4
+
log
2
(
k
/
2)
=
log
2
(4
k
/
2)
=
log
2
(2
k
)
=
log
2
2
+
log
2
k
=
1
+
log
2
k
To summarize, we assumed that
t
(
n
)
=
1
+
log
2
n
for all values of
n
<
k
and showed that
t
(
k
)
=
1
+
log
2
k
. Thus,
t
(
n
)
=
1
+
log
2
n
for all
n
≥
1. Since
power
's time requirement is given by
t
(
n
), the
method is O(log
n
).
7.28
The Towers of Hanoi is a classic problem in computer science whose solution is not obvious. Imagine three
poles and a number of disks of varying diameters. Each disk has a hole in its center so that it can fit over
each of the poles. Suppose that the disks have been placed on the first pole in order from largest to smallest,
with the smallest disk on top. Figure 7-7 illustrates this initial configuration for three disks.
FIGURE 7-7
The initial configuration of the Towers of Hanoi for three disks.
1
2
3
The problem is to move the disks from the first pole to the third pole so that they remain piled
in their original order. But you must adhere to the following rules:
1.
Move one disk at a time. Each disk you move must be a topmost disk.
2.
No disk may rest on top of a disk smaller than itself.
3.
You can store disks on the second pole temporarily, as long as you observe the previous two rules.
7.29
The solution is a sequence of moves. For example, if three disks are on pole 1, the following
sequence of seven moves will move the disks to pole 3, using pole 2 temporarily:
Move a disk from pole 1 to pole 3
Move a disk from pole 1 to pole 2
Move a disk from pole 3 to pole 2
Move a disk from pole 1 to pole 3
Move a disk from pole 2 to pole 1
Move a disk from pole 2 to pole 3
Move a disk from pole 1 to pole 3
Figure 7-8 illustrates these moves.
Question 9
We discovered the previous solution for three disks by trial and error. Using the
same approach, find a sequence of moves that solves the problem for four disks.
