格雷码

发表于 | 分类于 |
字数统计: 369 | 阅读时长 ≈ 1

格雷码

格雷码就是前一个数的格雷码和后一个数的格雷码只有一位二进制不一样。第一个数和最后一个也一样。

格雷码的生成有很多种方式

第一种是直接从二进制获取格雷码，首位保留，后面的第i位格雷码为第i-1位二进制和第i位的异或值。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
using namespace std;
int n;
int bin(int x){
    if(x==0) return 0;
    int pre_b = bin(x/2);
    int b = x%2;
    cout<<(b^pre_b);
    return b;
}
int main(){
    while(cin>>n){
        bin(n);
        cout<<endl;
    }
    return 0;
}

不过这道题是规定了二进制码的长度然后输出所有的格雷码。

（1） 初始化0的格雷码为全0

（2） 改变最右边的位元值

（3） 改变右起第一个为1的位元的左边位元

（4） 重复上面的步骤直到所有格雷码都产生

时间复杂度$O(n^2)$

代码如下

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
29
#include<iostream>
using namespace std;
int n;
int gray[20];
void cout_gray(int*  gray,int n){
    for(int i=0;i<n;i++)
        cout<<gray[i];
    cout<<endl;
}
int main(){
    while(cin>>n){
        for(int i=0;i<n;i++) gray[i]=0;
        cout_gray(gray,n);
        int count=1;
        do{
            if(count%2==1){
                gray[n-1]^=1;
            }else{
                int site = n-1;
                while(gray[site]==0) site--;
                gray[(site-1+n)%n]^=1;
            }
            cout_gray(gray,n);
            count++;
        }while(count<pow(2,n));
        cout<<endl;
    }
    return 0;
}
0%