NOIP2007 提高组 复赛试题

全国信息学奥林匹克联赛（NOIP2007）复赛提高组题目一览（2007年11月17日 3小时完成）说明：1.文件名（程序名和输入输出文件名）必须使用小写2.C/C++中函数main()的返回值必须是int，程序正常结束时返回值必须是0。

3.全国统一评测时采用的机器参考配置为：CPU 2.0GHz，内存256M。

1.统计数字（count.pas/c/cpp）【问题描述】某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。

已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

【输入】输入文件count.in包含n+1行；第一行是整数n，表示自然数的个数；第2~n+1每行一个自然数。

【输出】输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。

每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

【输入输出样例】【限制】40%的数据满足：1<=n<=100080%的数据满足：1<=n<=50000100%的数据满足：1<=n<=200000，每个数均不超过1500 000 000（1.5*109）2.字符串的展开（expand.pas/c/cpp）【问题描述】在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或者“4-8”的字串，我们就把它当作一种简写，输出时，用连续递增的字母H 或数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。

在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。

具体约定如下：(1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧同为小写字母或同为数字，且按照ASCII码的顺序，减号右边的字符严格大于左边的字符。

第十七届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal语言两小时完成）●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分。

共计30分。

每题有且仅有一个正确选项。

）1．在二进制下，1100011 +（）= 1110000。

A．1011 B．1101 C．1010 D．11112．字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。

A．66 B．5A C．50 D．视具体的计算机而定3．右图是一棵二叉树，它的先序遍历是（）。

A．ABDEFC B．DBEFAC C．DFEBCA D．ABCDEF4．寄存器是（）的重要组成部分。

A．硬盘B．高速缓存C．内存D．中央处理器（CPU）5．广度优先搜索时，需要用到的数据结构是（）。

A．链表B．队列C．栈D．散列表6．在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）。

A．程序运行时理论上所占的内存空间B．程序运行时理论上所占的数组空间C．程序运行时理论上所占的硬盘空间D．程序源文件理论上所占的硬盘空间7．应用快速排序的分治思想，可以实现一个求第K大数的程序。

假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。

A．O(n2)B．O(n log n)C．O(n) D．O(1)8．为解决Web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。

A．微软 B．美国计算机协会（ACM） C．联台国教科文组织D．万维网联盟（W3C）9．体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。

每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。

这种站队的方法类似于（）算法。

A．快速排序B．插入排序C．冒泡排序D．归并排序10．1956年（）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain)，以表彰他们对半导体的研究和晶体管效应的发现。

NOI’ 95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（高中组）（上机编程，完成时间：210 分钟）<1>编码问题：设有一个数组A:ARRAY[0..N-1] OF INTEGER；数组中存放的元素为0～N-1 之间的整数，且A[i]≠ A[j]（当i≠ j时）。

例如： N=6 时，有：此时，数组 A 的编码定义如下：A[0] 的编码为0；A[i] 的编码为：在A[0] ，A[1]∴上面数组 A 的编码为：A= （ 4，3， 0， 5，1， 2），， A[i-1] 中比 A[i] 的值小的个数（B= （0， 0，0，3，1， 2）i=1 ，2，， N-1 ）程序要求解决以下问题：①给出数组 A 后，求出其编码。

②给出数组 A 的编码后，求出 A 中的原数据。

<2> 灯的排列问题：设在一排上有 N 个格子（ N≤ 20），若在格子中放置有不同颜色的灯，每种灯的个数记为 N 1， N2， N k（ k 表示不同颜色灯的个数）。

放灯时要遵守下列规则：①同一种颜色的灯不能分开；②不同颜色的灯之间至少要有一个空位置。

例如： N=8 （格子数）R=2 （红灯数）B=3 （蓝灯数）放置的方法有：R-B 顺序R R B B BR R B B BR R B B BR R B B BR R B B BR R B B BB-R顺序B B B BBBBBBBBBBBBBBR RRRBRRRRRRRR放置的总数为12 种。

数据输入的方式为：NP1（颜色，为一个字母）P2N1（灯的数量）N2Q（结束标记， Q 本身不是灯的颜色）程序要求：求出一种顺序的排列方案及排列总数。

