信息学奥赛-入门级 题库
编码问题:设有一个数组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+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值的算法。
找出小于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