Jump to content
  • Advertisement
Sign in to follow this  
CableGuy

Gray code

This topic is 3579 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi. I know about the FAQ and this is indeed partially homework related. I'm not asking someone for a solution but rather a direction. I need to write a recursive function that gets two strings and checks whether they differ by only one bit. The thing is the skeleton of the function is already given (you can assume that the stings only contain 0's and 1's and are of the same length):
boolean IsGray(String s1,String s2)
{
   if ((s1.length()==0) || (s2.length()==0))
      return false;
   if (s1.charAt(0)!=s2.charAt(0))
   {
      // Do stuff
   }
   else
   {
      // Do stuff
   }
}
I only got here:
boolean IsGray(String s1,String s2)
{
   if ((s1.length()==0) || (s2.length()==0))
      return false;
   if (s1.charAt(0)!=s2.charAt(0))
   {
      boolean res=IsGray(s1.substring(1),s2.substring(1));
      if (res)
         return false;
      else
         return true;
   }
   else
   {
      return IsGray(s1.substring(1),s2.substring(1));
   }
}
As expected this code only checks if they differ by an odd number of bits. Any suggestions, tips and such would be greatly appreciated.

Share this post


Link to post
Share on other sites
Advertisement
Quick question: you say you are checking if they differ by only a bit; does this mean that in the case where one bit or less are different, to return true? Or only return true if the strings are identical?

Can you please be very specific as to the 'true' conditions?

Share this post


Link to post
Share on other sites
The function should return true only if the two strings differ by exactly one bit.
For instance:
s1=0001
s2=0000
returns true
but
s1=0001
s2=1000
returns false.

Share this post


Link to post
Share on other sites
Quote:
Original post by CableGuy
The function should return true only if the two strings differ by exactly one bit.
It is often helpful to think of boolean problems in terms of their inverse - in this case, you can return false as soon as you encounter second bit that is different, or at the end of the strings if all bits are the matching.

Share this post


Link to post
Share on other sites
But I can't count how many bits differ. My first thought was when I encounter two bits that are different check if there are more and return false, as written in my first post. But since it is recursive, it checks if the number of bits are odd.

Share this post


Link to post
Share on other sites
Consider these hints:

- For your function, the only data that you can pass recursively are the two strings themselves. This means you need to think about string usage and manipulation.

- Each recursive call always checks the first index of each string to compare. If the function always checks the first index of the string for each recursive call, what would that indirectly imply about the parameter strings that are passed each recursive chain (would they be the same string always or not)?

- Are the parameters passed by reference or by value? If they are passed by value, it means you can modify them in place. If they are passed by reference, then you will be passing a new object. The answer to this does not matter in particular, but it is related to the previous hint.

I think that's about as much can be said without giving it away, good luck [smile]

Share this post


Link to post
Share on other sites
As I see it, the function should "choose" different code paths depending on what was found previously but I can't know that.
Quote:

- Each recursive call always checks the first index of each string to compare. If the function always checks the first index of the string for each recursive call, what would that indirectly imply about the parameter strings that are passed each recursive chain (would they be the same string always or not)?

Sorry didn't quite get you. Did you mean I have to trim the strings I pass? If so did you look at the code at bottom of my first post?

Share this post


Link to post
Share on other sites
Is there any reason why this needs to be recursive in the first place.

With a simple loop over two equal-length strings it shouldn't be hard to inspect each pair of characters and keep a counter how many are different. You can stop earlier as already suggested, or continue till the end of the strings if you for some reason really want to find out the total count of different bits.

Of course, it wouldn't be hard to turn that into recursion either...

Share this post


Link to post
Share on other sites
Quote:
Original post by visitor
Is there any reason why this needs to be recursive in the first place.

With a simple loop over two equal-length strings it shouldn't be hard to inspect each pair of characters and keep a counter how many are different. You can stop earlier as already suggested, or continue till the end of the strings if you for some reason really want to find out the total count of different bits.

Of course, it wouldn't be hard to turn that into recursion either...


It needs to be recursive because that's the requirement.

Share this post


Link to post
Share on other sites
Don't know if I'm giving the answer away, but I'll try to just give you a hint (according to how I solved it). Return in this form: return a + b;. What a and b are, and what operator to use instead of + is up to you ;)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!