<3> 设有一个四层的积木块，1～ 4 层积木块的数量依次为：5， 6，7， 8如下图所示放置：815851691423414326其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。

全国信息学奥林匹克联赛（NOIP2007）复赛普及组题目一览(2007年11月17日3小时完成)说明：1. 文件名（程序名和输入输出文件名）必须使用小写2. C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3. 全国统一评测时采用的机器参考配置为：CPU 2.0GHz，内存256M。

1．奖学金(scholar.pas/c/cpp)【问题描述】某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。

期末，每个学生都有3门课的成绩：语文、数学、英语。

先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前5名学生的学号和总分。

注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。

例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是：7 2795 279这两行数据的含义是：总分最高的两个同学的学号依次是7号、5号。

这两名同学的总分都是279（总分等于输入的语文、数学、英语三科成绩之和），但学号为7的学生语文成绩更高一些。

如果你的前两名的输出数据是：5 2797 279则按输出错误处理，不能得分。

【输入】输入文件scholar.in包含n+1行：第1行为一个正整数n，表示该校参加评选的学生人数。

第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。

第j行的3个数字依次表示学号为j-1的学生的语文、数学、英语的成绩。

每个学生的学号按照输入顺序编号为1~n （恰好是输入数据的行号减1）。

所给的数据都是正确的，不必检验。

【输出】输出文件scholar.out共有5行，每行是两个用空格隔开的正整数, 依次表示前5名学生的学号和总分。

Day1铺地毯【问题描述】为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。

一共有n 张地毯，编号从1 到n。

现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。

注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

【输入】输入文件名为 carpet.in。

输入共 n+2 行。

第一行，一个整数 n，表示总共有n 张地毯。

接下来的 n 行中，第i+1 行表示编号i 的地毯的信息，包含四个正整数a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x轴和y 轴方向的长度。

第 n+2 行包含两个正整数x 和y，表示所求的地面的点的坐标（x，y）。

【输出】输出文件名为 carpet.out。

输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。

【输入输出样例 1】【输入输出样例说明】如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点（2，2）的最上面一张地毯是3 号地毯。

【输入输出样例 2】【输入输出样例说明】如上图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，点（4，5）没有被地毯覆盖，所以输出-1。

【数据范围】对于 30%的数据，有n≤2；对于 50%的数据，0≤a, b, g, k≤100；对于 100%的数据，有0≤n≤10,000，0≤a, b, g, k≤100,000。

【一句话题意】给定n个按顺序覆盖的矩形，求某个点最上方的矩形编号。

【考察知识点】枚举【思路】好吧我承认看到图片的一瞬间想到过二维树状数组和二维线段树。

置答案ans=-1，按顺序枚举所有矩形，如果点在矩形内则更新ans。

注意题中给出的不是对角坐标，实际上是(a,b)与(a+g,b+k)。

第十三届全国青少年信息学奥林匹克联赛初赛试题（提高组Pascal 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共 10 题，每题 1.5 分，共计 15 分。

每题有且仅有一个正确答案.）。

1. 在以下各项中。

（）不是 CPU 的组成部分。

A. 控制器B. 运算器C. 寄存器D. 主板E. 算术逻辑单元(ALU)2. 在关系数据库中, 存放在数据库中的数据的逻辑结构以( )为主。

A. 二叉树B. 多叉树C. 哈希表D. B+树E. 二维表3.在下列各项中，只有（）不是计算机存储容量的常用单位。

A. ByteB. KBC. MBD. UBE. TB4．ASCII码的含义是（）。

A. 二—十进制转换码B. 美国信息交换标准代码C. 数字的二进制数码D. 计算机可处理字符的唯一编码E. 常用字符的二进制编码5．在 Pascal 语言中，表达式 (23 or 2 xor 5)的值是（）A. 18B.1 C.23 D.32 E.246．在 Pascal 语言中，判断整数a 等于 0 或b等于 0或c等于0 的正确的条件表达式是（）A. not ((a<>0) or (b<>0) or (c<>0))B. not ((a<>0) and (b<>0) and (c<>0))C. not ((a=0) and (b=0)) or (c=0)D.(a=0) and (b=0) and (c=0)E. not ((a=0) or (b=0) or (c=0))7. 地面上有标号为A、B、C的3根细柱, 在A柱上放有10个直径相同中间有孔的圆盘, 从上到下次依次编号为1, 2, 3, ……，将A柱上的部分盘子经过B柱移入C柱, 也可以在B 柱上暂存。

