高中信息学竞赛各种问题求解试题及
答案
第1题(5分)，将n个不同颜色的球放人k个无标号的盒子中( n>=k，且盒子不允许为空)的方案数
为S(n，k)，例如：n=4，k=3时，S(n，k)=6。当n=6，k=3时，S(n，k)=________。答案：0 k < n S(n,k)= 1
k = 1
S(n-1,k-1)+k*S(n-1,k) n >= k >= 2
第2题(5分)，有5本不同的数学书分给5个男同学，有4本不同的英语书分给4个女同学，将全部书收回来后再从新发给他们，与原方案都不相同的方案有________种。答案：
5!*4!+D(5)*D(4)=1140480
其中：D(n)=(n-1)*(D(n-1)+D(n-2))
(n > 2)
D(1)=0 D(2)=1
第3题(6分)，把三角形各边分成n等分，过每一分点分别做各边的平行线，得到一些由三角形的边和这些平行线所组成的平行四边形。n为已知整数，能组成_______个平行四边形。答案：
3*C(n+2,4)
第4题(6分)，由a，b，c3个不同的数字组成一个N位数，要求不出现两个a相邻，也不出现两个b
相邻，这样的N位数的个数为AN，用AN-1和AN-2表示AN的关系式为：AN＝_______________。答案：
AN= 2*AN-1+AN-2
第5题(6分)，在m*n的棋盘上，每个方格(单位正方形，即边长为1的正方形)的顶点称为格点。以格点为顶点的多边形称为格点多边形。若设格点凸N边形面积的最小值为gn，格点凸N边形内部(非顶点的)格点
的个数的最小值为fn，则gn和fn的关系式为：gn=___________。答案：
Gn= fn+N/2-1 ( N >= 3 )
第6题(4分)，编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1、2、3、…、20、21、…，一圈又一圈。问：当数到数字N
时，所在纸牌的编号为多少? 答案：
1+(N-1) mod 13
第7题(8分)，有位小同学喜欢在方阵中填数字，规则是按下图示例从右上角开始，按斜线填数字，碰到边界就重新。显然，数字
1在坐标(1，5)位置，数字
25在坐标(5，1)位置。后来这位小朋友想知道，
对于N阶的方阵，随机取一个位置(x，y)，并规定x≤ｙ，问
这个位置上应该填的数字是多少?5阶方阵的
示例图如下：
11 7 4 2 1 16 12 8 5 3 20 17 13 9 6 23 21 18 14 10 25 24 22 19 15
答案：
(N-y+x)*(N-y+x-1)/2+x
第8题(5分)，设有质量为1、3、9、27、81、…3ng...的砝码各一枚，如果砝码允许放在天平的两边，
则用它们来称物体的质量，最多可称出1g到3n+3n/2g之间的所有质量，如n=4时，可称出18到121g之间的
所有质量；当物体质量为M=14时，有14+9+3+1=27，即天平一端放M=14g的物体和9g、3g、1g的砝码，另一
端放27g的砝码，即可称出M的质量。当M=518g时，请你写出称出该物体的质量的方法，并用上述所示的等式来表示。答案：
518+243+3+1= 729+27+9
第9题(7分)，在圆周上有N个点(N>=6)，在任意两个
点之间连一条弦，假设任何3条弦在圆的内部
都没有公共点，问这些弦彼此相交能在圆内构成多少个三角形(只要求写出三角形总数的表示式而无需化简)?
提示：下图是N=6的情况，图中所示的4个三角形从
某种意义上说具有一定的代表性。答案：
C(N,3)+4*C(N,4)+5*C(N,5)+6*C(N,6)
第10题(6分)，用1个或多个互不相同的正整数之和表示1～511之间的所有整数
①至少要多少个不同的正整数_________________; ②这些正整数是_______________ 答案：①９
②1,2,4,6,16,32,64,128,256
第11题(7分)，在有m行n列格子的棋盘内，一枚棋子从棋盘的左上角格子沿上、下、左、右方向行走，最后走到棋盘的右下角格子。该棋子走过的格子数为奇数的充分必要条件是________________ 答案：m+n为偶数
完善程序试题及其答案
第1题(14分)以下程序是将一组整数按从小到大的顺序排列。排序的方法是将长度为n的数a分为两个长度分别为(n div 2)与(n-n div 2)的子数组a1，a2。然后递归调用排序过程，将a1，a2分别排序，最后将a1，a2归并成数组a。例如a=(3，1，2，4)，那么a1=(3，1)，a2=(2，4)。调用排序过程将a1，a2排序，得到a1=(1，3)，a2=(2，4)，然后进行合并排序。从键盘输入数的长度n以及n个整数，存在数组a中，调用子过程sort进行排序，最后输出排序结果。program wsh；
const maxn=100；．
type arr：array[1..maxn] of integer；var
a：array[1..maxn] of integer；
n，i：integer；
procedure sort(n:integer; var a:arr); var
i, p1, p2, n1, n2: integer; a1,a2 :arr; begin
if n = 1 then exit;
fillchar(a1,sizeof(a1) ,0); fillchar(a2,sizeof(a2) ,0); n1:=0; n2:=0;
n1:=n div 2; n2:=(____(1)____); for i:= 1 to n1 do a1[i]:=a[i];
for i:= 1 to n2 do a2[i]:=____(2)____; ____(3)____; sort(n2, a2); p1:=1; p2:=1; n:=0;
while (p1 <= n1) and (____(4)____) do begin
n:=n+1;
if ____(5)____
then begin a[n]:=a1[p1] ;inc(p1); end else begin ____(6)____; inc(p2) ;end; end;
if p1 <= n1
then for i:= ____(7)____ to n1 do begin
n:=n+1;a[n]:=a1[i] end
else for i:=p2 to n2 do begin n:=n+1; a[n]:=a2[i]; end; end; begin
write('n = '); readln (n);
for i:= 1 to n do read(a[i]); readln; sort(n,a);
for i:=1 to n do write(a[i],''); writeln; end.
答案：n-n1 a[n1+i] sort(n1,a1) (p2 < =n2)
a1[p1] < a2[p2] a[n]:=a2[p2] p1
第2题(8分)有n(1≤n≤100)个同学种m(1≤n≤m≤100)种小树苗，例如：4个同学（1、2、3、4）每小时种4种树苗（A、B、C、D）的数量估算如下表所示，编程输出每人种1种苗所用的总时间最少的安排方案和所花费的时间。学生A B C D 1 5 2 4 5 2 4 3 5 3 3 5 2 4 2 4 3 2 3 3 program wsh; const
maxn=100; maxm = 100; var
a: array[1..maxn, 1..maxm] of integer; m, n: integer; i, j, t: integer;
procedure work(k,t1: integer); var i: integer; begin
if ____(1)____ then begin
if t1 < t then t1:=t; exit; end;
for i:= ___(2)___ to ___(3)___ do work(k+1,___(4)___); end; begin
readln(n,m);
for i:=1 to n do begin
for j:=1 to m do read (a[i,j]); readln end;
t:= maxint; work(1,0); writeln(t) end. 答案：
k>n 1 m
t1+t[k,i]
第3题(10分)程序的任务是用0…９中的数字填入如下乘法运算的*处，数字可重复使用，且所用的数字至少有一个是素数，要求输出满足下列算式的方案数。*
* *
x * * -------------------------
* * * * * *
------------------------- * * * program wsh;
const p:set of 0...9 = [2,3,5,7]; var
s:set of 0..9; n: integer; ans: longint; f: text;
procedure init; var
i: integer; t:byte; begin
readln(n); s:=[];
2
for i:=1 to n do begin read(t); s:=s+[t]; end; close(f); end;
function ok(x,l:integer):boolean; 件}
var t: byte; begin
ok:=false;
if ___(1)___< > l then exit; while x< >0 do begin
t:=x mod 10;
if not ( t in s) then exit; x:=x div 10; end; ok:=true; end;
function inset(x:integer):boolean; 素数字}
var t: byte; begin
inset:= false;
while ___(2)___ do begin
t:=x mod 10; if t in p then begin
inset:= true; exit; end;
___(3)___; end; end;
procedure work;
var i,i1,i2,i3,j1,j2:integer; begin
ans:=0;
{此函数判断{此函数判断x是否符合条
x中是否包含
for i1:=1 to 9 do if i1 in s then for i2:=1 to 9 do if i2 in s then for i3:=1 to 9 do if i3 in s then begin
___(4)___;
for j1:=1 to 9 do
if (j1 in s) and ok(j1*i,3) then for j2:=1 to 9 do
if (j2 in s) and ok(j2*i,3) and ___(5)___ then
begin
if (i1 in p) or (i2 in p) or (i3 in p)
or (j1 in p) or (j2 in p) or inset(j1*i) or
inset(j2*i)
then inc(ans); end;
end; writeln(ans); end; begin
init; work; end. 答案：
trunc(ln(x)/ln(10))+1 x>0
x:=x div 10
i:=i1*100+i2*10+i3 ok(j1*i*10+j2*i,4)
第4题(15分)下列程序是对冒泡排序的一种改进，数组elem中有n个元素elem[1]、elem[2]…、elem[n]。要排序的关键字是key。先从一端开始扫描，进行比较、交换，然后改变下一趟的扫描方向进行同样的处理。请完善下面的过程。
program wsh; type
Td = record
key: integer; inf: real; end; var
elem:array[1..1000] of Td; n, i: integer;
procedure shakesort(n: integer); var
i, t, h: integer; c: boolean; temp: Td; begin h:=1; t:=n; repeat
____(1)____; for i:=h to t-1 do
if elem[i].key > elem[i+1].key then begin temp:=elem[i]; elem[i]:=elem[i+1]; elem[i+1]:=temp; ____(2)____; end;
____(3)____;
for i:=t-1 downto h do
if elem[i].key > elem[i+1].key then begin temp:=elem[i]; elem[i]:=elem[i+1]; elem[i+1]:=temp; ____(4)____; end ;
____(5)____; until c ; end;
begin{主过程} …｛略} end．
各种问题3
高中信息学奥林匹克竞赛各种问题求解试题及参考答案集锦
