生成格雷码。
Generating gray codes.
我尝试在 Python 中生成格雷码。此代码工作正常。问题是我在 main
函数中初始化基本情况 (n=1,[0,1]
) 并将其传递给 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
吗?
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()
如果你迭代地实现函数(即使它是递归定义的),它相对容易做到。这通常会执行得更快,因为它通常需要更少的函数调用。
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()
生成格雷码比您想象的要容易。秘诀在于第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()
这个怎么样:
#! /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)))
这是我的做法。状态数组需要为某个 n 值保存一些 n 位格雷码,下一个格雷码将从中生成,状态数组将包含生成的格雷码,依此类推。尽管这里的状态被初始化为 n 位“0”代码,但它也可以是任何其他 n 位格雷码。
时间复杂度:O(2^n) 用于迭代列出每个 2^n 格雷码。
Space 复杂度: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)
显然这匹马已经被打死了,但我要补充一点,如果你不打算使用这个很酷且历史悠久的 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
我尝试在 Python 中生成格雷码。此代码工作正常。问题是我在 main
函数中初始化基本情况 (n=1,[0,1]
) 并将其传递给 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
吗?
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()
如果你迭代地实现函数(即使它是递归定义的),它相对容易做到。这通常会执行得更快,因为它通常需要更少的函数调用。
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()
生成格雷码比您想象的要容易。秘诀在于第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()
这个怎么样:
#! /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)))
这是我的做法。状态数组需要为某个 n 值保存一些 n 位格雷码,下一个格雷码将从中生成,状态数组将包含生成的格雷码,依此类推。尽管这里的状态被初始化为 n 位“0”代码,但它也可以是任何其他 n 位格雷码。
时间复杂度:O(2^n) 用于迭代列出每个 2^n 格雷码。
Space 复杂度: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)
显然这匹马已经被打死了,但我要补充一点,如果你不打算使用这个很酷且历史悠久的 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