Gray码问题

算法课碰到的问题,尝试用一次Python写写看了,不过时间复杂度还是挺高的O(n*2^n)。

Gray码是一个长度为2^n的序列。序列中无相同元素,每个元素都是长度为n位的(0,1)串,相邻元素恰好只有一位不同,用分治策略设计一个算法对任意的n位构造相应的Gray码。

1
2
3
4
5
6
7
8
9
10
11
class GrayCode:
def getGray(self, n):
return [bin((i>>1)^i).replace("0b","").rjust(n,"0") for i in range(2**n)]

# bin() 返回一个整数 int 或者长整数 long int 的二进制表示。
# replace() 方法把字符串中的 old(旧字符串) 替换成 new(新字符串)
# rjust() 返回一个原字符串右对齐

t = GrayCode()
i = input()
print (t.getGray(int(i)))

主要核心就一行return那里,利用了二进制两两xor得出格雷码的特性。