如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。

第一题：count 统计数字输入一个数n(n<=200000)和n个自然数（每个数都不超过1.5*10^9），请统计出这些自然数各自出现的次数，按顺序从小到大输出。

输入数据保证不相同的数不超过10000个。

样例输入：8242451002100样例输出：2 34 25 1100 2第一题program scholar(input,output);var a,b,c,id,s:array[1..300]of integer;v:array[0..0]of boolean;i,j,k,t,m,n,x,y:integer;beginassign(input,'scholar.in');assign(output,'scholar.out');reset(input);rewrite(output);readln(n);for i:=1 to n dobegin readln(a[i],b[i],c[i]);id[i]:=i;end;for i:=1 to n dos[i]:=a[i]+b[i]+c[i];for i:=1 to n-1 dofor j:=i to n dobeginif s[i]<s[j]thenbegint:=s[i];s[i]:=s[j];s[j]:=t;t:=a[i];a[i]:=a[j];a[j]:=t;t:=b[i];b[i]:=b[j];b[j]:=t;t:=c[i];c[i]:=c[j];c[j]:=t;t:=id[i];id[i]:=id[j];id[j]:=t;end;if s[i]=s[j]thenif a[i]<a[j] thenbegint:=s[i];s[i]:=s[j];s[j]:=t;t:=a[i];a[i]:=a[j];a[j]:=t;t:=b[i];b[i]:=b[j];b[j]:=t;t:=c[i];c[i]:=c[j];c[j]:=t;t:=id[i];id[i]:=id[j];id[j]:=t;endend;for i:=1 to 5 dowriteln(id[i],' ',a[i]+b[i]+c[i]);close(input);close(output);end.第二题：expand 字符串的展开我们可以用减号对连续字母或数字进行缩写，于是字符串a-dha3-68就可以展开为abcdha34568。

NOIP2007提高组题解1.count一切直接nlogn的算法，在常数不大的时候都能过。

我采用的是接近O(n+klogk)的算法，这里k=10000，即不同的数的个数：先把数存放到Hash表中，读完以后再取出Hash表内的数据排序。

Hash函数采用mod 99991的方式。

发生冲突采用类似开散列的解决办法：如果Hash(n)的位置已经被占用，但关键字不匹配，那接下来考虑Hash(n+1)的位置，直到找到一个空位，或者关键字相同。

提一句：直至今年，C的stdlib.h库中qsort函数仍然可以使用。

2.expand这题考查的是字符串处理的技巧。

注意一定要满足以下全部条件：非头非尾，两边均字母或均数字，左边字符比右边字符小。

这时候才按要求进行填充工作。

另：C/C++选手在熟练掌握for语句的情况下可以把顺序、逆序、大小写放在同一个过程里实现，降低编程复杂度。

3.game注意到每一行都是独立的一个结构，因此可以把每一行的答案全部加起来就是最后答案。

对于每一行，有状态转移方程：f(i,j) = 2*max(a(i)+f(i+1,j),a(j)+f(i,j-1))，边界f(i,i)=2*a(i)，其中f(i,j)表示从i到j这一子段单独操作可以达到的最大权值。

最后答案就把每一行的f(0,m-1)加起来即可。

这里可以算得答案不超过30位10进制数，所以高精度的digit数组开到30足够了。

乘法也不用写，用两次加法即可。

4.core以下是我在比赛时的做法：可以证明的是，如果图中存在多条路径，则在任何一条直径上都存在一条core（反证法，用到直径的距离最大性）。

因此只需讨论一条直径上的core的情况即可。

接着，如果一条路径包括了一条子路径的所有边，那么子路径的解不会比父路径更优。

这一点后面将用到。

下面是算法：先寻找一条直径：任取一点u'，遍历得到到它的最远点u，再对u寻找一个到它的最远点v，则路径u-v一定是一条直径（想想为什么），在刚才遍历u-v的时候记录遍历到每一个点的时候的前继，那么从v出发一直寻找前继到u，就能记录下这一条直径。

