高中信息学竞赛各种问题求解试题及答案

1、高中信息学竞赛各种问题求解试题及答案 第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 < nS(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

2、)*(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的正方形)的顶点称为格点。以格点为顶点的多边形称为格

3、点多边形。若设格点凸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)位置。后来这位小朋友想知道，对

4、于N阶的方阵，随机取一个位置(x，y)，并规定xy，问这个位置上应该填的数字是多少?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、

5、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个或多个互不相同的正整数之和表示1511之间的

6、所有整数 至少要多少个不同的正整数_; 这些正整数是_答案：91,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，

7、1)，a2=(2，4)。调用排序过程将a1，a2排序，得到a1=(1，3)，a2=(2，4)，然后进行合并排序。从键盘输入数的长度n以及n个整数，存在数组a中，调用子过程sort进行排序，最后输出排序结果。program wsh；const maxn=100；type arr：array1.maxn of integer；var a：array1.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

8、 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 a1i:=ai; for i:= 1 to n2 do a2i:=_(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 an:=a1p1 ;inc(p1); end

9、else begin _(6)_; inc(p2) ;end; end; if p1 <= n1 then for i:= _(7)_ to n1 do begin n:=n+1;an:=a1i end else for i:=p2 to n2 do begin n:=n+1; an:=a2i; end; end;begin write('n = '); readln (n); for i:= 1 to n do read(ai); readln; sort(n,a); for i:=1 to n do write(ai,''); writeln;end.

10、答案：n-n1an1+isort(n1,a1)(p2 < =n2)a1p1 < a2p2an:=a2p2p1第2题(8分)有n(1n100)个同学种m(1nm100)种小树苗，例如：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 3program wsh;const maxn=100; maxm = 100;var a: array1.maxn, 1.maxm of integer; m

11、, 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 (ai,j); readln end; t:= maxint; work(1,0); writel

12、n(t)end.答案：k>n1mt1+tk,i第3题(10分)程序的任务是用09中的数字填入如下乘法运算的*处，数字可重复使用，且所用的数字至少有一个是素数，要求输出满足下列算式的方案数。 * * *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:=; for i:=1 to n do be

13、gin read(t); s:=s+t; end; close(f); end;function ok(x,l:integer):boolean; 此函数判断x是否符合条件 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; 此函数判断x中是否包含素数字 va

14、r 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; 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)

15、_; 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

16、)+1x>0x:=x div 10i:=i1*100+i2*10+i3ok(j1*i*10+j2*i,4)第4题(15分)下列程序是对冒泡排序的一种改进，数组elem中有n个元素elem1、elem2、elemn。要排序的关键字是key。先从一端开始扫描，进行比较、交换，然后改变下一趟的扫描方向进行同样的处理。请完善下面的过程。program wsh;type Td = record key: integer; inf: real; end;var elem:array1.1000 of Td; n, i: integer;procedure shakesort(n: integer);

17、 var i, t, h: integer; c: boolean; temp: Td; begin h:=1; t:=n; repeat _(1)_; for i:=h to t-1 do if elemi.key > elemi+1.key then begin temp:=elemi; elemi:=elemi+1; elemi+1:=temp; _(2)_; end; _(3)_; for i:=t-1 downto h do if elemi.key > elemi+1.key then begin temp:=elemi; elemi:=elemi+1; elemi+1

18、:=temp; _(4)_; end ; _(5)_; until c ; end;begin主过程 略end答案：c:=truec:=falset:=t-1c:=falseh:=h+1第5题(15分)读入一个10x10的数字矩阵，矩阵中的数字各不相同，输出这个矩阵经过旋转、翻转后的7种不同样式。program wsh;var matrix: array 0.7,1.10,1.10 of integer; lr, lc, which: integer;procedure overturn( which: integer); var lr, lc: integer; begin for lr:=

