算法趣题--格雷码构造问题

算法趣题--格雷码构造问题

• 格雷码问题是什么
• • 实现代码（C语言）

格雷码问题是什么

Gray码是一个长度为2的n次方的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好 只有一位不同。试设计一个算法对任意n构造相应的Gray码(分治、减治、变治皆可）。
对于给定的正整数n，格雷码为满足如下条件的一个编码序列。
(1)序列由2的n次方个编码组成，每个编码都是长度为n的二进制位串。
(2)序列中无相同的编码。
(3)序列中位置相邻的两个编码恰有一位不同。

实现代码（C语言）

算法思路：格雷码的取值范围为0—2的n次方，我是直接取十进制的值转换二进制将二进制的每一位补充。
我取n=3。

#include
int a[8][3];
int ddd(int i,int j,int k){//i是十进制数，j是一维数组下标，k是二维数组下标if(i==0){//先判断十进制数是否为0return 0;}int x=i%2;int y=i/2;a[j][k]=x;ddd(y,j,--k);
}
/*初始化数组*/
void init(){for(int i=0;i<8;i++){for(int j=0;j<3;j++){a[i][j]=0;}}
}void main(){init();for(int i=0,j=0;i<8;i++,j++){ddd(i,j,2);}for(int x=0;x<8;x++){for(int y=0;y<3;y++){printf("%d ",a[x][y]);}printf("\n");}
}

还有一种分治思想，将二进制每一位分为0和1两个数字，我们只需要将每一位分成0和1两种情况，最后得到的每个结果同样为2的n次方。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！