编程题笔记-格雷码生成

什么是格雷码?

格雷码(Gray Code)是一个数列集合，每个数使用二进位来表示，假设使用n位元来表示每个数字，任两个相邻数之间只有一个位元值不同

• 比如3元格雷码 :
  000 001 011 010 110 111 101 100

那我们怎么生成格雷码呢?

生成格雷码思路一

以二进制为0值的格雷码为第零项，第一项改变最右边的位元，第二项改变右起第一个为1的位元的左边位元，第三、四项方法同第一、二项，如此反复，即可排列出n个位元的格雷码。

步骤: 以生成3位元的格雷码为例，初始值: 000

• 第一步：改变最右边的位元值：001
• 第二步：改变右起第一个为1的位元的左边位元：011
• 第三步：改变最右边的位元值：010
• 第四步：改变右起第一个为1的位元的左边位元：110
• 第五步：改变最右边的位元值：111
• 第六步：改变右起第一个为1的位元的左边位元：101
• 第七步：改变最右边的位元值：100

生成格雷码思路二

从格雷码的排列得出这样的规律: 除了最高位（左边第一位），格雷码的位元完全上下对称（看下面列表）。比如第一个格雷码与最后一个格雷码对称（除了第一位），第二个格雷码与倒数第二个对称，以此类推。

• 维基百科：n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到

JavaScript代码

//利用格雷码n-1位后对称性生成 n 位格雷码
function getGray(n) {
    var grayArr = [];
    if(n < 1 ) return false;
    if(n == 1) {
        grayArr.push("0");
        grayArr.push("1");
        return grayArr;
    }
    
    var gray = getGray(n - 1);
    var len = n - 1;
    for(var i = 0; i < len; i++) {
        grayArr.push("0" + gray[i]);
    }
    for(var i = len - 1; i >= 0; i--) {
        grayArr.push("1" + gray[i]);
    } 

    return grayArr; 
}

参考资料: 格雷码- 维基百科，自由的百科全书