NOIP 提高组初赛 · NOIP 2007 提高组初赛试题 第 27 题

（格雷码，Gray Code）格雷码是对十进制数的一种二进制编码。编码顺序与相应的十进制数的大小不一致。其特点是：对于两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。另外，最大数与最小数之间也仅有一个二进制位不同，以 $4$ 位二进制数为例，编码如下：

如果把每个二进制的位看作一个开关，则将一个数变为相邻的另一个数，只须改动一个开关。因此，格雷码广泛用于信号处理、数-模转换等领域。

下面程序的任务是：由键盘输入二进制数的位数 $n(n<16)$，再输入一个十进制数 $m(0\leq m<2n)$，然后输出对应于 $m$ 的格雷码（共 $n$ 位，用数组 gr[] 存放）。

为了将程序补充完整，你必须认真分析上表的规律，特别是对格雷码固定的某一位，从哪个十进制数起，由 $0$ 变为 $1$，或由 $1$ 变为 $0$。

#include <stdio.h>
main()
{
	int bound = 1, m, n, i, j, b, p, gr[15];
	printf( "input n,m\n" );
	scanf( "%d%d", &n, &m );
	for ( i = 1; i <= n; i++ )
		bound = ①;

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这道题考查格雷码的生成规律与循环控制。拿到题先别急着填，观察表格：第1位（最低位）每1个数翻转，第2位每2个数翻转，第3位每4个数翻转……第i位每2^(i-1)个数翻转一次。程序里的bound就是2的幂次，每轮循环bound翻倍。核心就是抓住“从0开始遍历，遇到后半段就取反”这个逻辑，然后对应到四个填空。

最容易栽跟头的地方是把bound的更新写错，比如写成bound++或者bound*2放在循环外，导致后面判断周期全乱。还有填j的初值时，有人会写成j=1，结果整个后半段的判断就偏了一位，最后输出的格雷码全错。另外，判断条件里那个减b/2的意图是找后半段，有人会漏掉括号或者写错运算符，导致逻辑反了。最后输出循环的边界，有人会写成i<=n，结果多输了一个高位0，虽然题目没明说，但规范写法应该是从高位往下输到第1位。

程序填空——格雷码生成

考点与概念

这道题的核心是格雷码的生成规律。格雷码是一种特殊的二进制编码，它的最大特点是：相邻两个数（包括首尾）对应的编码只有一位不同。这在硬件电路（比如旋转编码器、数模转换）里特别有用，因为状态切换时只变一位，能避免“毛刺”。

题目给了一张表，n=4时，十进制0到15对应的格雷码。我们得从表里看出规律，再套用到程序里。