I am not getting how you place a move when you get a bit that is
different from previous one
# A bit with a different value to the previous one means that the
corresponding disk is one position to the left or right of the
previous one. Whether it is left or right is determined by this rule:
* Assume that the initial peg is on the left and the final peg is
on the right.
* Also assume "wrapping" - so the right peg counts as one peg
"left" of the left peg, and vice versa.
* Let n be the number of greater disks that are located on the
same peg as their first greater disk and add 1 if the largest disk is
on the left peg. If n is even, the disk is located one peg to the
left, if n is odd, the disk located one peg to the right.
For 8 disks 11011000 = 216
The largest disk is 1, so it is on the right (final) peg.
Disk two is also 1, so it is stacked on top of it, on the right peg.
till now we have
1:
2:8|7
3:
Disk three is 0, so it is on another peg
previous peg=peg 2
left peg=peg 1
right peg=peg 3
now initial peg is on the left implies initial peg=peg 1 and final peg
is on the right means final peg=peg 3
number of greater disks that are located on the same peg as their
first greater disk=2
now the largest disk is on peg = 2 which is not the left peg so n
comes out to be 2 while its given on wiki that
". Since n is odd(n=3), it is one peg to the right, i.e. on the left peg."
please help
Thanks&Regards
Anuj Kumar
On Tue, Jun 15, 2010 at 9:42 PM, Jitendra Kushwaha
<[email protected]> wrote:
> Dear Anuj,
>
> Its easy to do.
> lets take an example
> say we have 4 disks. We will require 2^4-1 = 15 steps to solve it.
> Now suppose we are at 6th step..
> write it binary form using 4 bits(since we have 4 disks) 0110
> now from left 0 means 4th disk is on initial peg
> second bit 1 means disk 3 is on left of the previous disk
> third bit 1 means it is above previous disk
> fourth bit 0 means it is on right of previuos disk
>
> so the solution is something like
> 1: 4|1
> 2:
> 3: 3|2
>
> 1: is initial peg (left of 1 means 3 and right means 2)
> 2: is final peg
>
> hope it is clear how to solve this in O(no_of_disk) complexity
> you can refer this link :
> http://britton.disted.camosun.bc.ca/jbhanoi.htm
>
> comment for any related doubts :)
>
> --
> Regards
> Jitendra Kushwaha
> MNNIT, Allahabad
>
> --
> 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.
