当前位置：首页 > news >正文

神秘序列——格雷码序列

news 2026/5/11 22:12:37

背景

昨日写题的时候，偶遇一道神奇的构造题，题目是这样的：

构造一个长度为$2^n$的序列$p_0,p_1,…,p_{2^n−1}$，使得相邻两项异或值之和最小。

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

0
0 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

这就是我所想到的贪心思路，它是正确的，代码如下：

#include <bits/stdc++.h>
using namespace std;
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;int m = 1 << n;vector<int> ans;vector<bool> vis(m, false);int cur = 0;ans.push_back(cur);vis[cur] = true;while ((int)ans.size() < m) {for (int i = 0; i < n; i++) {int nxt = cur ^ (1 << i);if (!vis[nxt]) {cur = nxt;ans.push_back(cur);vis[cur] = true;break;}}}for (int i = 0; i < m; i++) {cout << ans[i] << " \n"[i == m - 1];}return 0;
}

转折

当我完成这道题后，还没来得及欣喜，就在看题解时发现了这道题原来另有说法，这道题目所要求构造的序列其实是一个非常经典的序列，该序列构造的规则是一个叫做格雷码的二进制数字系统，是由贝尔实验室的Frank Gray于20世纪40年代提出。它具有许多优点。

格雷码

基本定义

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）

性质

单位距离性

相邻格雷码之间的二进制仅有一位不同

循环性

任意连续$2^k$个格雷码其首尾仍符合单位距离性，即首位间二进制仅有一位不同

子立方体封闭性

在 n 维格雷码序列中，任意连续 $2^k$ 项（从 $2^k$ 的整数倍位置开始）恰好构成一个 k 维子立方体的格雷码。

构造

手动构造

$k$ 位的格雷码可以通过以下方法构造．我们从全 $0$ 格雷码开始，按照下面策略：

翻转最低位得到下一个格雷码，（例如 $000\to 001$）；
把最右边的 $1$ 的左边的位翻转得到下一个格雷码，（例如 $001\to 011$）；

交替按照上述策略生成 $2^{k-1}$ 次，可得到 $k$ 位的格雷码序列．

镜像构造

$k$ 位的格雷码可以从 $k-1$ 位的格雷码以上下镜射后加上新位的方式快速得到，如下图：

\[\begin{matrix} k=1\\ 0\\ 1\\\\\\\\\\\\\\ \end{matrix} \to \begin{matrix}\\ \color{Red}0\\\color{Red}1\\\color{Blue}1\\\color{Blue}0\\\\\\\\\\ \end{matrix} \to \begin{matrix} k=2\\ {\color{Red}0}0\\{\color{Red}0}1\\{\color{Blue}1}1\\{\color{Blue}1}0\\\\\\\\\\ \end{matrix} \to \begin{matrix}\\ \color{Red}00\\\color{Red}01\\\color{Red}11\\\color{Red}10\\\color{Blue}10\\\color{Blue}11\\\color{Blue}01\\\color{Blue}00 \end{matrix} \to \begin{matrix} k=3\\ {\color{Red}0}00\\{\color{Red}0}01\\{\color{Red}0}11\\{\color{Red}0}10\\{\color{Blue}1}10\\{\color{Blue}1}11\\{\color{Blue}1}01\\{\color{Blue}1}00 \end{matrix} \]

贪心构造

就是和我采用的策略一致，首先将0放进排列尾部，然后每次从小到大尝试改变尾部的二进制位，如果得到的是新数就更新排列

公式法

先使用手搓的方式，构造一些小的格雷码，然后观察第 $i$ 个格雷码与 $i$ 之间的关系，我们可以发现：第 $n$ 个格雷码的二进制第 $i$ 位为 $1$，仅当 $n$ 的二进制第 $i$ 位为 $1$，第 $i+1$ 位为 $0$ 或者第 $i$ 位为 $0$，第 $i+1$ 位为 $1$，于是，我们能想到使用异或运算来构造这一个格雷码，其公式如下：

\[Gray_i = i \bigoplus (i>>1) \]

优点

有些人可能会说，自然二进制编码就能直接使用，为什么要拐弯抹角地使用另外一种二进制编码系统呢，这是因为格雷码是一种具有反射特性和循环特性的单步自补码，其循环和单步特性消除了随机取数时出现重大错误的可能，其反射和自补特性使得对其进行求反操作也非常方便，所以，格雷码相较于自然二进制编码更加可靠，同时，它是一种错误最小化的编码方式，格雷码每一次变动时，仅改变一位二进制位，而自然二进制编码每一次变动，有可能因为进位使得多位二进制位发生改变，更不容易出错。

应用

格雷码在多个领域有着巧妙且实用的应用：

在三维曲面量测中，可采用格雷码投射的非接触式光学投影方法，实现对微型曲面的精准测量
在逻辑函数化简过程中，借助按格雷码规则排列的卡诺图，便能高效完成化简操作
在汽车制动系统的角度传感器中，该传感器需通过数字值指示机械位置，其编码盘与触点的设计遵循格雷码逻辑——编码盘中的暗区与逻辑1的信号源相连，亮区则无连接，触点会将其识别为逻辑0，为3位二进制编码的编码盘采用格雷码编码后，能让连续码字之间仅有一个数位发生变化，有效避免因器件制造精度限制，触点转到边界位置时出现的编码错误问题
格雷码可以用于解决汉诺塔问题：

设盘的数量为 $n$．我们从 $n$ 位全 $0$ 的格雷码 $G(0)$ 开始，依次移向下一个格雷码（$G(i)$ 移向 $G(i+1)$）．当前格雷码的二进制第 $i$ 位表示从小到大第 $i$ 个盘子．

由于每一次只有一个二进制位会改变，因此当第 $i$ 位改变时，我们移动第 $i$ 个盘子．在移动盘子的过程中，除了最小的盘子，其他任意一个盘子在移动的时侯，只能有一个放置选择．在移动第一个盘子的时侯，我们总是有两个放置选择．于是我们的策略如下：

如果 $n$ 是一个奇数，那么盘子的移动路径为 $$f\to t\to r\to f\to t\to r\to\cdots$$ ，其中 $f$ 是最开始的柱子，$t$ 是最终我们把所有盘子放到的柱子，$r$ 是中间的柱子．

如果 $n$ 是偶数：$f \to r \to t \to f \to r \to t \to \cdots$
格雷码也在遗传算法理论中得到应用，格雷码的单位距离性使其每次改变仅改变一位二进制位，因此如果在变异时使用可以避免变异后与变异前的差异过大导致收敛不稳定，同时父代交叉时单点交叉会破坏连续性，使子代与父代差异过大，而使用格雷码则可以避免子代父代不像亲生的。