主题：如何构造格雷码？
flks
[专家分：0] 发布于 2005-04-05 11:46:00
各位编程高手：
请帮忙！构造格雷码！
“格雷码”（gray code）是一个长度为2的n 次方的序列，满足：
（a），每个元素都是长度为n比特的串，
（b），序列中无相同元素
（c）。连续的两个元素恰好只有1比特的不同。例如：n=2时，格雷码为{00，01，11，10}
要求：
（1）。构造n=3时的格雷码。
（2）。利用分治策略设计一个算法对任意的n构造相应的“格雷码”。（语言不限）
小飞
回复列表 （共15个回复）
沙发
springsimba [专家分：30] 发布于 2005-04-08 09:33:00
方法很多的，我说其中的一个吧
先构造一个立方图，顶点是编号，只要能有一个通路就可以了，路径就是格雷码
板凳
flks [专家分：0] 发布于 2005-04-17 11:14:00
大哥，可否说具体一些？
立方图怎么构造？
3 楼
wsppl [专家分：100] 发布于 2005-04-17 15:49:00
不知道你有没有学过数字电路，你可以参考卡诺图的方法来求出表达式后构造程序就很简单了~~~
4 楼
LangHua888 [专家分：600] 发布于 2005-04-23 21:27:00
你可以这样构造：
当n=1时
0
1
当n=2时,设结果为一个二维数组
第一列为
0
0
1
1
加上第二列为
00
01
11
10
规律为（下标从零开始）
第一列的改变的位置为1-4（即2的平方）中对2（即2的(2-1)次幂）取模得零的数，除去0
第二列的改变的位置为1-4（即2的平方）中对1(即2的(2-2)次幂）取模得零的数，除去0
利用这样的规律可以构造任何位数的格雷码
当n=3时
000
001
011
010
110
111
101
100
也可以利用规律编程实现一个非递归算法
但是我个人认为不太好，仅供参考
5 楼
LangHua888 [专家分：600] 发布于 2005-04-23 21:30:00
当n=3时
000 在第二列中0011与1100正好反向，在第三列中01于10正好反向
001
011
010
110
111
101
100
6 楼
LangHua888 [专家分：600] 发布于 2005-04-23 21:34:00
如果需要源码，几天后我会发上去的
7 楼
281490635 [专家分：0] 发布于 2006-03-02 09:58:00
8 楼
281490635 [专家分：0] 发布于 2006-03-02 10:00:00
各位高手,能把构造格雷码的源码传上来吗?谢谢!
9 楼
ccpp [专家分：9360] 发布于 2006-04-03 12:01:00
知道用递归，
1）求n-1位的格雷码。
2）反向顺序将n-1位的格雷码重写一便。
3）在第1步得到的格雷码前面加0，在第2步得到的格雷码前面加1。
我不会代码的实现！希望高手贴出代码！！！！！！
所以
顶！！
10 楼
ccpp [专家分：9360] 发布于 2006-04-03 13:51:00
再顶！
我来回复
您所在位置：