Python实现：打印n位格雷码字典序最小解及代码详解

以下是使用Python实现打印 `n` 位格雷码的字典序最小解的代码： ```python n = int(input()) # 生成格雷码 gray_codes = [] for i in range(2n): # 利用位运算生成格雷码 gray = i ^ (i >> 1) # 将格雷码转换为二进制字符串，并填充到 n 位 gray_str = bin(gray)[2:].zfill(n) gray_codes.append(gray_str) # 打印格雷码 for code in gray_codes: print(code) ``` 代码解释 1. 输入读取：首先读取用户输入的整数 `n`，表示格雷码的位数。 2. 生成格雷码： - 使用 `for` 循环遍历从 `0` 到 `2n - 1` 的所有整数。 - 对于每个整数 `i`，使用位运算 `i ^ (i >> 1)` 生成对应的格雷码。 - 将生成的格雷码转换为二进制字符串，并使用 `zfill(n)` 方法将其填充到 `n` 位。 3. 打印格雷码：遍历生成的格雷码列表，并逐行打印每个格雷码。 复杂度分析 - 时间复杂度：$O(2^n)$，其中 $n$ 是格雷码的位数。需要遍历从 `0` 到 `2n - 1` 的所有整数。 - 空间复杂度：$O(2^n)$，主要用于存储生成的格雷码列表。 ######[AI问答 | 361点数解答 | 2026-01-23 19:47:19]