深入解析格雷码生成算法：递归求解与代码实现

问题分析 格雷码的生成规则： - 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; } ``` ######[AI问答 | 443点数解答 | 2026-01-05 12:21:49]