Java Reference
In-Depth Information
For
n
>
1, the algorithm uses two recursive calls to solve problems that have
n
-
1 disks each. The
required number of moves in each case is
m
(
n
-
1). Thus, you can see from the algorithm that
m
(
n
)
=
m
(
n
-
1)
+
1
+
m
(
n
-
1)
=
2
m
(
n
-
1)
+
1
From this equation, you can see that
m
(
n
)
>
2
m
(
n
-
1). That is, solving the problem with
n
disks
requires more than twice as many moves as solving the problem with
n
-
1 disks.
It appears that
m
(
n
) is related to a power of 2. Let's evaluate the recurrence for
m
(
n
) for a few
values of
n
:
m
(1)
=
1,
m
(2)
=
3,
m
(3)
=
7,
m
(4)
=
15,
m
(5)
=
31,
m
(6)
=
63
It seems that
m
(
n
)
=
2
n
-
1
We can prove this conjecture by using mathematical induction, as follows.
Proof by induction that
m
(
n
)
=
2
n
-
1.
We know that
m
(1)
=
1 and 2
1
-
1
=
1, so the conjecture is
true for
n
=
1. Now assume that it is true for
n
=
1, 2, . . . ,
k
, and consider
m
(
k
+
1).
7.33
m
(
k
+
1)
=
2
m
(
k
)
+
1
(use the recurrence relation)
=
2 (2
k
-
1)
+
1
(we assumed that
m
(
k
)
=
2
k
-
1)
=
2
k
+ 1
-
1
Since the conjecture is true for
n
=
k
+
1, it is true for all
n
≥
1.
7.34
Exponential growth.
The number of moves required to solve the Towers of Hanoi problem grows
exponentially with the number of disks
n
. That is,
m
(
n
)
=
O(2
n
). This rate of growth is alarming, as
you can see from the following values of 2
n
:
2
5
=
32
2
10
=
1024
2
20
=
1,048,576
2
30
=
1,073,741,824
2
40
=
1,099,511,627,776
2
50
=
1,125,899,906,842,624
2
60
=
1,152,921,504,606,846,976
Remember the monks mentioned at the end of Segment 7.29? They are making 2
64
-
1 moves. It
should be clear that you can use this exponential algorithm only for small values of
n
, if you want
to live to see the results.
Before you condemn recursion and discard our algorithm, you need to know that you cannot
do any better. Not you, not the monks, not anyone. We demonstrate this observation next by using
mathematical induction.
Proof that Towers of Hanoi cannot be solved in fewer than 2
n
-
1 moves.
We have shown that our
algorithm for the Towers of Hanoi problem requires
m
(
n
)
=
2
n
-
1 moves. Since we know that at least
one algorithm exists—we found one—there must be a fastest one. Let
M
(
n
) represent the number of
moves that this optimal algorithm requires for
n
disks. We need to show that
M
(
n
)
=
m
(
n
) for
n
7.35
1.
When the problem has one disk, our algorithm solves it in one move. We cannot do better, so
we have that
M
(1)
=
m
(1)
=
1. If we assume that
M
(
n
-
1)
=
m
(
n
-
1), consider
n
disks. Looking
back at Figure 7-9b, you can see that at one point in our algorithm the largest disk is isolated on one
pole and
n
-
1 disks are on another. This configuration would have to be true of an optimal algo-
rithm as well, for there is no other way to move the largest disk. Thus, the optimal algorithm must
have moved these
n
-
1 disks from pole 1 to pole 2 in
M
(
n
-
1)
=
m
(
n
-
1) moves.
≥