全国信息学奥林匹克分区联赛（NOIP）复赛提高组试题第一届全国信息学奥林匹克分区联赛（NOIP1995）复赛试题（提高组竞赛用时：3.5小时）1、编码问题设有一个数组A:ARRAY[0..N-1]OFINTEGER；数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。

例如：N=6时，有：A=（4，3，0，5，1，2）此时，数组A的编码定义如下：A[0]的编码为0；A[i]的编码为：在A[0]，A[1]，…，A[i-1]中比A[i]的值小的个数（i=1，2，…，N-1）∴上面数组A的编码为：B=（0，0，0，3，1，2）程序要求解决以下问题：①给出数组A后，求出其编码。

②给出数组A的编码后，求出A中的原数据。

2、灯的排列问题设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……N k（k表示不同颜色灯的个数）。

放灯时要遵守下列规则：①同一种颜色的灯不能分开；②不同颜色的灯之间至少要有一个空位置。

例如：N=8（格子数）；R=2（红灯数）；B=3（蓝灯数），放置的方法有：R-B顺序B-R顺序放置的方法总数为12种。

数据输入的方式为：NP1（颜色，为一个字母）N1（灯的数量）P2 N2……Q（结束标记，Q本身不是灯的颜色）程序要求：求出一种顺序的放置（排列）方案及放置（排列）方案总数。

3、积木块上的数字设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，8，如下图所示放置：其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。

计算的方法是：第三层的某个数据A是由第四层相邻的两个数据B，C经过某种计算后产生的：计算所用到的计算符为：+，-，⨯，且无优先级之分（自左向右计算），运算符最多为2个。

如：3+4⨯5=35 5⨯4+3=23可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的：A=B⨯C+B也就是：8=2⨯3+2，15=3⨯4+3，……14=2⨯6+2程序要求：给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。

NOIP2007提高组复赛试题解题报告我小菜也来发题解了，不过现在都已经过去那么长时间再来发题解未免太迟，但是写题解可以让自己对题目始终抱有需要深刻理解的态度，所以我还是坚持写题解。

NOIP2007的题目并不十分难，我们浙江省有1个满分，不知道2008年题目会怎么样。

首先我这里题目就省略了，因为这年头题目网上满天飞，所以直接开始写题解。

一、统计数字。

这题其实是道送分题，而且还十分弱智，不知道是考排序还是数据结构，这题解法有很多，可以快排，BST，HASH。

这些方法都很容易AC，而且据说写裸BST（不严格平衡的BST）都能满分，可见这题简单的程度。

记得当时我是用先读入数据，然后一趟快排，最后去重输出，简单吧，这题我就不费话，直接帖上程序：[参考程序]program count(input,output);constmaxn=200000;maxn1=10000;typearr=array[1..maxn] of longint;nums=recordnumb,time:longint;end;varnum:arr;ans:array[1..maxn1] of nums;i,j,k,n:longint;f1,f2:text;procedure ranqsort(var num:arr; low,high:longint);vari,j,k,tmp,x:longint;beginwhile low<high do begini:=low-1;k:=random(high-low+1)+low;tmp:=num[k]; num[k]:=num[high]; num[high]:=tmp;x:=num[high];for j:=low to high-1 do if num[j]<=x thenbegininc(i);tmp:=num[i]; num[i]:=num[j]; num[j]:=tmp;end;tmp:=num[i+1]; num[i+1]:=num[high]; num[high]:=tmp; ranqsort(num,low,i);low:=i+2;end;end;beginfillchar(num,sizeof(num),0);fillchar(ans,sizeof(ans),0);assign(f1,'count.in'); reset(f1);assign(f2,'count.out'); rewrite(f2);readln(f1,n);for i:=1 to n do readln(f1,num[i]);close(f1);randomize;ranqsort(num,1,n);j:=1; ans[1].numb:=num[1]; ans[1].time:=1;for i:=2 to n do if num[i]=ans[j].numb then inc(ans[j].time) else begin inc(j); ans[j].numb:=num[i]; ans[j].time:=1; end; for i:=1 to j do writeln(f2,ans[i].numb,' ',ans[i].time);close(f2);end.二、字符串的展开这道题是全卷思路最简单的一道题，简单模拟即可，但是这一点恰恰是这道题目的难点，因为字符串处理的题目对编程熟练程度要求比较高，而且这题还要考虑好多种因素，比如说有可能字符串开头出现了“-”号，结果不少人当时就因此有一个点WA的WA，崩溃的崩溃。

