In last post, we wondered what on earth the number 2n-1 doing (regardless of how many N rings we used!) in our little towers problem, for all the values of N.
1) make a tower N-1 on the transit tower
2) move ring N from source to the final destination
3) make a tower N-1 on final destination
That involved 2 towers with height N-1 and moving of one ring. Similarly making a tower of N-1 will be equal to making 2 towers of N-2 and moving a ring. if we expand this for 3 ring case:
tower of 3 = 2 * (tower of 2) + 1 = 2 * (2*(tower of 1) +1) + 1 = 2 * (2*(1) +1) + 1 = 7 = 23 - 1
(since making a tower of 1 always takes one move)
so, making a tower of 3 involved making 2 towers of 2 and 1 move.
that is, 4 towers of 1 and 2 + 1 moves.
that is, 2(3-1) towers of 1 and 21 + 20 moves. (making a tower of 1 takes just 1 move)
that is, 2n-1 + (2n-2 + 2n-3 + 2n-4 + ... + 20)
Total Steps = 2n-1 + (2n-2 + 2n-3 + 2n-4 + ... + 1)
but the sum of sequence (2n-2 + 2n-3 + 2n-4 + ... + 1) = 2n-1 - 1
Hence total steps = 2n-1 + 2n-1 - 1 = 2 * (2n-1 ) - 1 = 2n-1 !!
Wow, now we know why it has to be 2n-1 always !!
Our series is only just starting to get interesting! Now to the today's challenge :
We can now write a nice recursive function to solve the puzzle. However, what we are solving is actually a subset of the problem. We have so far considered cases where all the rings are in tower 1. How about we removing that restriction, how about letting the rings to be anywhere on 3 towers (as long as a bigger ring is not upon a smaller). Can we come up with the code to resolve that ?
In fact, this can be considered as the general case in Towers of Hanoi. What we have discussed in earlier posts was just a specific subset of it. In the next post, we will come with few more hits on how to approach that.
Meanwhile, try it out yoursef!
No comments:
Post a Comment