陕西省西安高级中学导高中信息技术奥赛强化练习卷六.doc

信息学奥赛强化练习卷六

以下各题请分析问题，完善程序：
1． [题 目]
找出小于33的6个正整数，用这些整数进行加法运算，使得包括原来的整数在内能组成尽可能多的不同整数。
例如：用2，3，5这三个数能可组成下面的数
2, 3, 5
2 + 3 = 5, 但5已经存在
2 + 5 = 7, 3 + 5 = 8, 2 + 3 + 5 = 10
所以用2，3，5能组成6个不同的数。
[程序要求]：输出所选的这6个数，以及能组成不同整数的个数。
[算法提要]：选择的这6个数，用来组成数时应该尽可能不重复，引入数组A保存找出的这6个整数。
程序：begin
A[1] := 1; t := 0;
For i := 2 to 6 do
begin
_____①____;
for j := 1 to i - 1 do
s := ______②_______;
a[i] := _______③_______;
END;
FOR i:=1 TO 6 DO
begin
T := ______④______ WRITE(a[i], ' ');
END;
Writeln('能组成不同整数的个数：', t)
End.
答：
① s:=0;
② s:=s+a[j];
③ a[i]:=s+1
④ t:=t+a[i]; 或t:=t*2+1
分析：掌握程序中变量S的意义是求解本题的关键。根据算法说明中提到的 “选择的这6个数，用来组成数时应尽可能不重复” 这一策略，同时，这6个数要小于33的限制条件，我们不妨假设前I-1个数a1,a2,a3,a4…ai-1 已找到，对第I 个数ai, 确定其值的原则为：（1）ai 要尽可能小且满足a1<a2<a3<a4<…<ai-1<ai ；（2）由ai参与加法的结果应大于a1+a2+…a i-1 , 这样保证与前I-1个数所组成的整数不重复。显然ai=a1+a2+…ai-1+1。因此，S的意义为前I-1个数之和，填空②为S+a[ j ], 填空①置S初值为0，填空③为S+1。
我们还可以换一种方法来思考：所选6个数1=a1<a2<a3<a4<a5<a6<33, 这6个数在组成数时，每一个数都有参与加法或不参与加法两种可能，很自然想到，这6个数在组成数时，可用一个6位二进制数表示b6b5b4b3b2b1, 其中bi=0表示ai不参与加法运算，bi=1表示ai参与加法运算。6位二进制数的每一种情况就表示组成的一个数，且各不相同。000001表示只有a[1]=1时的值，当有a[1]=1和a[2]时，能组成的数为000001，000010，000011，这3个不同的数，所以a[2]取2，即二进制000010，。。。。依次可得a[3]=4, 即二进制000100，a[4]=8, a[5]=16, a[6]=32。
能组成不同整数的个数 t=a[1]+a[2]+a[3]+a[4]+a[5]+a[6], 所以④处应填 t+a[I ],得到累加和。

2． [题 目]
求出所有满足下列条件的二位数：将此二位数的个位数字与十位数字进行交换，可得到一个新的数，要求新数与原数之和小于100。
程序要求：每行输出6个满足条件的数。
[算法提要] 分解每一个二位数，然后重新组成一个新数，当满足条件时，用计数器来统计个数。
程序： K := 0;
FOR i := ______①____ TO 99 DO
X := _____②_____; Y := _____③_____;
J := x * 10 + y;
IF ____④_____ THEN
K := k + 1;
Write(I : 4);
______⑤_____ THEN WRITELN;
ENDIF
ENDFOR;
答：
① 10
② x:=i mod 10;
③ y:=i div 10;
④ If (i+j)<100
⑤ if k mod 6=0

3．[题 目]
设有N个不同整数的数列：例如N=4时，有4个不同整数的数列为17，4，16，5。数列中的第1个数17，比它后面的三个数都大，则称数17的逆数为3。数列中的第2个数4比它后面的数都小，则称数4的逆数为0。同时记数列中全部逆数的和称为数列的逆数。上例中，数列17，4，16，5的逆数：为3+0+1+0=4。

