算法竞赛备考冲刺必刷题（C++） | AcWing 1152 格雷码
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AcWing：1152. 格雷码 - AcWing题库
【题目描述】
通常，人们习惯将所有 n n n 位二进制串按照字典序排列，例如所有 2 2 2 位二进制串按字典序从小到大排列为： 00 , 01 , 10 , 11 00,01,10,11 00,01,10,11。
格雷码（Gray Code）是一种特殊的 n n n 位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同，特别地，第一个串与最后一个串也算作相邻。
所有 2 2 2 位二进制串按格雷码排列的一个例子为： 00 , 01 , 10 , 11 00,01,10,11 00,01,10,11。
n n n 位格雷码不止一种，下面给出其中一种格雷码的生成算法：
- 1 1 1 位格雷码由两个 1 1 1 位二进制串组成，顺序为： 0 , 1 0,1 0,1。
- n + 1 n+1 n+1 位格雷码的前 2 n 2^n 2n 个二进制串，可以由依此算法生成的 n n n 位格雷码（总共 2 n 2^n 2n 个 n n n 位二进制串）按顺序排列，再在每个串前加一个前缀 0 0 0 构成。
- n + 1 n+1 n+1 位格雷码的后 2 n 2^n 2n 个二进制串，可以由依此算法生成的 n n n 位格雷码（总共 2 n 2^n 2n 个 n n n 位二进制串）按逆序排列，再在每个串前加一个前缀 1 1 1 构成。
综上， n + 1 n+1 n+1 位格雷码，由 n n n 位格雷码的 2 n 2^n 2n 个二进制串按顺序排列再加前缀 0 0 0，和按逆序排列再加前缀 1 1 1 构成，共 2 n + 1 2^{n+1} 2n+1 个二进制串。
另外，对于 n n n 位格雷码中的 2 n 2^n 2n 个二进制串，我们按上述算法得到的排列顺序将它们从 0 ∼ 2 n − 1 0\sim 2^n-1 0∼2n−1 编号。
按该算法， 2 2 2 位格雷码可以这样推出：
- 已知 1 1 1 位格雷码为 0 , 1 0,1 0,1。
- 前两个格雷码为 00 , 01 00,01 00,01。后两个格雷码为 11 , 10 11,10 11,10。合并得到 00 , 01 , 11 , 10 00,01,11,10 00,01,11,10，编号依次为 0 ∼ 3 0\sim 3 0∼3 。
同理， 3 3 3 位格雷码可以这样推出：
- 已知 2 2 2 位格雷码为： 00 , 01 , 11 , 10 00,01,11,10 00,01,11,10。
- 前四个格雷码为： 000 , 001 , 011 , 010 000,001,011,010 000,001,011,010。后四个格雷码为： 110 , 111 , 101 , 100 110,111,101,100 110,111,101,100。合并得到： 000 , 001 , 011 , 010 , 110 , 111 , 101 , 100 000,001,011,010,110,111,101,100 000,001,011,010,110,111,101,100，编号依次为 0 ∼ 7 0\sim 7 0∼7。
现在给出 n , k n,k n,k，请你求出按上述算法生成的 n n n 位格雷码中的 k k k 号二进制串。
【输入】
仅一行，包含两个整数 n n n 和 k k k。
【输出】
仅一行，一个 n n n 位二进制串表示答案。
【输入样例】
2 3 【输出样例】
10 【算法标签】
《AcWing 1152 格雷码》 #递归# #位运算# #格雷码#
【代码详解】
#!代码技巧#：将数字转为unsigned long long，2ull
#include<bits/stdc++.h>usingnamespace std;// 使用unsigned long long，因为k可能很大（最大2^64-1）typedefunsignedlonglong ULL;// 递归函数：查找n位格雷码中序号为k的格雷码// 参数：n - 格雷码的位数，k - 要查找的格雷码序号（从0开始）// 返回值：序号为k的n位格雷码的二进制字符串 string find(int n, ULL k){// 递归基：当n=0时，返回空字符串if(n ==0){return"";}// 计算n位格雷码总数的一半// 对于n位格雷码，总共有2^n个，一半是2^(n-1)个 ULL len =pow(2ull, n -1);// 情况1：k在前半部分（0到len-1）// 此时格雷码的第一位是'0'if(k < len){// 递归求解n-1位格雷码，序号为k// 在前面添加'0'return"0"+find(n -1, k);}// 情况2：k在后半部分（len到2^n-1）// 此时格雷码的第一位是'1'else{// 递归求解n-1位格雷码，序号需要对称映射// 映射规则：后半部分的序号k映射为前半部分的序号(len*2-1-k)// 在前面添加'1'return"1"+find(n -1, len *2-1- k);}}intmain(){int n;// 格雷码的位数 ULL k;// 要查找的格雷码序号（从0开始） cin >> n >> k;// 输入位数n和序号k// 输出序号为k的n位格雷码 cout <<find(n, k)<< endl;return0;}【运行结果】
2 3 10 
