\"Java\" Towers of Hanoi Suppose n disks with a center hole are stacked up on pe

Question

"Java" Towers of Hanoi

Suppose n disks with a center hole are stacked up on peg1 and they are to be moved over to peg3.

Pseudo code:

- move n-1 disks over to peg2

- move the bottom disk over peg3

- move the n-1 disks from peg2 over to peg 3

determine T(1) and T(2)

Verify the recursion: T(n+1) = 2 T(n) + 1

Verify the formula: T(n) = 2^n - 1

Assuming a monk can execute one move in one second. Compute T(64) in a sensible time unit.

Assuming a monk of superfast hand can execute one move in a nanosecond. Compute T(64) in a sensible time unit.

Explanation / Answer

The base case - when n is 1 - is easy: The monks just move the single disk directly.

T(1) = 1.

In the other cases, the monks follow our three-step procedure. First they move the (n-1)-disk tower to the spare peg; this takes t(n-1) moves. Then the monks move the nth disk, taking 1 move. And finally they move the (n-1)-disk tower again, this time on top of the nth disk, taking t(n-1) moves. This gives us our recurrence relation,

T(n) = 2 T(n-1) + 1.

Now,

T(n) = 2 T(n-1) + 1.

=> T(n) = 2[2T(n-2) + 1]

= 2[2[2T(n-3) + 1] + 1] = 2[2[2......[2T(n-k) + 1] + 1]....1]

Now for k = n-1, we have

T(n) = 2k * T(n-(n-1)) + [1 + 2 + 4 + 16 +....2k]

= 2k * T(1) + 2k - 1

= 2 * 2k - 1

= 2k+1 - 1 = 2n - 1 (proved)

For T(64), the monks will move 2^64 - 1 (about 18.45x1018) disks. If they move a disk in 1 second, then T(64) will take 584.6 billion years.

Howeever, if they move a disk in 1 nanosecond, then T(64) will take 584.6 years.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.