19、 1 to 10 do for lc:= 1 to 10 do matrixwhich,lr,lc:=matrixwhich-1,_(1)_,_(2)_; end;procedure rotate( which: integer); var lr, lc: integer; begin for lr:=1 to 10 do for lc:=1 to 10 do matrixwhich,lr,lc:=matrixwhich-1,_(3)_,_(4)_; end;begin for lr:= 1 to 10 do for lc:=1 to 10 do read(matrix0,lr,lc); re

20、adln; for which:= 1 to 7 do begin if _(5)_ then overturn(which) else rotate(which); for lr:=1 to 10 do begin for lc:= 1 to 10 do write(matrixwhich,lr,lc:3); writeln; end; readln; end;end.答案：11-lrlc11-lclrwhich=4第6题(16分)问题描述在n个元素的集合S中，找最大和最小元素(设n的值为2m)解题思路把集合S分成两个子集S1和S2，每个子集有n/2个元素应用递归过程search(S，Y，M

21、AX，MIN)(S中有2k个元素)，过程返回一对(MAX，MIN)值，为最大和最小元素，最后，把S1和S2中的最大和最小元素进行比较，从而得到S中的最大和最小元素程序program wsh;type data = array1.256 of byte; jh = set of byte;var s,ss:jh; a:data; i ,j, d,largest, smallest: byte;function sq(k: byte): byte; begin if k =1 then sq:=2 else sq:=2*sq(k-1); end;procedure seareh(x:jh; y:b

22、yte; var max,rain:byte); var k,p,w,nxl,nx2,ni1,ni2,n: byte; m:array1.2 of byte; s1 ,s2:jh; begin if y = 2 then begin p:=0; for k:=1 to i do if _(1)_ then begin p:=p+1;mp:=_(2)_; end; if _(3)_ then begin w:=m1;m1:=m2;m2:=w; end; max:= m1 ;min:= m2 ;exit; end else begin si:=;n:=O;y:=_(4)_; for k:=1 to

23、 i do if _(5)_ then begin n:=n+1;if n <= y then s1:=_(6)_; end; s2:=_(7)_; search(s1,y,nx1,ni1);search(s2,y,nx2,ni2); if nx1 > nx2 then max:=nx1 else max:=nx2; if ni1 < ni2 then min:=ni1 else min:=ni2; end end;begin i:=0;s:=;ss:=; for j:=1 to 7 do ss:=ss+sq(j); writeln('enter 2n data:&#

24、39;); repeat while not eoln do begin i:=i + 1; read(d); if _(8)_ then i:= i - 1 else begin ai:=d;s:=s+ai; end; end; readln; until i in ss; search(s,i,largest,smallest); writeln('largest-data：'，largest，'smallest-data：'，smallest)end答案：ak in xmp:=akm1 < =m2y:=trunc(y/2)ak in xs1:=s1+

