全国第二届青少年信息学奥林匹克竞赛分区联赛初赛试题 [1996年]

1. 已知A盘上的目录和文件组织如下:（1+1+3=5%） 其中TP、TB、DOS、D11、D31都是子目录名。 设当前命令提示符为 A:＼TB> ,请写出完成如下操作的DOS 命令： ① 将F1.TXT 移到D31子目录中去； ② 删除子目录 TB ； ③ 在DOS运行中，没有执行过PATH命令，现要用DOS子目录中FORMAT命令，对插入在B驱动器（5.25英寸高密）中的360KB软盘进行格式化工作，请写出相应的操作命令。
答案：① A：\TB>COPY \TP\D11\F1.TXT \DOS\D31 ② A：\TB>DEL\ TB\*.* A：\TB>RD TB ③ A：\TB>\DOS\FORMAT B：/4

2. 执行命令时，屏幕上显示如下出错信息：（1+1=2%） WRITE PROTECT ERROR WRITING DRIVE B ABORT， RETRY ， FALL ？ 请说明这是什么错误？应如何校正？
答案：错误：向B盘写入时发现写保护。 校正：可在驱动器灯不亮时取出B盘，去掉写保护然后重新插入B驱动器，回答R，重新写入。

3. 请用等号或不等号联接表示下列不同进位制数值的大小。（3%） 例如：（3）10 <(4)4 =(100)2 < ( A )16 其中圆括号外右下角的下标，表示圆括号内数的进位制。 （21）10 (15)16 (25)8 (10101)2
答案：10 （15）16=（25）8=（10101）2

4. 阅读下列程序段，写出程序段运行后变量X的值。（4%） 100 X1=3 X1：=3 ； X2：=8 ； FOR I：=1 TO 5 DO BEGIN 循环结构，应用数据轮换方式，求 X：=（X1+X2）*2 ； 两个数和的2倍。 X1：=X2 ；X2：=X ； END； WRITELN（‘X=’，X） ；
答案：X=1224

5. 阅读下列程序段，写出程序运行后数组元素A1，A2，…，A11中的值。（6%） A[1]：=1； A[2]：=1 ； K：=1 ； REPEAT A[K+2]：=1 ； FOR I：=K DOWNTO 2 DO A[I]：=A[I] +A[I-1 ] ； K：=K+1 ； UNTIL K>=10 ；
答案：注：除A6 为1分外，其余每空为0.5分） A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 1 10 45 120 210 252 210 120 45 10 1

6. 已知：ACK（M，N）函数的计算公式如下： （4%） N+1 M=0 ACK（M，N）= ACK（M-1，1） N=0 ACK（M-1，ACK（M，N-1） M≠0 且N≠0 请计算：ACK（1，2）与ACK（2，2）的值。
答案：ACK（1，2）=4 ACK（2，2）=7

7. 请写出对应计算如下算式的程序段：（4%） Y=ANX^N+A(N-1)X^(N-1)+……A1X+A0
答案：Y：=1； FOR I：=N DOWNTO 0 DO Y：=Y*X+A[I]；

8. 有N×N个数据组成如下方阵：（7%） A11 A12 A13 …… A1N A21 A22 A23 …… A2N A31 A32 A33 …… A3N ………… AN1 AN2 AN3 …… ANN 并已知： Aij = Aji 现将A11 ，A21，A22 ，A31 ，A32 ，A33 …存储在一维数组A[1]，A[2]，…A[（N*（N+1））/2] 中。 试问：任给i，j怎样求出K来，使得A[K]的值正好是Aij，请写出由i，j计算K值的表达式。
答案：IF I>=J THEN K=（I*（I-1））/2+J ELSE K=（J*（J-1））/2+I

