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) = ???
4 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?
I would highly recommend Mr Benjamin services to any person in need of financial help and they will keep you on top of high directories for any further needs. Once again I commend yourself and your staff for extraordinary service and customer service, as this is a great asset to your company and a pleasant experience to customers such as myself. Wishing you all the best for the future.Mr, Benjamin is the best way to get an easy loan,here is their email.. 247officedept@gmail.com Thank You for helping me with loan once again in my sincerely heart I'm forever grateful.
Post a Comment