25、aks2:=x-s1d in s第7题(14分)问题描述将一个含有运算符为：(、)、+、-、*、/、(乘幂运算)、(求负运算)的中缀表达式，如：(1+2)*5)2-(3+5)/2转化为后缀表达式，如：12+5*235+2/-解题思路将中缀表达式转化为后缀表达式，首先规定运算符的优先数如下：运算符 ( ) +， * ，/ 优先数 0 1 2 3 4 5 1若输入是运算量，则将该运算量输出；2若是左括号“(”，则将该符号的优先数压入设置的运算符堆栈ep中去；3输入运算符优先数是2，3，4，5时，如果栈空，则将运算符的优先数进栈。如果栈不空，则将它与栈顶元素进行比较，倘若优先数大于栈顶元素的优先数，

26、则进栈；小于顶元的，则顶元退栈并输出该运算符，然后再继续比较，直到大于顶元或栈空时进栈；4若是右括号“)”，同时栈顶元又为左括号“(”，则栈顶元退栈，并抹去右括号“)”否则转3处理；5输入完而栈非空，则将栈内内容逐一退栈并输出。所有输出的结果就为后缀表达式。过程中用到的相关数据结构如下：type arraydata = array1.100 of string20;const fh:array1.8 of string1 =('(',')','+','-','*','/','',&#

27、39;'); b:array1.8 of byte =(0,1,2,2,3,3,4,5);var d: arraydata; 存储运算量及运算符号 i,j,m,k: byte;过程程序procedure hzbds(var d: arraydata; var m: byte ); var: array 1'-. 100 of byte; i,p,k ,bi:byte; bl: boolean; begin p:=O;k:=1;bj:=0; while k<=m do begin if _(1)_ then begin p:=p+1;ep:=1 end else begin

28、 for i:=2 to 8 do if _(2)_ then begin b1:= true; repeat if _(3)_ then begin p:= p+1 ;ep:=i;bj:= 1 ;b1:= false end else if _(4)_ then if ep < >1 then begin p:=p+1;ep:=i;bj:=1;b1:=false end else if dk < >')' then begin p:=p+1;ep:=i;bj:=1;b1:=false end else begin _(5)_;bj:= 1 ;b1:=

29、false; end else begin write(fhep ,' ') ;p:=p-1 end; until b1 = false; end if _(6)_ then write(dk ,' ') else bj:=0; end; k:=k+1 end b1:= true; repeat if p=0 then b1:= false else begin _(7)_;p:=p-1; end until b1 = false; writeln; end;答案：dk:='('dk:=fhip=0bep < bip:=p-1bj=0wri

30、te(fhep,'')第8题(15分)以下程序完成对数组每个元素向后移动n个单位。数组元素的下标依次为0到m-1，对任意一个数组元素ai而言，它的值移动后将存储在数组元素a(i+n) mod m中。例如，m=10，n=3，移动前数组中存储的数据如下前一行所示，则程序运行后数组中存储的数据如下后一行所示。 0 3 86 20 27 67 31 16 37 42 16 37 42 0 3 86 20 27 67 3 程序清单：program wsh;const maxm = 10000;var i, k, m, n, rest, start, temp: longint; a:ar

31、ray 0.maxm of longint;begin write('input m, n: '); readln(m ,n); for i:=0 to m-1 do ai:= random(100); writeln('before move'); for i:=0 to m -1 do write(ai:5); writeln; rest:= m; start:= 0; while _(1)_ do begin k:= start; repeat k:=(k+n) mod m until k <= start; if _(2)_ then begin

32、temp:= ak; repeat ak:=a(m*n+k-n) mod m; k:=(m*n+k-n) mod m; _(3)_; until k = start; _(4)_; end; _(5)_; end; writeln('after move'); for i:=0 to m - 1 do write(ai:5); writelnend.答案：rest>0k:=startrest:=rest-1a(k+n) mod m:=tempstart:=start+1第9题(15分)设m叉树采用列表法表示，即每棵子树对应一个列表，表的结构为：子树根顶点的值部分(设为一个

33、字符)和用“( )”括起来的各树的列表(如有子树的话)，各子列表间用“,”分隔。例如下面的三叉树可用表a(b(c,d),e,f(g,h,i)表示。 本程序输入列表，生成一棵m叉树，并由m叉树输出列表。假定输入无错误。程序清单：program wsh;const m=3;type pointer =node; node = record val: char; subtree: array 1.m of pointer end;var i: integer; bur: string; root: pointer;procedure maketree(var s: pointer); 由列表生成m叉

34、树 var k: integer; begin _(1)_; s.val:= bufi; i:=i+1; for k:=1 to m do s.subtreek:=nil; if bufi='(' then begin k:=1; repeat i:=i+1; _(2)_; if bufi =')' then begin i:= i + 1; break end; k:=k+1 until _(3)_; end end;procedure walktree(t:pointer); 由m叉树输出列表 var i: integar; begin if t <

35、> nil then begin _(4)_; if t.subtree1 < > nil then begin write('('); for i:=1 to m do begin _(5)_; if (i< >m)and(t.subtreei+1 < >nil) then write(',') end; write(')') end end end;begin main program write('input list: '); readln(buf); i:=1; maketree

36、(root); walktree(root); writelnend.答案：new(s)maketree(s.subtreek)bufi < >','write(t.val)walktree(s.subtreei)阅读程序试题及其答案第1题(6分)program yd;var d, p: integer;begin p:=1; d:=11; while d>1 do begin p:=2*(p+1); d:=d-1 end; writeln (p)end.输出：_答案：3070第2题(6分)program yd;var g,m: integer; k,t: r

37、eal;begin k:=0; g:=0; for m:=1 to 49 do begin g:=g+1; k:=k+1/(g*(g+1) end; writeln ( k: 10: 2 )end.输出：_答案： 0.98第3题(6分)program yd;var n, i, t: longint; tem: integer; s: string;begin write('Input n: '); readln(n); s:='1' repeat i:= length(s); while si ='1' do begin si:= '0&

38、#39; ;dec(i); end; if i>0 then si:='1' else s:= '1' +s; val(s,t,tem); until t mod n = 0; writeln(n,'*',t div n,'=',s);end.输入：6输出：_答案：6*185=1110第4题(6分)program yd;const n = 5;var i,j,m,s:integer;begin m:=0; for i:=1 to n do begin m:=m+i; s:=m; for j:=1 to 2*i do writ

39、e(''); ''中间是一个空格 for j:=1 to n do begin write(s mod 10:2); s:=s+j; end; writeln; end;end.输出：_答案：1 2 4 7 13 4 6 9 36 7 9 2 60 1 3 6 05 6 8 1 5第5题(7分)program yd;var a:array0.8 of char; i: integer;begin for i:= 1 to 8 do ai:=char(i * 2 +ord('A'); for i:= 1 to 4 do begin a0:=ai;

40、ai:=a9-i; a9-i:=a0; end; for i:= 1 to 8 do write(ai); writeln;end.输出：_答案：QOMKIGEC第6题(7分)Program yd;var n, i, x: integer; d:array0.10 of integer;begin readln(n); fori:=1 to n do begin read(x); dx:=dx +1; end; d0:=0; for i:=1 to 10 do di:=di-1+di; for i:=1 to 10 do if di < > di-1 then writeln(i:

41、3,di-1+1:4);end.输入: 20 3 4 6 1 7 6 9 4 10 7 6 6 3 3 8 7 9 10 6 7输出：_答案： 1 1 3 2 4 5 6 7 7 12 8 16 9 17 10 19第7题(7分)program yd;var a,b:array1.32 of integer; i: integer;procedure ssort( i ,j: integer); var m, k, x: integer; begin if j-i>1 then begin m:=(i+j) div 2; ssort(i,m); ssort(m+1,j); k:=i; f

42、or x:=i to m do begin bk:=ax; bk+1:=am+x-i+1; k:=k+2; end; for x:=i to j do ax:=bx; end; end;begin for i:=1 to 16 do ai:=i; ssort(1,16); for i:= 1 to 16 do write(ai:3); writeln;end.输出：_答案： 1 9 5 13 3 11 7 15 2 10 6 14 4 12 8 16第8题(6分)program yd;var a,d:array1.100 of integer; n ,i ,j ,k,x ,s :integer

43、;begin n:=5;a1:=1;d1:=1; for i:=1 to n do begin s:=i+1;x:=0; for j:=1 to n+1-i do begin k:=s+x;x:=x+1;aj+1:=aj+k; write(aj,' '); end; writeln('.');di+1:=di+i;a1:=di+1; end;end.输出：_答案：1 3 6 10 15 .2 5 9 14 .4 8 13 .7 12 .11 .第9题(7分)program yd;const d: array 0.3,1.4 of integer =(4,7,10

44、,13),(1,8,11,14),(2,5,12,15),(3,6,9,16);var i ,j ,a,x,k ,bj :integer; y,u,v:real;begin for i:=1 to 4 do begin a:=3-i;bj:=0; for j:=0 to 3 do for k:=1 to 4 do begin x:=dj,k;u:=(x+a)/4;v:=(x+trunc(u)/4; y:=4*(v-trunc(v); if y< >j then begin k:=4;j:=3;bj:=1;end; end; if bj=0 then begin write('U = (X'); if a>0 then write('+'); writeln(a,')