Java Reference
In-Depth Information
recursive algorithm, given in pseudocode. Suppose that needle 1 contains n disks,
where n
1
.
1. Move the top n
- 1
disks from needle 1 to needle 2, using needle 3 as the
intermediate needle.
2. Move disk number n from needle 1 to needle 3.
3. Move the top n
- 1
disks from needle 2 to needle 3, using needle 1 as the
intermediate needle.
This recursive algorithm translates into the following Java method:
public static void
moveDisks(
int
count,
int
needle1,
int
needle3,
int
needle2)
{
if
(count > 0)
{
moveDisks(count-1, needle1, needle2, needle3);
System.out.println("Move disk " + count
+ " from needle "
+ needle1
+ " to needle " + needle3 + ".");
moveDisks(count-1, needle2, needle3, needle1);
}
}
Let us determine how long it would take to move all 64 disks from needle 1 to needle 3.
If needle 1 contains 3 disks, then the number of moves required to move all 3 disks
from needle 1 to needle 3 is 2
3
1
¼
7. Similarly, if needle 1 contains 64 disks, then the
number of moves required to move all 64 disks from needle 1 to needle 3 is 2
64
1.
Because 2
10
¼
1024
1000
¼
10
3
, we have
2
64
¼
2
4
2
60
2
4
10
18
¼
1
:
6
10
19
The number of seconds in one year is approximately 3.2
10
7
. Suppose the priests move
one disk per second and they do not rest. Now:
1
:
6
10
19
¼
5
3
:
2
10
18
¼
5
ð
3
:
2
10
7
Þ
10
11
¼ð
3
:
2
10
7
Þð
5
10
11
Þ
The time required to move all 64 disks from needle 1 to needle 3 is roughly 5
10
11
years. It is estimated that our universe is about 15 billion years old (1.5
10
10
). Also,
5
10
11
¼
50
10
10
33
(1.5
10
10
). This calculation shows that our universe
would last about 33 times as long as it already has.
Assume that a computer can generate 1 billion (10
9
) moves per second. Then, the
number of moves that the computer can generate in one year is:
ð
3
:
2
10
7
Þ
10
9
¼
3
:
2
10
16
1
3
Search WWH ::
Custom Search