The Tower of Hanoi (ToH) Game is described as follows: l. ToH contains n disks s

Question

The Tower of Hanoi (ToH) Game is described as follows: l. ToH contains n disks stacked with large at the bottom. 2. The disks are numbered from 1 to n starting from small. 3. A player is supposed to move the entire stack from one pole to another using the third pole. 4. The player will receive dollar k if he/she moves disk k. a. Form a recurrence relation and initial condition for the winning amount W_n for playing n disks a1. Solve your recurrence problem. Solution: W_n = 2^n+1 - n - 2, n greaterthanorequalto 1 b. If the player is allowed to move the disks only to adjacent poles, Formulate and solve the winning amount A_n. Solution: A_n = 3^n+1/2 - n - 3/2, n greaterthanorequalto 1.

Explanation / Answer

a) recurrence relation is given by the following:

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

where T(1) =1

a1) solving recurrence problem:

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

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

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

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

T(n) = 24 T ( n-4 ) + 15

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

if k = n-1 then

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

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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