生成灰色代码。

Question

我试着用Python生成灰色代码。此代码工作正常。问题是，我正在初始化main函数中的基本大小写(main)，并将其传递给gray_code函数以计算其余部分。我想要生成函数本身内部的所有灰色代码，包括大小写。我该怎么做？

def gray_code(g,n):
    k=len(g)
    if n<=0:
        return

    else:
        for i in range (k-1,-1,-1):
            char='1'+g[i]
            g.append(char)
        for i in range (k-1,-1,-1):
            g[i]='0'+g[i]

        gray_code(g,n-1)

def main():
    n=int(raw_input())
    g=['0','1']
    gray_code(g,n-1)
    if n>=1:
        for i in range (len(g)):
            print g[i],

main()

这个算法的递推关系是T(n)=T(n-1)+n吗？

Answer 1

def gray_code(n):
    def gray_code_recurse (g,n):
        k=len(g)
        if n<=0:
            return

        else:
            for i in range (k-1,-1,-1):
                char='1'+g[i]
                g.append(char)
            for i in range (k-1,-1,-1):
                g[i]='0'+g[i]

            gray_code_recurse (g,n-1)

    g=['0','1']
    gray_code_recurse(g,n-1)
    return g

def main():
    n=int(raw_input())
    g = gray_code (n)

    if n>=1:
        for i in range (len(g)):
            print g[i],

main()

Answer 2

生成灰色代码比你想象的要容易。秘密在于N个灰色代码在N^(N>>1)的位中。

所以：

def main():
    n=int(raw_input())
    for i in range(0, 1<<n):
        gray=i^(i>>1)
        print "{0:0{1}b}".format(gray,n),

main()

Answer 3

如果您以迭代方式实现该函数(即使它是递归定义的)，这是相对容易的。这通常会更快地执行，因为它通常需要更少的函数调用。

def gray_code(n):
    if n < 1:
        g = []
    else:
        g = ['0', '1']
        n -= 1
        while n > 0:
            k = len(g)
            for i in range(k-1, -1, -1):
                char = '1' + g[i]
                g.append(char)
            for i in range(k-1, -1, -1):
                g[i] = '0' + g[i]
            n -= 1
    return g

def main():
    n = int(raw_input())
    g = gray_code(n)
    print ' '.join(g)

main()