信息学奥赛-入门级 题库
有N×N个数据组成如下方阵:

现将
…存储在一维数组A[1],A[2],…A[(N*(N+1))/2] 中。
试问:任给i,j怎样求出K来,使得A[K]的值正好是
请写出由i,j计算K值的表达式。
已知:
共有81个数,其中只有一个数比其它数大,要用最少的比较运算次数,把这个值大的数找出来(假设两个数比较一次能决定出大于、小于或等于这三种情况)请将以下算法补充完整:

设有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,然后用一个二重循环求出数列的逆数。
[程 序]

装球:设有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用数组元素代表盒子,然后依次装入小球。
[程序清单]

积木游戏:设有n 个小木块排成一排,如下图:

游戏开始时,每个小木块向下的一面涂有红、黄、蓝三种颜色之中的一种(约定:0表示红色,1表示黄色,2表示兰色)。要求通过翻看与交换方式对小木块重新排列(翻看的规则为每个小木快只能看一次),最终成为下面的形状:

即相同颜色的木块排列在一起,设计一个翻看与交换的方案,使得用最少的交换次数实现上面的要求。
[算法描述] 翻看小木块时,可以从两端进行。
例如,设中间状态如下:

此时,可以从两个方向看,即从A或B处开始:
(1)若看A则有三种可能性:
为红色,则不用交换
为兰色,交换一次,即A与B交换
为黄色,交换两次,即C与B交换一次,然后A与C再交换一次
此时,平均交换次数为1。
(2)若看B,也有三种可能性:
为兰色,则不用交换
为红色,交换一次,即B与A交换。
为黄色,交换一次,即B与C交换。
此时,平均交换次数为2/3。
由此可见,从B处翻看直到游戏结束,次数最少符合题目要求。
[程 序]

若将一个正整数化为二进制数,在此二进制数中,我们将数字1的个数多于数字0的个数的这类二进制数称为A类数,否则就称其为B类数。
例如:
其中1的个数为3,0的个数为1,则称此数为A类数;

其中1的个数为2,0的个数也为2,称此数为B类数;

其中1的个数为2,0的个数为3,则称此数为B类数;
程序要求:求出1~1000之中(包括1与1000),全部A、B两类数的个数。
编码问题:设有一个数组A:ARRAY[0..N-1] OF INTEGER;数组中存放的元素为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中的原数据。
灯的排列问题:设在一排上有N个格子(N≤20),若在格子中放置有不同颜色的灯,每种灯的个数记为N1,N2,……Nk(k表示不同颜色灯的个数)。
放灯时要遵守下列规则:
①同一种颜色的灯不能分开;
②不同颜色的灯之间至少要有一个空位置。
例如:N=8(格子数)
R=2(红灯数)
B=3(蓝灯数)
放置的方法有:


放置的总数为12种。
数据输入的方式为:
N
P1(颜色,为一个字母) N1(灯的数量)
P2 N2
……
Q(结束标记,Q本身不是灯的颜色)
程序要求:求出一种顺序的排列方案及排列总数。
执行①C>DIR 命令后,屏幕上显示如下画面:
FORMAT COM 12145
SYS COM 4878
PUC BAT 126
XCOPY EXE 11216
4 File(s) 123456 bytes free
接着又顺序执行了如下几条DOS 命令:
② C>DIR> DF.TXT //表示将列表显示的目录作为文件写盘 //
①C>TYPE DF.TXT
②C>DIR
试问:执行命令③和④ 在屏幕上显示的结果是否与①相同?
请将以下程序段表示的计算公式写出来(假设X的值已给出)
E:=1 ;
A:=1 ;
FOR N:=1 TO 10 DO
A:=A*X/N ;
E:=E+A ;
ENDFOR ;
写出所表示的公式。
列举一个算法,使算法的解能对应相应的问题。
例如,设问题为:学生答题,答对一题可得10分,答错一题则要扣去5分,输入答对的题数(M)与答错的题数(N),求最后得分(S)是多少?
列举出相应算法为:
X:=10;
Y:=5;
READ(M,N);
S:=X*M-Y*N;
现有以下问题:用五角钱换成5分、2分与1分的硬币,可有多少种换法?
请列出该问题的算法。
已知如下N*(N+1)/2个数据,按行的顺序存入数组A[1],A[2],……中:
a11
a21 a22
a31 a32 a33
……
an1 an2 an3 …… ann
其中:第一个下标表示行 第二个下标表示列。
若:aij(i≥j,j,i=1,2,……n)存贮在A[k]中,试问:
(1)k和i,j之间的关系如何表示?
(2)给定k值(k≤n*(n+1)/2)后,写出能决定相应的i,j值的算法。
有红、黄、黑、白四色球各一个,放置在一个内存编号为1、2、3、4四个格子的盒中,每个格子放置一只球,它们的顺序不知。甲、乙、丙三人猜测放置顺序如下:
甲:黑编号1,黄编号2;
乙:黑编号2,白编号3;
丙:红编号2,白编号4 。
结果证明甲乙丙三人各猜中了一半。
写出四色球在盒子中放置情况及推理过程。
求出所有满足下列条件的二位数:将此二位数的个位数字与十位数字进行交换,可得到一个新的数,要求新数与原数之和小于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;
找出小于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个整数。
程序: A[1] := 1; t := 0;
For i := 2 to 6 do
_____①____;
for j := 1 to i - 1 do
s := ______②_______;
ENDFOR;
a[i] := _______③_______;
ENDFOR;
FOR i:=1 TO 6 DO
T := ______④______ WRITE(a[i], ' ');
ENDFOR;
Writeln('能组成不同整数的个数:', t)
End.
求出2~1000之间长度最长的、成等差数列的素数(质数)。
例如:在2~50之间的全部素数有
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
其中公差为1的素数数列为2, 3,其长度为2
公差为2的素数数列为3, 5, 7,其长度为3
……
程序要求:输出满足条件的素数数列。
[算法提要]:首先用筛选法求出此范围内的全部素数,存放在数组B中,然后用2个变量i,j,逐步求出满足条件的素数数列。
程序: Max := 0; num := 1000;
For i := 2 to num do
b[i] := i;
ENDFOR
For i := 2 to ______①______ do
If _____②_____ then
k := i + i;
While k <= num do
B[k] := 0;
K := k + i
ENDWHILE;
ENDIF;
ENDFOR;
For i := 2 to num - 1 do
If ____
求出二个整形数组错位相加的最大面积。
1.数组面积的定义:(限定数组头尾不为0)设有一个数组C=(4,8,12,0,6)
则C的面积为:
Sc=(4+8)/2 + (8+12)/2 + 12/2 + 6/2
也就是说,Sc=各梯形面积之和(其中梯形的高约定为1,三角形作为梯形的特殊情况处理)。

又如D=(12, 24, 6)时,其面积的定义为Sd=(12+24)/2 + (24+6)/2

2.数组错位相加的定义
设有2个正整数的数组a,b,长度为n,当n=5时:
a=(34,26,15,44,12) b=(23,46,4,0,18)
对a、b进行错位相加,可能有下列情况
34 26 15 44 12
+) 23 46 4 0 18
34 26 15 44 12 23 46 4 0 18
或:
34 26 15 44 12
+) 23 46 4 0 18 -
34 26 15 44 35 46 4 0 18
或:
34 26 15 44 12
+) 23 46 4 &nb