第十届全国信息学奥林匹克分区联赛（NOIP2004）复赛试题（提高组竞赛用时：3小时）1、津津的储蓄计划(Save.pas／dpr／c／cpp)【问题描述】津津的零花钱一直都是自己管理。

每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。

因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

例如11月初津津手中还有83元，妈妈给了津津300元。

津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。

到了11月月末，津津手中会剩下3元钱。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。

有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。

如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。

如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。

【输入文件】输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。

【输出文件】输出文件save.out包括一行，这一行只包含一个整数。

如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。

【样例输入1】29023028020030017034050908020060【样例输出1】-7【样例输入2】29023028020030017033050908020060【样例输出2】1580【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。

NOIP2007 初赛试题（提高组C)2008-08-03 15:09分类：默认分类字号：大中小信息学奥赛试题NOIP2007 初赛试题（提高组C）© 中国计算机学会20071第十三届全国青少年信息学奥林匹克联赛初赛试题（提高组C 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10 题，每题1.5 分，共计15 分。

每题有且仅有一个正确答案）。

1. 在以下各项中，（）不是CPU 的组成部分。

A. 控制器B. 运算器C. 寄存器D. 主板E. 算术逻辑单元(ALU)2．在关系数据库中，存放在数据库中的数据的逻辑结构以（）为主。

A. 二叉树B. 多叉树C.哈希表D. B+树E.二维表3．在下列各项中，只有（）不是计算机存储容量的常用单位。

A. ByteB. KBC.MBD.UBE.TB4．ASCII 码的含义是（）。

A. 二—十进制转换码B. 美国信息交换标准代码C. 数字的二进制编码D. 计算机可处理字符的唯一编码E. 常用字符的二进制编码5．在C 语言中，表达式23|2^5 的值是（）A. 23B. 1C.18D.32E.246．在C 语言中，判断a 等于0 或b 等于0 或c 等于0 的正确的条件表达式是（）A. !((a!=0)||(b!=0)||(c!=0))B. !((a!=0)&&(b!=0)&&(c!=0))C. !(a==0&&b==0)||(c!=0)D. (a=0)&&(b=0)&&(c=0)E. !((a=0)||(b=0)||(c=0))7．地面上有标号为A、B、C 的3 根细柱，在A 柱上放有10 个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3，……，将A 柱上的部分盘子经过B 柱移入C 柱，也可以在B 柱上暂存。

如果B 柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。

NOIP2007提高组第一题格雷码 (Gray Code)Gray Code是一种二进制编码，编码顺序与相应的十进制数的大小不一致。

其特点是，对于两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。

另外，最大数与最小数间也仅有一个二进制位不同，以4位二进制数为例，编码如下：十进制数格雷码十进制数格雷码0 0000 8 11001 0001 9 11012 0011 10 11113 0010 11 11104 0110 12 10105 0111 13 10116 0101 14 10017 0100 15 1000如果把每个二进制的位看做一个开关，则将一个数变为相邻的另一个数，只须改动一个开关。

因此，格雷码广泛用于信号处理、数-模转换等领域。

下面程序的任务是：由键盘输入二进制的位数n(n<16)，再输入一个十进制数m(0≤m<2n)，然后输出对应于m的格雷码(共n位，用数组gr[ ]存放)program s501;varbound，m，n，i，j，b，p:integer;gr:array[0..14]of integer;beginbound:=1; writeln('input n，m'); readln(n，m);for i:=1 to n do bound:=[ ① ];if (m<0)or(m>=bound)then beginwriteln('Data error!');[ ② ];end;b:=1;for i:=1 to n dobeginp:=0; b:=b*2;for[ ③ ] to m doif ([ ④ ]) then p:=1-p;gr:=p;end;for i:=n[ ⑤ ] do write(gr); writeln;end.NOIP2007提高组第二题连续邮资问题某国发行了n种不同面值的邮票，并规定每封信上最多允许贴m张邮票。