深入探究：n 位格雷码中编号 k 二进制串的求解算法与实现

题目要求根据给定的递归算法，求出 n 位格雷码中编号为 k 的二进制串。 格雷码的递归构造规则： 1. 1 位格雷码：0, 1（编号 0, 1）。 2. n+1 位格雷码： - 前 2^n 个：在 n 位格雷码的每个串前加 0（保持顺序）。 - 后 2^n 个：在 n 位格雷码的每个串前加 1（逆序）。 关键观察 设 n 位格雷码编号为 0 到 2^n - 1。 对于 n+1 位格雷码： - 编号 0 到 2^n - 1：第一位是 0，后面 n 位是 n 位格雷码的正序第 k 个。 - 编号 2^n 到 2^(n+1) - 1：第一位是 1，后面 n 位是 n 位格雷码的逆序第 (k - 2^n) 个。 逆序第 m 个（m = k - 2^n）在正序中的编号是 2^n - 1 - m。 推导公式 设 f(n, k) 表示 n 位格雷码中编号 k 对应的二进制串（长度为 n 的字符串）。 - 若 k < 2^(n-1)：第一位是 '0'，后面 n-1 位是 f(n-1, k)。 - 若 k >= 2^(n-1)：第一位是 '1'，后面 n-1 位是 f(n-1, 2^(n-1) - 1 - (k - 2^(n-1))) = f(n-1, 2^n - 1 - k)。 即： ``` if k < 2^(n-1): return '0' + f(n-1, k) else: return '1' + f(n-1, 2^n - 1 - k) ``` 边界：n=1 时，若 k=0 返回 "0"，k=1 返回 "1"。 直接位运算方法 格雷码的另一种公式： 格雷码 g(k) = k XOR (k >> 1)。 对于 n 位，取 g(k) 的二进制表示（n 位，高位补零）。 验证 n=3, k=5： k=5 (101b) g = 5 XOR 2 = 7 (111b) 二进制 111 对应格雷码 111，与递归构造一致。 数据范围 n ≤ 64，k ≤ 2^63 - 1，用 64 位无符号整数存储。 实现 使用公式 g = k XOR (k >> 1)，将结果转为 n 位二进制字符串。 代码 ```python def gray_code(n, k): # 计算格雷码编号 g = k ^ (k >> 1) # 转为 n 位二进制字符串 return format(g, f'0{n}b') # 示例 n = 3 k = 5 print(gray_code(n, k)) # 输出 111 ``` ######[AI问答 | 726点数解答 | 2026-01-13 12:31:37]