please explain what happens when we get a different bit from the previous one.
On Wed, Jun 16, 2010 at 4:53 PM, ANUJ KUMAR <[email protected]> wrote: > 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.
