遞迴 產生格雷碼

 用 遞迴 產生格雷碼

---

def generate_gray_code(n):

  if n==0:

    return ['0']

  if n==1:

    return ['0','1']

  smaller_gray_code = generate_gray_code(n-1)

  

  result = []

  result.extend(['0' + code for code in smaller_gray_code])

  result.extend(['1' + code for code in reversed(smaller_gray_code)])

  return result

n = 3

print(generate_gray_code(n))

Output:

['000', '001', '011', '010', '110', '111', '101', '100']

追蹤

假設我們需要產生 3 位元的格雷碼，過程如下：

1. 基礎情況（遞歸終止條件）：

   • 當 ( n = 1 ) 時，格雷碼為：["0", "1"]。

2. 進一步構造：

   • ( n = 2 )：從 ( n = 1 ) 的結果構造。
     • 在 ["0", "1"] 前加 0：["00", "01"]
     • 在 ["0", "1"]（反向排列）前加 1：["11", "10"]
     • 合併：["00", "01", "11", "10"]
   • ( n = 3 )：從 ( n = 2 ) 的結果構造。
     • 在 ["00", "01", "11", "10"] 前加 0：["000", "001", "011", "010"]
     • 在 ["00", "01", "11", "10"]（反向排列）前加 1：["110", "111", "101", "100"]
     • 合併：["000", "001", "011", "010", "110", "111", "101", "100"]

逐步結果：

位元數 ( n )	格雷碼生成結果
( n = 1 )	["0", "1"]
( n = 2 )	["00", "01", "11", "10"]
( n = 3 )	["000", "001", "011", "010", "110", "111", "101", "100"]