格雷码的几种实现方式 递归 迭代 递推

1
递归方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class GrayCode {
public:
    vector<string> getGray(int n) {
        // write code here
        vector<string> res;
        if(n == 1) {
            res.push_back("0");
            res.push_back("1");
            return res;
        }
        vector<string> v = getGray(n - 1);
        for(int i = 0; i < v.size(); i++) {
            res.push_back("0" + v[i]);
        }
        for(int i = v.size() - 1; i >= 0; i--) {
            res.push_back("1" + v[i]);
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void Gray(int n)
{
    if(n<=0)
        return;
    vector<string> result;
    int len=pow(2,n);
    result.reserve(len);
    result.push_back("0");
    result.push_back("1");
    for(int i=1;i<n;i++)
    {
        for(int j=result.size();j>0;)
        {
              result.push_back(result[--j]);
        }
        for(int j=0;j<result.size()/2;j++)
            result[j]="0"+result[j];
        for(int j=result.size()/2;j<result.size();j++)
            result[j]="1"+result[j];
    }
    for(int i=0;i<len;i++)
        cout<<result[i]<<endl;
}

1
2
3
4
5
6
7
8
void gray_code(int n)
{
	int *a=new int[1<<n];
	for(int i=0;i<1<<n;i++)
	{
		a[i]=i<<1^i;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<pre class="html" name="code">void _10_2(int n,int nb=0)//十进制转为二进制字符串
{
	int m = log(n*1.0) / log(2.0);
	if (nb != 0)
	{
		string rreess(nb, '0');
		for (int i = 0; i <= m; i++)
		{
			int r = (n&(1 << (m - i))) >> (m - i);
			rreess[nb - m - 1 + i] = r + '0';
		}
		cout << rreess;
	}
	else
	{
		char res[1000] = { 0 };
		for (int i = 0; i <= m; i++)
		{
			int r = (n&(1 << (m - i))) >> (m - i);
			res[i] = r + '0';
		}
		cout << res;
	}

}

 

1