@Terence Sorry, had misunderstood your solutions earlier. Your approach and calculations both are correct and more efficient than my soln. Initially I was not much convinced with the assumption that in the first solution, all but last pair are in their original order. Later realized that its happening because every pair except last one is moved even number of times causing original order of disks to be recovered. This makes me think on another very simple solution. 1- Move all disks from source to temp. (using approach in first soln) 2- Move all disks from temp to dest.
This will cause even number of moves even for last pair. takes 2f(n) moves [one extra move from your approach though :)]. Thanks, - Ravindra On Sat, Oct 9, 2010 at 8:18 AM, Terence <[email protected]> wrote: > @ravindra > > Great solution. But I need some clarification on my solution to the second. > > My solution to the second is based on the solution to the first. > > As I stated, in the solution to the first, only the last 2 disks are > swapped, while the order of all other disks are preserved. > So moving the same pile of disks twice will preserve the original order of > all disks. > > In step 1) 3) 5) 7) of my solution to the second, the process of a) is > performed for the first (2n-2) disks. (No need to preserve order) > After step 1)-3) and 5)-7), the order of the first (2n-2) disks is > preserved. So order of all disks is preserved after 1)-7). > > Denote the number of moves as f(n) in case a), and g(n) in case b). > We have: > f(n) = 2^(n+1) - 2 and > g(n) = 4f(n-1)+3. > So g(n) = 4*2^n-5 > > > > On 2010-10-9 1:56, ravindra patel wrote: > > @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. > > -- > 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.
