简答题 偏难
#22098

day1-1 格雷码

day1-1 格雷码


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;string&gt; using namespace std; int main() {     int n;     unsigned long long k;     cin &gt;&gt; n &gt;&gt; k;          unsigned long long gray = k ^ (k &gt;&gt; 1);     string result(n, '0'); // 初始化为n个'0'的字符串          for (int i = 0; i &lt; n; ++i) {         // 检查第(n-1 - i)位是否为1,若为1则将对应位置设为'1'         if (gray &amp; (1ULL &lt;&lt; (n - 1 - i))) {             result[i] = '1';         }     }          cout &lt;&lt; result &lt;&lt; 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 的情况。