9. 已知：A1，A2，……，A81 共有81个数，其中只有一个数比其它数大，要用最少的比较运算次数，把这个值大的数找出来（假设两个数比较一次能决定出大于、小于或等于这三种情况）请将以下算法补充完整：（9%） 第一步： S1 = A1 + A2 + …… + A27 S2 = A28 + A29 +……+ A54 第一次比较（S1，S2） ： S1 > S2 取 K=0 S1 < S2 取 K=27 S1 = S2 取 K=54 第二步： S1 = AK+1 + AK+2 + …… + AK+9 S2 = AK+10 + AK+11 +……+ AK+18 第二次比较（S1，S2） ： S1 > S2 取 K= S1 < S2 取 K= S1 = S2 取 K= 第三步： S1 = AK+1 + AK+2 + AK+3 S2 = AK+4 + AK+5 + AK+6 第三次比较（S1，S2） ： S1 > S2 取 K= S1 < S2 取 K= S1 = S2 取 K= 第四步： S1 = AK+1 S2 = AK+2 第四次比较（S1，S2） ： S1 > S2 为最大数 S1 < S2 为最大数， S1 = S2 为最大数。
答案：第二次比较（S1，S2）： S1>S2 取K=K+0 S1<S2 取K=K+9 S1=S2 取K=K+18 第三次比较（S1，S2）： S1>S2 取K=K+0 S1<S2 取K=K+3 S1=S2 取K=K+6 第四次比较（S1，S2）： S1>S2 AK+1为最大数 S1<S2 AK+2为最大数 S1=S2 AK+3为最大数

1. 设有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    N-1     DO
    FOR J:=     I+1     TO N DO
      IF A[I]>A[J] THEN    S:=S +1；	    ;
  WRITELN('S=',S)
END.

2. 20分（每空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);
      A[0]:=0；     ;
  J:=1;
  WHILE      K>A[J-I]       DO BEGIN
    A[J]:=J;      K:=K-J      ; J:=J+1
  END;
  L:=J-1;
  WHILE K>0 DO BEGIN
         A[L]:=A[L]+1      ;
    K:=K-1;
    L:=L-1;
  END;
  FOR I:=1 TO      J-1       DO
    WRITE(A[I]:4)
END.

3. 21分（3+4+3+3+4+4）
积木游戏：设有n 个小木块排成一排，如下图：
……
游戏开始时，每个小木块向下的一面涂有红、黄、蓝三种颜色之中的一种（约定：0表示红色，1表示黄色，2表示兰色）。要求通过翻看与交换方式对小木块重新排列（翻看的规则为每个小木快只能看一次），最终成为下面的形状：
…… …… ……
红 蓝 黄
即相同颜色的木块排列在一起，设计一个翻看与交换的方案，使得用最少的交换次数实现上面的要求。
[算法描述] 翻看小木块时，可以从两端进行。
例如，设中间状态如下：
…… A …… B …… C ……
红 未翻过 蓝 黄
此时，可以从两个方向看，即从A或B处开始：
（1）若看A则有三种可能性：
为红色，则不用交换
为兰色，交换一次，即A与B交换
为黄色，交换两次，即C与B交换一次，然后A与C再交换一次
此时，平均交换次数为1。

（2）若看B，也有三种可能性：
为兰色，则不用交换
为红色，交换一次，即B与A交换。
为黄色，交换一次，即B与C交换。
此时，平均交换次数为2/3。
由此可见，从B处翻看直到游戏结束，次数最少符合题目要求。

[程 序]

 
CONST N=20;
VAR I,TEM,R,B,Y:INTEGER;
           A:ARRAY[1..N] OF 0..2;
BEGIN
  FOR I:=1 TO N DO READ(A[I]);
  R:=1;     B:=N      ; Y:=N;
  WHILE      R<=B     DO
IF      A[B]=0      THEN BEGIN
 TEM:=A[R];A[R]:=A[B];A[B]:=TEM;
 R:=R+1
END
ELSE IF      A[B]=1      THEN BEGIN
  TEM:=A[B];A[B]:=A[Y];A[Y]:=TEM;
       Y:=Y-1     ;      B:=B-1     ;
END
ELSE B:=B=1
  FOR I:=1 TO N DO WRITE(A[I]:3)
END.