@Terence Solution for first one is trivial. Just double the number of moves of typical ToH as each pair requires now 2 moves.
In second one the approach is correct but the calculation is wrong. F(n) = 4f(n-1) + 3 = 3(4^n -1)/(4-1) = 4^n-1 = 2^2n -1. This can however be optimized as you can reduce the number of recursions. 1- Move (2n-2, From source, to dest) [f(n-1)] 2- Move the last 2 disks from source to temp (2 moves and order reversed) 3- Move (2n-2, From dest, to source) [f(n-1)] 4- Move the last 2 disks from temp to dest (2 moves and original order recovered) 5- Move(2n-2, From source, to dest) [f(n-1)] so f(n) = 3f(n-1) + 4, f(1) = 4 f(n) = 4(3^n -1)/(3-1) = 2(3^n -1) For larger n(>2) this is more efficient. Thanks, - Ravindra On Fri, Oct 8, 2010 at 1:42 PM, Terence <[email protected]> wrote: > > > 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