[程序要求] 当给出N个不同整数的数列后，求出此数列的逆数。

[算法描述] 为求得上面问题的解，设置数组A : ARRAY[1..N] OF INTEGER 和逆数计数器5，然后用一个二重循环求出数列的逆数。

[程 序]
CONST N=10;
VAR I,J,S:INTEGER;
A:ARRAY[1..N] OF INTEGER;
BEGIN
S:=0;
FOR I:=1 TO N DO READ(A[I]);
FOR I:=1 TO ① DO
FOR J:= ② TO N DO
IF A[I]>A[J] THEN ③ ;
WRITELN('S=',S)
END.
答： ① N-1 ② I+1 ③ S：=S +1；

4．[题 目]
装球：设有n个盒子（n足够大，可装入任何数量的球），分别编号1，2，……。同时有k个小球（k>0），今将k 个小球装入到盒子中去。
装入规则如下：
（1） 第一个盒子不能为空。
（2） 装入必须严格按递增顺序进行。
例如，当k=8，n=6时，装入方法有1，2，5或1，3，4
（3） 在满足上面的两个条件下，要求有球的盒子尽可能多。
（4） 装完后，相邻盒子中球个数差的绝对值之和最小（未装的盒子不计）。
如上例中：
装入法1，2，5，则差的绝对值之和为2-1+5-2=4
装入法1，3，4，则差的绝对值之和为3-1+4-3=3

[程序要求] 给出k（k表示小球的个数）之后，求出满足上述四个条件的装入方法。
[算法描述] 设计一个数组A用数组元素代表盒子，然后依次装入小球。
[程序清单]
CONST N=20;
VAR I,J,K,L:INTEGER;
A:ARRAY[1..N] OF INTEGER;
BEGIN
READLN (K) ;
① ;
J:=1;
WHILE ② DO BEGIN
A[J]:=J; ③ ; J:=J+1
END;
L:=J-1;
WHILE K>0 DO BEGIN
④ ;
K:=K-1;
L:=L-1;
END;
FOR I:=1 TO ⑤ DO
WRITE(A[I]:4)
END.
答：① for I:=1 to n do A[I]：=0； ② K>A[J-I] ③ K：=K-J
④ A[L]：=A[L]+1 ⑤ J-1
分析：由本题条件（1），第一个盒子至少放一个小球，即A[I]>=1；根据条件（2）盒子中放到小球数必须严格按递增的顺序，因此A[1]<A[2]<…<A[n-1]<A[n]。为达到放球的盒子尽可能多，也就是n 尽可能大的目的，在小球数K确定的情况下，对每个盒子放球时要尽可能节约，显然A[1]=1, A[2]=2…A[n]=n是最节约的放法，具体实现时，先根据盒子的编号，从1号盒子放1个球，2号盒子放2个球，…，n号盒子放n个球，n的确定可根据余下的球数小于n+1为止。也就是第n+1个盒子就不够放了。因此，填空②③处的作用应该是余下的球数不够放下一个盒子，所以③处是计算余下的球数，应该填K：=K-J, 而②处为循环控制条件k>=J。上述这种放球的思路可以仔细阅读程序得到启发：语句a[ j]:= j 告诉我们程序先利用第j 号盒子放 j 个球的方法，满足题目给出的前三个条件。
用上述方法放球后，如果余下的球数为0，放球过程结束，如果还有球多出来，把这些余下的球再分配到各个装球的盒中，考虑到条件（4）：装完后，相邻的盒中球的个数差的绝对值之和为最小，如何分配，这是程序要处理的第二个问题。由于a1<a2<…<an，相邻盒中球个数差的绝对值之和：s=(a2-a1)+(a3-a2)+…+（an-2-an-1）
= a2-a1+a3-a2+…+an-2-an-1+an-an-1=an-a1
显然s与第1个盒子、第n个盒子的球数有关，增加第1个盒子的球数，可以使s更小，但第1个盒子加1个，后面的盒子至少都要加1个，而多出来的球数<=n ,所以只能从编号大的加起，逐个往编号小的盒子中加1个球，直到加完为止（最多n个盒子）。程序中④处应填 a[1]:=a[1]+1。变量 j 的最后值为装球盒子数加1，所以输出部分I 的终值应为装球的盒子数：j-1

