On 2010-10-8 15:14, snehal jain wrote:
A Double Tower of Hanoi contains 2n disks of n different sizes, two of
each size. As usual, we’re required to move only one disk at a time,
without putting a larger one over a smaller one.
a. How many moves does it take to transfer a double tower from one
peg to another, if disks of equal size are indistinguishable from each
other?
Denote the minimum moves as f(n).
Like the classical Tower of Hanoi:
1) move the first (2n-2) disks from Peg 0 to Peg 1 -- f(n-1) moves
2) move the last 2 disks from Peg 0 to Peg 2 -- 2 moves
3) move the (2n-2) disks from Peg1 to Peg 2 -- f(n-1) moves
f(n) = 2f(n-1) + 2, f(1) = 2
So f(n) = 2^(n+1) - 2
b. What if we are required to reproduce the original top-to-bottom
order of all the equal-size disks in the final arrangement?
Denote the minimum moves as g(n).
It can be proved that, in case a, only the last 2 disks are swapped. The
order of all other disks are preserved.
So we only need to modify the process to restore the order of the last 2
disks.
1) move the first (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves
2) move the second last disk from Peg 0 to Peg 1 -- 1 move
3) move the (2n-2) disks from Peg 2 to Peg 1 -- f(n-1) moves
4) move the last disk from Peg 0 to Peg 2 -- 1 move
5) move the first (2n-2) disks from Peg 1 to Peg 0 -- f(n-1) moves
6) move the second last disk from Peg 1 to Peg 2 -- 1 move
7) move the (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves
g(n) = 4f(n-1)+3
= 2^(n+2)-5
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
