简答题
偏难
#22098
day1-1 格雷码
day1-1 格雷码


答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
unsigned long long k;
cin >> n >> k;
unsigned long long gray = k ^ (k >> 1);
string result(n, '0'); // 初始化为n个'0'的字符串
for (int i = 0; i < n; ++i) {
// 检查第(n-1 - i)位是否为1,若为1则将对应位置设为'1'
if (gray & (1ULL << (n - 1 - i))) {
result[i] = '1';
}
}
cout << result << endl;
return 0;
}</pre><p><br/></p>
解析
方法思路
1、格雷码性质:第 k 个格雷码的二进制值可以通过 k ^ (k >> 1) 计算得到,其中^表示异或运算,>>表示右移运算。
2、转换为二进制字符串:将计算得到的格雷码值转换为 n 位的二进制字符串,不足 n 位时在前面补零。
代码解释
1、输入处理:读取输入的 n(格雷码的位数)和 k(编号)。
2、计算格雷码值:利用性质 gray = k ^ (k >> 1) 计算第 k 个格雷码的数值。
3、生成二进制字符串:初始化一个长度为 n 的字符串,所有字符初始为 '0'。通过位运算逐位检查格雷码值的每一位,若某一位为 1,则将字符串对应位置的字符设为 '1'。
4、输出结果:输出生成的 n 位二进制字符串。
这种方法的时间复杂度为 O (n),空间复杂度为 O (n),能够高效处理 n 最大为 64 的情况。