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

小学、初中、高中各科资料汇总第1页共20页有任何资料需要，请QQ联系：10300877571高中信息学竞赛各种问题求解试题及答案第1题(5分)，将n个不同颜色的球放人k个无标号的盒子中(n=k，且盒子不允许为空)的方案数为S(n，k)，例如：n=4，k=3时，S(n，k)=6。当n=6，k=3时，S(n，k)=________。答案：0knS(n,k)=1k=1S(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))(n2)D(1)=0D(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)mod13第7题(8分)，有位小同学喜欢在方阵中填数字，规则是按下图示例从右上角开始，按斜线填数字，碰到边界就重新。显然，数字1在坐标(1，5)位置，数字25在坐标(5，1)位置。后来这位小朋友想知道，对于N阶的方阵，随机取一个位置(x，y)，并规定x≤y，问这个位置上应该填的数字是多少?5阶方阵的示例图如下：11742116128532017139623211814102524221915答案：(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之间的所有整数①至少要多少个不同的正整数_________________;②这些正整数是_______________答案：①9②1,2,4,6,16,32,64,128,256第11题(7分)，在有m行n列格子的棋盘内，一枚棋子从棋盘的左上角格子沿上、下、左、右方向行走，最后走到棋盘的右下角格子。该棋子走过的格子数为奇数的充分必要条件是________________答案：m+n为偶数完善程序试题及其答案第1题(14分)以下程序是将一组整数按从小到大的顺序排列。排序的方法是将长度为n的数a分为两个长度分别为(ndiv2)与(n-ndiv2)的子数组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进行排序，最后输出排序结果。programwsh；constmaxn=100；．typearr：array[1..maxn]ofinteger；var小学、初中、高中各科资料汇总第2页共20页有任何资料需要，请QQ联系：10300877572a：array[1..maxn]ofinteger；n，i：integer；proceduresort(n:integer;vara:arr);vari,p1,p2,n1,n2:integer;a1,a2:arr;beginifn=1thenexit;fillchar(a1,sizeof(a1),0);fillchar(a2,sizeof(a2),0);n1:=0;n2:=0;n1:=ndiv2;n2:=(____(1)____);fori:=1ton1doa1[i]:=a[i];fori:=1ton2doa2[i]:=____(2)____;____(3)____;sort(n2,a2);p1:=1;p2:=1;n:=0;while(p1=n1)and(____(4)____)dobeginn:=n+1;if____(5)____thenbegina[n]:=a1[p1];inc(p1);endelsebegin____(6)____;inc(p2);end;end;ifp1=n1thenfori:=____(7)____ton1dobeginn:=n+1;a[n]:=a1[i]endelsefori:=p2ton2dobeginn:=n+1;a[n]:=a2[i];end;end;beginwrite('n=');readln(n);fori:=1tondoread(a[i]);readln;sort(n,a);fori:=1tondowrite(a[i],'');writeln;end.答案：n-n1a[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种苗所用的总时间最少的安排方案和所花费的时间。学生ABCD15245243533524243233programwsh;constmaxn=100;maxm=100;vara:array[1..maxn,1..maxm]ofinteger;m,n:integer;i,j,t:integer;procedurework(k,t1:integer);vari:integer;beginif____(1)____thenbeginift1tthent1:=t;exit;end;fori:=___(2)___to___(3)___dowork(k+1,___(4)___);end;beginreadln(n,m);fori:=1tondobeginforj:=1tomdoread(a[i,j]);readlnend;t:=maxint;work(1,0);writeln(t)end.答案：kn1mt1+t[k,i]第3题(10分)程序的任务是用0…9中的数字填入如下乘法运算的*处，数字可重复使用，且所用的数字至少有一个是素数，要求输出满足下列算式的方案数。***x**-------------------------******-------------------------***programwsh;constp:setof0...9=[2,3,5,7];vars:setof0..9;n:integer;ans:longint;f:text;procedureinit;vari:integer;t:byte;beginreadln(n);s:=[];fori:=1tondobeginread(t);s:=s+[t];end;close(f);end;functionok(x,l:integer):boolean;{此函数判断x是否符合条件}小学、初中、高中各科资料汇总第3页共20页有任何资料需要，请QQ联系：10300877573vart:byte;beginok:=false;if___(1)___lthenexit;whilex0dobegint:=xmod10;ifnot(tins)thenexit;x:=xdiv10;end;ok:=true;end;functioninset(x:integer):boolean;{此函数判断x中是否包含素数字}vart:byte;begininset:=false;while___(2)___dobegint:=xmod10;iftinpthenbegininset:=true;exit;end;___(3)___;end;end;procedurework;vari,i1,i2,i3,j1,j2:integer;beginans:=0;fori1:=1to9doifi1insthenfori2:=1to9doifi2insthenfori3:=1to9doifi3insthenbegin___(4)___;forj1:=1to9doif(j1ins)andok(j1*i,3)thenforj2:=1to9doif(j2ins)andok(j2*i,3)and___(5)___thenbeginif(i1inp)or(i2inp)or(i3inp)or(j1inp)or(j2inp)orinset(j1*i)orinset(j2*i)theninc(ans);end;end;writeln(ans);end;begininit;work;end.答案：trunc(ln(x)/ln(10))+1x0x:=xdiv10i:=i1*100+i2*10+i3ok(j1*i*10+j2*i,4)第4题(15分)下列程序是对冒泡排序的一种改进，数组elem中有n个元素elem[1]、elem[2]…、elem[n]。要排序的关键字是key。先从一端开始扫描，进行比较、交换，然后改变下一趟的扫描方向进行同样的处理。请完善下面的过程。programwsh;typeTd=recordkey:integer;inf:real;end;varelem:array[1..1000]ofTd;n,i:integer;procedureshakesort(n:integer);vari,t,h:integer;c:boolean;temp:Td;beginh:=1;t:=n;repeat____(1)____;fori:=htot-1doifelem[i].keyelem[i+1].keythenbegintemp:=elem[i];elem[i]:=elem[i+1];elem[i+1]:=temp;____(2)____;end;____(3)____;fori:=t-1downtohdoifelem[i].keyelem[i+1].keythenbegintemp:=elem[i];elem[i]:=elem[i+1];elem[i+1]:=temp;____(4)____;end;____(5)____;untilc;end;begin