Noip初赛复习指南、题目分类解析(6)

检查。

只要程序段：

For I := 1 to 10 do a[I] := 0; For I := 1 to 10 do read(x[I]); J := 0; f := 0; k := 0; b := 0; If x[1] = '-' then begin

____________①____________; ____________②____________; End

Else if x[1] := ' ' then I := 2 Else I := 1; While ________③_________ do I := I + 1; While __________④___________ do BEGIN

If (x[I]>= '0') and (x[I]<= '9') Then begin k:=k+1;

________⑤_______;

If b=1 then ______⑥_______; end Else if (x[I]='.') and (b=0) then b := 1; I:=I+1 END;

If j>0 then while a[k]=0 do begin

__________⑦_________ __________⑧_________ End;

解答：显然，蓝色的程序段是用来处理实数的符号的，所以根据约定①应该是设置负数标记，即f:=1;根据else后面的句子，发现i为循环扫描的指针，所以②应该是确定下一位置，即i:=2；

③很明显是过滤掉空格！所以填：（x[i]=’ ’）and（i<10）;

④也很明显，一个大循环，判断字符串是否扫描结束，即：x[i]<>’%’

再看看b变量的含义：根据else子句，发现b=1表示整数部分结束！所以⑤是把一个数字字符转换成数字填到数组a中（a[k]:=ord(x[i])-48）；⑥填j:=j+1;(j表示小数点后的位数)；

⑦⑧很明显，是处理有小数、并且有多余的0的情况，所以为：j:=j-1;k:=k-1; 小结：注意程序前前后后看，发现变量的作用和含义！！！

? 4.典型算法+数据结构（1996年高中组1/初中组3）

四色问题：

设有下列形状的图形：（N=8），其编号 为1，2，??，N。

图形之间的相邻关系用下面的邻接矩阵表示：

26

其中：1——相邻，0——不相邻。

[程序要求] 将上面图形的每一个部分涂上红（1），黄（2），蓝（3），1 绿（4）四种颜色之一，要求相邻的部分有不同颜色。 2 输入方式：邻接矩阵。 3 输出方式：区域、颜色。 4 [算法描述] 用数组R:ARRAY[1..N,1..N] OF 0..1表示相邻关系，5 S:ARRAY[1..N] OF INTEGER 表示颜色。 6 采用回溯的方法，首先给第一个图形涂上红色（1），然后在下面的图7 形中依次涂上其他颜色，当有矛盾时回溯解决。 8 ［程 序］

PROGRAM EXP2(INPUT,OUTPUT);

CONST N=8;

VAR I,J,K:INTEGER;

R:ARRAY[1..N,1..N] OF 0..1; S:ARRAY[1..N] OF INTEGER; BEGIN

FOR I:=1 TO N DO BEGIN

FOR J:=1 TO N DO READ(R[I,J]); READLN END;

① ；I:=2; J:=1; WHILE I<=N DO BEGIN

WHILE (J<=4) AND (I<=N) DO BEGIN K:=1;

WHILE ② DO K:=K+1; IF K

④ ; I:=I+1; J:=1 END END;

IF J>4 THEN BEGIN

I:=I-1; ⑤ END; END;

FOR I:=1 TO N DO WRITELN(I,'?',S[I]) END.

解答：邻接矩阵+回溯法，步骤略，答案如下： ① S[1]：=1；

