9

我尝试在Python中生成灰色代码。此代码工作正常。问题是我在函数中初始化基本情况（n=1,[0,1]）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吗？

4

6 回答 6

22

生成格雷码比您想象的要容易。秘密在于第 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()
于 2016-08-03T13:46:05.750 回答
5 
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()
于 2016-08-03T09:05:45.917 回答
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()
于 2016-08-03T09:38:56.277 回答
2

那这个呢：

#! /usr/bin/python3

def hipow(n):
    ''' Return the highest power of 2 within n. '''
    exp = 0
    while 2**exp <= n:
        exp += 1
    return 2**(exp-1)

def code(n):
    ''' Return nth gray code. '''
    if n>0:
        return hipow(n) + code(2*hipow(n) - n - 1)
    return 0

# main:
for n in range(30):
    print(bin(code(n)))
于 2018-01-26T17:50:39.577 回答
0

这就是我的做法。状态数组需要为某个 n 值保存一些 n 位格雷码，从中生成下一个格雷码，状态数组将包含生成的格雷码，依此类推。尽管这里将状态初始化为 n 位“0”代码，但它也可以是任何其他 n 位格雷码。

时间复杂度：O(2^n)用于迭代列出每个 2^n 格雷码。

空间复杂度：O(n)用于具有 n 长度状态和幂数组。

def get_bit(line, bit_pos, state, powers):
    k = powers[bit_pos-1]
    if line % (k // 2):
        return str(state[bit_pos-1])
    else:
        bit = 1 - state[bit_pos - 1]
        state[bit_pos - 1] = bit
        if line % k == 0:
            state[bit_pos - 1] = 1 - bit
            bit = 1 - bit
        return str(bit)


def gray_codes(n):
    lines = 1 << n
    state = [0] * n
    powers = [1 << i for i in range(1, n + 1)]
    for line in range(lines):
        gray_code = ''
        for bit_pos in range(n, 0, -1):
            gray_code += get_bit(line, bit_pos, state, powers)
        print(gray_code)


n = int(input())
gray_codes(n)
于 2021-07-29T03:57:48.173 回答
0

显然这匹马已经被打死了，但我要补充一点，如果你不打算使用这个很酷且历史悠久的n ^ (n >> 1)技巧，递归可以更简洁地表述：

def gc(n):
  if n == 1:
    return ['0', '1']
  r = gc(n - 1)
  return ['0' + e for e in r] + ['1' + e for e in reversed(r)]

...以及迭代：

def gc(n):
  r = ['0', '1']
  for i in range(2, n + 1):
    r = ['0' + e for e in r] + ['1' + e for e in reversed(r)]
  return r
于 2021-07-29T04:45:22.027 回答