名企笔试：腾讯2016招聘笔试（生成格雷码）

1、题目描述

 

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同， 则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。

 

给定一个整数n，请返回n位的格雷码，顺序为从0开始。

---

 

2、程序分析

 

1位的格雷码是 0 1

2位的格雷码是 00   01  11  10

3位的格雷码是 000 001  011  010  110  111  101  100

 

通过观察上面的数据，可以很快发现一些规律

（1） 2位格雷码的数量是1位的两倍，3位格雷码的数量是2位的两倍，那么照此推论，4位格雷码的数量应该是3位的两倍

（2） 2位格雷码是在1位格雷码的基础上发展来的，最高位分别加0 和 1 ，加0 生成了 00  01  加1 生成了 11 10 ，因此形成了两倍的数量差

（3） 去掉最高位后，格雷码呈现出对称的特点，比如3位格雷码，去掉最高位以后是 00  01  11 10  10 11 01 00 ，而00 01 11 10  不正是2位格雷码么，10  11 01 00 不正是2位格雷码倒过来么

---

 

3、示例代码

 

#coding=utf-8

def GrayCode(n):
    if n == 1:
        return ['0','1']
    else:
        last = GrayCode(n-1)
        length = len(last)
        graycode = [i for i in range(length*2)]
        for i in range(length):
            graycode[i] = "0" + last[i]
            graycode[length+i] = "1" + last[length-i-1]
        return graycode

print GrayCode(3)