Gray code

[c2252011]

Hi.

I am asked to write a program using recursion. when input n, then program will generate all length n bits strings in increasing order.
e.g. n=2, output:00,01,10,11
n=3, output:000,001,010,011,100,101,110,111

here is my code:

#include <iostream>
#include <string>
using namespace std;
void bitString(int x,string prefix){
if (x == 0)
cout << prefix <<endl;
for (int i = 0;i<x;++i){
bitString(x-1,(prefix+"0"));
bitString(x-1,(prefix+"1"));
} }
int main (){
int n;
cin >> n;

bitString(n,"");

system ("pause");
return 0;
}


so y my program's output repeat a few times?

[rambo1177]

Actually you don't need recursion...
The largest number possible is 2ⁿ - 1.
Just run a loop from 0 to 2ⁿ - 1 and print its binary equivalent.

Recursive Code :

#include <iostream>
#include <string>
using namespace std; 
void bitString(int x,string prefix)
{ 
     if (x == 0)
     cout << prefix <<endl; 
     else
     {
      bitString(x-1,(prefix+"0"));
      bitString(x-1,(prefix+"1")); 
     }
} 
int main ()
{
    int n; 
    cin >> n;
    bitString(n,"");
    system ("pause");
    return 0;
}

Your "for " loop in the recursive function is not required.

[c2252011]

Thank you for your reply.

and if i would like to make the program display in such a way that any two gray code in consecutive differ by 1 bit? can i change this above program to generate such outputs?

[rambo1177]

See my previous post...

The program gives the same result u asked for....

[c2252011]

the output from your code is:
000
001
010
011
100
101
110
111

but the output should look like:
000
001
011
010
110
111
101
100

where each line is one bit different from previous.

[rambo1177]

Why would you want that sort of an output?

000 -0
001 -1
011 -3
010 -2....
The series is completely pointless......

[c2252011]

well, i wonder y our teacher wants us to think of a way to generates these output. I understand the first one's logic, but i have no clue to write the second one :'(

[rambo1177]

Which grade u in??????

[c2252011]

LOL..i am year 1 student in uni, i didnt learn anything about programming in high school :(

[rambo1177]

ooooh k

[c2252011]

i got it now :)

[sazzadmim]

Here is non- recursive code.
If you think it may help you then complete it.
I'm posting a recursive code after some time.

#include <iostream>
#include <string>
#include<cmath>
using namespace std;

void print(int num_of_digit, unsigned num)
{
    cout<<num<<endl; //this is for test.
    // Remove the above line and
    //write a code to print num into binary with num_of_digit

}

unsigned short binaryToGray(unsigned short num)
{
        return (num>>1) ^ num;
}

int main ()
{
    int n;
    unsigned num;
    cin >> n;
    //bitString(n,"");
    for(unsigned i=0;i< pow(2,n);i++)
    {
        num = binaryToGray(i);
        print(n,num);
    }

    //system ("pause");
    return 0;
}

[sazzadmim]

Here is a program using recursion. And I think it will fulfill your need.

#include <iostream>
#include <string>
using namespace std;

void print_gray(string binary)
{
    string shift = "0",gray="";
    shift += binary;
    for(int i=0;i< binary.length();i++ )
        if(binary[i] != shift[i] )
            gray += "1";
        else
            gray += "0";
    cout<<gray<<endl;
}

void bitString(int x,string prefix)
{
     if (x == 0){
        print_gray(prefix);
     }

     else
     {
      bitString(x-1,(prefix+"0"));
      bitString(x-1,(prefix+"1"));
     }
}
int main ()
{
    int n;
    cin >> n;
    bitString(n,"");
 //   system ("pause");
    return 0;
}