格雷码的定义:相邻的编码,二进制只有1位不同,这样可以防止冲突,数字逻辑的。
第一种 ---------------------- 按生成规律
格雷码产生的规律是:第一步,改变最右边的位元值;第二步,改变右起第一个为1的位元的左边位元;第三步,第四步重复第一步和第二步,直到所有的格雷码产生完毕(换句话说,已经走了(2^n) - 1 步)。
用一个例子来说明:
假设产生3位元的格雷码,原始值位 000
第一步:改变最右边的位元值: 001
第二步:改变右起第一个为1的位元的左边位元: 011
第三步:改变最右边的位元值: 010
第四步:改变右起第一个为1的位元的左边位元: 110
第五步:改变最右边的位元值: 111
第六步:改变右起第一个为1的位元的左边位元: 101
第七步:改变最右边的位元值: 100
需要注意的是,代码的健壮性, unsigned int 的范围是 0~ 2^32-1 ..所以,要保证输出的 n 要小于32
// 对 字符串 第 i+1 个字符进行反转 0->1 1->0
void MyQuFan(char * num,int i){
if( num[i] == '0'){
num[i] = '1';
}
else{
num[i] = '0';
}
}
// 找到字符串中,右边起,第一个1的左边的那个索引
int FindLeft(char * num,int len){
int r = len - 1;
for( ; r >= 0; r--){
if( num[r] == '1')
break;
}
r--;
return r;
}
// 生成 n 位 格雷码
void newMakeGray(int n ){
clock_t st = clock();
if( n <1 || n >32)
return ;
if( n == 1){
cout << "0" << endl;
cout << "1" << endl;
return ;
}
unsigned int l = (unsigned int)pow(2,n);
char * num = new char[n+1];
memset(num,'0',n+1);
num[n] = 0;
cout << num << endl;
for( unsigned int i = 1; i<=l-1;i++){
if( i & 1){
//取反最右边的一个
MyQuFan(num,n-1);
}else{
//找到最右边
int left = FindLeft(num,n);
MyQuFan(num,left);
}
cout << num << endl;
}
printf_cpudifftime(st);
}
第二种 ----------------------------按发现的规律
这种方法基于格雷码是反射码的事实,利用递归的如下规则来构造:
2位格雷码 | 3位格雷码 | 4位格雷码 | |
---|---|---|---|
00 01 11 10 | 000 001 011 010 110 111 101 100 | 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 |
这样的话,我们就可以写出递归方式。这里需要注意,因为,这里用的是字符串数组,那么,由于每个进程的堆空间是有限制的,一般不能超过1G,所以这里大概估摸了下,n要小于24.
// 生成存储 n 位的字符串数组
char ** GennerChar(int n ){
//要这么多个
unsigned int l = (unsigned int)pow(2,n);
char ** p = new char*[l];
for(unsigned int i = 0;i<l;i++){
p[i] = new char[n+1];
memset(p[i],0,n+1);
}
return p;
}
// 释放内存
void deleteChar(char** p,int n ){
unsigned int l = (unsigned int)pow(2,n);
for(unsigned int i = 0;i<l;i++){
delete []p[i];
}
delete []p;
}
void show(char ** p,int n){
unsigned int l = (int)pow(2,n);
for(unsigned int i = 0;i<l;i++){
cout << p[i] << endl;
}
deleteChar(p,n);
}
void Gray(char ** num , int len, int max){
if ( len > max)
return ;
//计算出上一个有多少个,和现在应该有多少个
unsigned int pl = (int)pow(2,len-1);
unsigned int nl = (int)pow(2,len);
char ** n = NULL;
try{
n = GennerChar(len);
}catch(bad_alloc& e){
cout << e.what() << endl;
deleteChar(num,len-1);
}
// 在前面的基础上,加0 和 1
for( int i = 0;i < 2;i++){
for(unsigned int j = 0;j<pl;j++){
unsigned int cur = i*pl+j;
//逆序
if( i == 1){
n[cur][0] = '1';
strcat(n[cur],num[pl-j-1]);
}
//顺序
else{
n[cur][0] = '0';
strcat(n[cur],num[j]);
}
}
}
deleteChar(num,len-1);
if( len == max){
show(n,len);
return ;
}
Gray(n,len+1,max);
}
void MakeGray(int n ){
if( n < 0 || n >= 24)
return ;
if( 1 == n){
cout << "0" << endl;
cout << "1" << endl;
}
char ** num = GennerChar(1);
strcpy(num[0],"0");
strcpy(num[1],"1");
Gray(num,2,n);
}