神秘序列——格雷码序列

背景

昨日写题的时候，偶遇一道神奇的构造题，题目是这样的：
构造一个长度为\(2^n\)的序列\(p_0,p_1,…,p_{2^n−1}\)，使得相邻两项异或值之和最小。
这道题很容易就可以看出，如果要构造一个使得相邻两项异或值之和最小的序列，就要保证每个元素与相邻元素间在二进制下仅有一位的差距，而这样的序列显然会按照有效二进制位数升序排列，因此我很快就想到了这样一个贪心策略：首先将0放进排列尾部，然后每次从小到大尝试改变尾部的二进制位，如果得到的是新数就更新排列，这里的从小到大尝试改变尾部的二进制位指的是：当数已经存在于生成的答案序列中时，尝试改变更高一位的二进制位。举个例子：

1. 00 1(尝试改变0的倒数1位,得到1,成功)0 1 3(尝试改变1的倒数1位,得到0,但0在排列中,失败,尝试改变1的倒数第2位,得到3,成功)0 1 3 2(尝试改变3的倒数1位，得到2，成功)0 1 3 2 6(尝试改变2的倒数1位,得到3,失败,尝试改变2的倒数第2位,得到0,失败,尝试改变2的倒数第3位,得到6,成功)0 1 3 2 6 7 5 4

复制代码

这就是我所想到的贪心思路，它是正确的，代码如下：
[code]#include using namespace std;int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    int n;    cin >> n;    int m = 1  1) 这个公式，更重要的是理解了它通过改变编码顺序来降低系统不确定性的思维方式。希望这篇博客能让你在下次遇到类似构造题或工程问题时，能敏锐地联想到这个神奇的序列。</p>
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！