2．[题 目]
4色问题。 设有下列形状的图形：（N=8），其编号为1，2，……，N。

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

1
2
3
4
5
6
7
8
1
0
1
0
0
0
0
1
1
2
1
0
1
0
0
1
1
0
3
0
1
0
1
0
1
0
0
4
0
0
1
0
1
1
0
0
5
0
0
0
1
0
1
0
0
6
0
1
1
1
1
0
1
0
7
1
1
0
0
0
1
0
1
8
1
0
0
0
0
0
1
0

其中：1——相邻，0——不相邻。
[程序要求] 将上面图形的每一个部分涂上红（1），黄（2），蓝（3），绿（4）四种颜色之一，要求相邻的部分有不同颜色。
输入方式：邻接矩阵。
输出方式：区域、颜色。
…………
[算法描述] 用数组R:ARRAY[1..N,1..N] OF 0..1表示相邻关系，S:ARRAY[1..N] OF INTEGER 表示颜色。
采用回溯的方法，首先给第一个图形涂上红色（1），然后在下面的图形中依次涂上其他颜色，当有矛盾时回溯解决。
［程 序］
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 THEN ③
ELSE BEGIN
④ ; 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 ； ② (K<I) AND (S[K]*R[I,J])<>J
③ J:=J+1; ④ S[I]:=J; ⑤ J:=S[I]+1
分析：涂色算法：深度优先搜索
读入邻接矩阵；
对第一号区域涂色；
while I<n do {还有区域尚未涂色}
while (J<=4) and (I<=n) do {选择颜色}
begin
if k<I and (检查相邻区域，如不是当前要涂色区域) then
试探下一区：k+1àK
if 当前色不能涂 then 试探下一种颜色：y+1ày
else 本区域涂色，准备试探下一区域
if 试探不成功 then {回溯}
I-1àI {返回上一个点区域}
修正y颜色值；
end;
3．[题　 目]
多项式加法运算：一个仅含有x的多项式可以用下列的方式表示：
（系数，指数），（系数，指数），…，（0，0）。
其中（0，0）作为结束标志。
例如：P(x)=4x6-3x3+2x2-1
可表示为：(4,6),(-3,3),(2,2),(-1,0),(0,0)
Q(x)=x4-x+1
可表示为：(1,4),(-1,1),(1,0),(0,0)
当用上面的方式给出2个多项式之后，编制程序对这两个多项式进行加法运算，结果也用上面的方式给出。
例如：上面的P(x)和Q(x)相加的结果为：
4x6+x4-3x3+2x2-x
表示结果为：(4,6),(1,4),(-3,3),(2,2),(-1,1),(0,0)
[算法描述] 多项式可用数组P表示；分别以p1表示P，p2表示Q，p3表示结果。
处理的过程为将P复制到p3，然后逐项检查Q，当发现有相同的方次时，进行系数相加；当发现没有相同方次时，插入到p3中去。
[程 序]
PROGRAM EXP3(INPUT,OUTPUT)
VAR
X,Y,I,I1,J,J1,J2:INTEGER;
P1,P2,P3 :ARRAY[1..20,1..2] OF INTEGER
BEGIN
J1:=0; WRITE('INPUT P(X)='); READ(X,Y);
WHILE X<>0 DO
BEGIN
J1:=J1+1; P1[J1,1]:=X; P1[J1,2]:=Y; READ(X,Y)
END;
J1:=J1+1; P1[J1,1]:=0; P1[J1,2]:=0;
WRITE('INPUT Q(X)='); READ(X,Y); J2:=0;
WHILE X<>0 DO
BEGIN
J2:=J2+1; P2[J2,1]:=X; P2[J2,2]:=Y; READ(X,Y)
END;
J2:=J2+1; P2[J2,1]:=0; P2[J2,2]:=0;
FOR I:=1 TO J1 DO
BEGIN
P3[I,1]:=P1[I,1]; P3[I,2]:=P1[I,2]
END;
I:=1;
WHILE ① DO
BEGIN
IF ② THEN
BEGIN
FOR J:=J1 DOWN TO 1 DO
BEGIN
P3[J+1,1]:=P3[J,1]; P3[J+1,2]:=P3[J,2]
END;
P3[I,1]:=P2[I,1]; P3[I,2]:=P2[I,2]; J1:=J1+1
END
ELSE BEGIN
I1:=1;
WHILE P2[I,2]<P3[I1,2] DO
③ ;
IF P2[I,2]=P3[I1,2] THEN
P3[I1,1]:= ④
ELSE BEGIN
FOR J:=J1 DOWNTO I1 DO
BEGIN
P3[J+1,1]:=P3[J,1]; P3[J+1,2]:=P3[J,2]
END;
P3[I1,1]:=P2[I,1]; P3[I1,2]:=P2[I,2];
⑤
END;
END；
I：=I+1
END；
FOR J:=1 TO J1-2 DO WRITE ('(',P3[J,1],',',P3[J,2],'),');
WRITELN('(',P3[J+1,1],',',P3[J+1,2],')');
END.
答：① P2[I，1]<>0 ② P2[I，1]> P3[1，2] ③ I1:=I1+1;
④ P3[I1，1]+ P2[I，1] ⑤ J1:=J1+1 ;
分析：
程序实现的是线性表的归并算法。多项式相加的规则是指数相同，系数相加。多项式p和q 利用了将系数不为0的项用一对数字表示某一项的方式，分别存在一个二维数组中，p和q 相加的结果用另一个二维数组存放。根据算法说明，归并运算实际上在表示多项式q的数组p2和表示相加结果的数组p3之间进行，p3的初始值为表示多项式p的数组p1，其初始长度为p1的长度。以后在归并过程中，p3的长度将会变大，因此，仔细阅读程序可发现，表示p3长度的变量j1是一个关键的量。程序的主要部分是如何实现将p2的每一分量加入到数组p3中去。
程序利用循环扫描数组p2的方法，其扫描指针为变量I ，因此（1）处为循环控制条件，由题意可知，应为p2[I ,1]<>0；下面的循环体用嵌套的if then else 结构分别处理p2数组的当前分量p2[I]是插入到p3还是与p3中某一分量合并（指数相同时）。从if 条件（2）成立时处理的程序段for j:=j1 downto 1 do …可知，是将p3各项依次向后移一位置，p2[I]插入p3的第1个位置，可知，（2）应为p2[I,2]>p3[I,2], 即p2(i )的指数大于p3的最大指数（注：数组表示多项式均利用降幂形式）。当（2）处条件不成立时，p2(i)将与p3中各分量一一比较，程序用语句i1:=1; while p2[I,2] <p3[i1,2] do ③ 来实现，③处实现时表示P3分量位置指针I1往后移，直到P2[I,2]<P3[I1,2]不成立， 所以空格③处应填I1:=I1+1;然后比较P2和P3当前分量的指数，若相同，则系数相加P3[I1,1]:=P3[I1,1]+P2[I,1]。指数不同，此时P2[I,2]>P3[I1,2]，就把P2的第I个分量插入到P3的I1位置。空格⑤处应处理p3的长度增加，即j1:=j1+1。
题目给出的程序中，忽略了一种情形，当p2与p3 中两个同类项相加，系数之和为0时，是否要保存在p3中，程序没有进行处理，因此，p3中会出现系数为0的项，同学们可试试改动程序，使之更符合题目要求。