② (KJ ③ J:=J+1; ④ S[I]:=J; ⑤ J:=S[I]+1;

1 2 3 4 5 6 7 8 0 1 0 0 0 0 1 1 1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 0 ? 5.子程序及参数（1999年初中组）

[问题描述]

下面程序的功能是从键盘读取A，B数组的元素，A，B数组均已从小到大排好序（无相同元素），现将A，B

27

合并为数组C，同样要求数组C也是从小到大排好序（有相同元素时只保留一个）。

程序中N表示数组A，B的长度，i，j，k分别表示数组A，B，C的取数或存数的指针。 [程序清单]

program excp3;

const n=8;m=2*n;

type arr1=array[1..n]of integer; arr2=array[1..m]of integer; var a,b:arr1;c:arr2;i,j,k:integer;

procedure copy(x:arr1;var y:arr2;var i,j:integer); begin i:=i+1;

y[i]:=x[j]; j:=j+1; end; begin

for i:=1 to n do read(a[i]);readln; for i:=1 to n do read(b[i]);readln; i:=1;j:=1;___________①________ while__________②__________do

if a[i]

else if b[j]

copy(a,c,k,i);

__________③__________ end; while__________④___________do copy(a,c,k,i); while__________⑤___________do copy(b,c,k,j); for i:=1 to k do write (c[i]:4); writeln; end.

解答：就本题而言，算法和题目本身对选手很清楚！线性表的归并操作在NOIP中考过多次，不管是用数组来操作还是用链表操作；甚至还有一些题目是它的变形（比如多项式的加法）。

本题中的copy过程是关键，好在题目并没有考到过程调用的语句（关键是参数的书写），所以下面只要理解了过程的作用和4个参数的含义，题目就会很容易了。 答案：① k:=0

② (i<=n)and (j<=n) ③ j:=j+1 ④ i<=n ⑤ j<=n

? 6.特定的算法（1999年高中组2）

[问题描述] 用生成法求出1，2，?，r的全排列(r<=8) [算法过程] 用数组：a:array[1..r]of integer ;表示排列；

初始化时，a[I]:=1(I=1,2,?.f)

设中间的某一个排列为a[1],a[2],?a[r]，则求出下一个排列的算法为： (1) 从后面向前找，直到找到一个顺序为止（设下标为j,则a[j-1]

28

(4) 将a[j]，a[j+1]??a[r]由小到大排序。

[程序清单] program exp4; const r=7;

var n,i,s,k,j,i1,t:intger;

a:array[1..r]of integer; procedure print1; var ik:integer; begin

for ik:=1 to r do write(a[ik]:8);writeln; end begin

for i:=1 to r do __________①__________; print1; s:=1;

for i:=2 to r do s:=s*i; s:=s-1;

for i:=__________②__________do begin j:=r;

while__________③_________do j:=j-1; 步骤1 k:=j;

for i1:=j+1 to r do

if __________④_________then k:=i1; 步骤2 t:=a[j-1];a[j-1]:=a[k];a[k]:=t; 步骤3 for i1:=j to r-1 do for k:=i1+1 to r do

if __________⑤___________then 步骤4 begin

t:=a[i1];a[i1]:=a[k];a[k]:=t; end; print1; end; end.

解题步骤： 1） 首先，本题给出了关键而详细的算法说明，但没有给一个样例，下面我们结合一个中间状态数据，

看看如何生成下一个状态数据。

1 8 7 3 4 6 5 2

经过4步后得到：1 8 7 3 5 2 4 6 这样，你对程序的逻辑过程就很清楚了！！！ 2） 把程序分段：如上4中颜色。

红色的过程表示输出，没问题！

蓝色的显然是初始化，所以①填：a[i]:=i;

绿色的表示统计总的方案数（并且已经输出了一个，所以-1）；

紫色的程序段很明显是解决算法说明的4个步骤的，下面重点解决！ 3） 看看4个步骤分别对应着哪些语句？注意对应和找关键动作！！！

②应该填:1 to s 或s downto 1，但不能写成2 to s； ③填：a[j-1]>a[j]

29

④填：(a[i1]>a[j-1]) and (a[i1]a[k]，显然是从小到大冒泡排序用。

小结：重视题目给出的每一个信息与程序中的哪些语句对应；如果没有样例，自己找一个典型的，运行运行找出规律；程序的分块！！！

? 7.数据结构题（1999年高中组试题）

[问题描述]求一棵树的深度与宽度。

[算法说明]树可用数组tree:array[1..n,1..5]of integer;

其中：tree[I,1]表示结点号；tree[I,2]——tree[I,5]所属结点

（1）

（2）

（3）

（4）

（5）（ 6）（ 7） （8） （9） （10）

（11） （12）

（13） 如上图可表示为： 1 2 3 4 0 2 5 6 7 0 3 8 0 0 0 4 9 10 0 0 5 0 0 0 0 6 0 0 0 0 7 11 12 0 0 8 0 0 0 0 9 0 0 0 0 10 0 0 0 0 11 0 0 0 0 12 13 0 0 0 13 0 0 0 0

在求解的过程中，用到数组G:ARRAY[1..N,1..7]OF INTEGER； 其中：G[I,1]表示父结点，G[I,2]表示层次，

G[I,3]表示本结点号，G[I,4]——G[I,7]表示子女结点； 同时，设2个指针SP1（取数指针），SP2（存数指针） [程序清单]：

program exＧp3;

const n=13;

var i,j,k,sp1,sp2,n1,n2,jmax,p:integer; tree:array[1..n,1..5]of integer; g :array[1..n,1..7]of integer; begin

for i:=1 to n do begin

tree[i,1]:=i;

for j:=2 to 5 do read (tree[i,j]);readln; end;

30

sp1:=1;sp2:=1;g[1,1]:=0;g[1,2]:=1;g[1,3]:=1; for i:=4 to 7 do g[1,i]:=tree[1,i-2]; while__________①_________do begin

p:=g[sp1,2];n2:=g[sp1,3];_________②________;j:=4; while _________③_________do begin

n1:=g[sp1,j];j:=j+1;__________④_________; g[sp2,1]:=n2;g[sp2,2]:=p;g[sp2,3]:=n1; for i:=1 to 4 do g[sp2,i+3]:=tree[n1,i+1]; end;

__________⑤_________; end;

writeln('maxd=',g[sp2,2]); j:=1;k:=g[1,2];jmax:=0; for i:=2 to sp2 do

if __________⑥__________then j:=j+1 else begin

if j>jmax then jmax:=j;

__________⑦________;k:=g[Ｉ,2]; end; if j>jmax then jmax:=j; writeln('max1=',jmax); end. 解答：

1） 本题的数据结构含义，首先要搞清楚：tree[i,j]存储编号为i的结点的第j号孩子（2<=j<=5,即

最多4个孩子），tree[i,j]=0表示不存在；g[i,k]是一个队列，sp1为读取队列用的指针,sp2为存储队列用的指针。g[i,1] 存储i的父结点，g[i,2]存储i所在的层次，g[i,3]存储本结点的编号i，g[i,4],g[i,5],g[i,6],g[i,7]存储i的孩子结点编号。列出g的表格形式，以便更加直观！！！ 2） 程序关键在红色和蓝色的两段。先看红色段，①显然表示队列非空时做??，所以应该填：sp1<=sp2；

变量p是用来存放层次的，所以②填：p:=p+1；为该结点的孩子结点准备好层次；n2是表示当前处理的结点号，n1是表示n2的孩子结点号(用j循环)，③这个地方的循环是为了遍历本结点的所有孩子，所以③填：g[sp1,j]<>0；那么④⑤干什么呢？不要忘记一个重要的事情，队列的读取都需要移动指针（sp1,sp2），所以正好，④为下面的存入操作作准备，即sp2:=sp2+1;⑤为下一个结点的遍历操作作准备，即读指针下移：sp1:=sp1+1；

3） 下面看看蓝色的程序段，目的很明显是为了输出。再注意题目的目的：输出树的宽度和深度！深度

简单，其实就是g[sp2,2]。题目也没有考你！！！那么剩下的问题显然就是为了求宽度。方法也很简单，就是求每一层的宽度（即g[I,4]~g[I,7]中的非0个数，或者按本题的方法是看g[I,2]中最多有几个数相同），然后打擂台找出最大值。因此，⑥填：g[I,2]=k，计算层次相同的元素个数放在j中，用j与jmax打擂台，注意一层完了，j值要还原，宽度至少为1,所以⑦填：j:=1；

（2000年高中组试题）问题与上一样，只是写程序的人不一样，具体的风格不同而已。

小结：本题其实很重要的是队列的操作，经常出现的还有：堆栈操作、模拟法（解决递归等问题的现场保护和恢复）。

31