通常，人们习惯将所有 位二进制串按照字典序排列，例如所有 2 位二进制串按字典序从小到大排列为：00，01，10，11。 格雷码（Gray Code）是一种特殊的 位二进制串排列法，它要求相邻的两个二进制串间**恰好**有一位**不同**，特别地，第一个串与最后一个串也算作相邻。 所有 2 位二进制串按格雷码排列的一个例子为：00，01，11，10。 位格雷码不止一种，下面给出其中一种格雷码的生成算法： 1. 1 位格雷码由两个 1 位二进制串组成，顺序为：0，1。 2. 位格雷码的前 个二进制串，可以由依此算法生成的 位格雷码（总共 个 位二进制串）按**顺序**排列，再在每个串前加一个前缀 0 构成。 3. 位格雷码的后 个二进制串，可以由依此算法生成的 位格雷码（总共 个 位二进制串）按**逆序**排列，再在每个串前加一个前缀 1 构成。 综上， 位格雷码，由 位格雷码的 个二进制串按顺序排列再加前缀 0，和按逆序排列再加前缀 1 构成，共 个二进制串。另外，对于 位格雷码中的 个 二进制串，我们按上

问题分析 格雷码的生成规则： - 1 位格雷码：`0, 1` - n 位格雷码 = `0` + (n-1 位格雷码顺序) 和 `1` + (n-1 位格雷码逆序) 关键点 对于 n 位格雷码，编号 k 的二进制串： - 若 k < 2^(n-1)，则最高位为 0，剩余位是 (n-1) 位格雷码的第 k 个。 - 若 k ≥ 2^(n-1)，则最高位为 1，剩余位是 (n-1) 位格雷码的第 (2^n - 1 - k) 个（逆序部分）。 递归求解 1. 若 n = 1，直接返回 `"0"`（k=0）或 `"1"`（k=1）。 2. 计算 mid = 2^(n-1)。 3. 若 k < mid，返回 `"0" + gray(n-1, k)`。 4. 否则，返回 `"1" + gray(n-1, mid*2 - 1 - k)`。 代码实现 ```cpp #include <iostream> #include <string> using namespace std; string gray(int n, long long k) { if (n == 1) { return (k == 0) ? "0" : "1"; } long long mid = 1LL << (n - 1); // 2^(n-1) if (k < mid) { return "0" + gray(n - 1, k); } else { return "1" + gray(n - 1, mid * 2 - 1 - k); } } int main() { int n; long long k; cin >> n >> k; cout << gray(n, k) << endl; return 0; } ``` [2026-01-05 12:21:49 | AI问答 | 443点数解答]