Gray Code简介及生成
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。
格雷码属于可靠性编码，是一种错误最小化的编码方式。因为，虽然自然二进制码可以直接由数/模转换器转换成模拟信号，但在某些情况，例如从十进制的3转换为4时二进制码的每一位都要变，能使数字电路产生很大的尖峰电流脉冲。而格雷码则没有这一缺点，它在相邻位间转换时，只有一位产生变化。它大大地减少了由一个状态到下一个状态时逻辑的混淆。由于这种编码相邻的两个码组之间只有一位不同，因而在用于方向的转角位移量－数字量的转换中，当方向的转角位移量发生微小变化（而可能引起数字量发生变化时，格雷码仅改变一位，这样与其它编码同时改变两位或多位的情况相比更为可靠，即可减少出错的可能性。
格雷码是一种绝对编码方式，典型格雷码是一种具有反射特性和循环特性的单步自补码，它的循环、单步特性消除了随机取数时出现重大误差的可能，它的反射、自补特性使得求反非常方便。
由于格雷码是一种变权码，每一位码没有固定的大小，很难直接进行比较大小和算术运算，也不能直接转换成液位信号，要经过一次码变换，变成自然二进制码，再由上位机读取。
典型格雷码是一种采用绝对编码方式的准权码，其权的绝对值为2^i-1(设最低位i=1)。
格雷码的十进制数奇偶性与其码字中1的个数的奇偶性相同。
根据格雷码的特性，其每一位的编码都能由前一位编码得到，方法是做镜面对称，然后在最左侧上半部分补0，下半部分补1，可以通过数组简单模拟得到，缺点是数字大的时候就存不下来了
#include <cstdio>#include <cstring>#define num 20bool g[1 << num][num];int main(){g[0][0] = 0;g[1][0] = 1;for(int i = 1; i < num; i++){int k = 0;while(k < i){for(int j1 = 0; j1 < (1 << i); j1++){int j2 = (1 << (i + 1)) – 1 – j1;g[j2][k] = g[j1][k];}k++;}for(int j1 = 0; j1 < (1 << i); j1++){int j2 = (1 << (i + 1)) – 1 – j1;g[j1][k] = 0;g[j2][k] = 1;}k++;}int n;while(true){printf("Please input\nn = ");scanf("%d", &n);if(n == 0)break;printf("\nShow %d Gray Code :\n", n);for(int i = 0; i < (1 << n); i++){for(int j = n – 1; j >= 0; j–)printf("%d ", g[i][j]);printf("\n");}printf("\n");}}
老师出的题是输出无穷大位数的格雷码，显然不能使用任何数据结构，我们再回到格雷码，，观察其规律可以发现对于同一位数的第奇数组和偶数组序列，奇数组是都是先0后1，偶数组都是先1后0，通过这个规律和格雷码本身的性质我们可以直接计算出格雷码
#include <cstdio>#define judge (i % (1 << j)) < ((1 << j) >> 1)int main(){int bit;while(true){printf("Please input\nn = ");scanf("%d", &bit);if(bit == 0)break;printf("\nShow %d Gray Code :\n", bit);int n = (1 << bit);for(int i = 0; i < n; i++)for(int j = bit; j >= 1; j–)if((i / (1 << j)) & 1)printf("%d%c", judge ? 1 : 0, j == 1 ? '\n' : ' ');elseprintf("%d%c", judge ? 0 : 1, j == 1 ? '\n' : ' ');printf("\n");}}
放弃等于又一次可以选择的机会。
