For example, if a single disk is to be moved from Tower A to Tower B (using Tower C), then moving the disk directly from A to B is not allowed. The disk must be first transferred to Tower C and then to Tower B.

The purpose is to find the shortest sequence / number of moves we can do this in :

- T(0) = 0 (basis case, nothing to move)
- T(1) = 2 (from above)
- T(n-discs) = ???

## 2 comments:

If we work out the small cases, we see that :

T(1) = 2

T(2) = 8

T(3) = 26

Also, to transfer the 'n'th disc from Tower A to Tower B, we must first transfer the previous 'n-1' discs from Tower A to Tower B. Now, since direct transfers are forbidden, the approach will be this :

1.> move the 'n-1' discs from Tower A to Tower B

2.> move 'n'th disc to Tower C

3.> move 'n-1' discs from Tower B to Tower A

4.> move 'n'th disc from Tower C to Tower B

5.> Now recursively transfer the 'n-1'th disc from Tower A to Tower B

From above we can see that

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

which means

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

solving this :

T(n) + 1 = 3 * [T(n-1) + 1)

using U(n) = T(n) + 1, we get

U(n) = 3*U(n-1)

which can be solved to be :

U(n) = 3^n (for n > 0)

Hence,

T(0) = 0 and

T(n) = 3^n - 1 (for n > 0)

Hi

Do you have any pseudocode for this?

Post a Comment