@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]
<mailto:[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]
<mailto:[email protected]>.
To unsubscribe from this group, send email to
[email protected]
<mailto: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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
