高中信息学竞赛各种问题求解试题及答案第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 = 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)) (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≤y,问这个位置上应该填的数字是多少?5阶方阵的示例图如下:11 7 4 2 116 12 8 5 320 17 13 9 623 21 18 14 1025 24 22 19 15答案:(N-y+x)*(N-y+x-1)/2+x第8题(5分),设有质量为1、3、9、27、81、…3n g...的砝码各一枚,如果砝码允许放在天平的两边,则用它们来称物体的质量,最多可称出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分为两个长度分别为(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;vara:array[1..maxn] of integer;n,i:integer;procedure sort(n:integer; var a:arr);vari, p1, p2, n1, n2: integer;a1,a2 :arr;beginif 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)____) dobeginn:=n+1;if ____(5)____then begin a[n]:=a1[p1] ;inc(p1); endelse begin ____(6)____; inc(p2) ;end;end;if p1 <= n1then for i:= ____(7)____ to n1 do begin n:=n+1;a[n]:=a1[i] endelse for i:=p2 to n2 do begin n:=n+1; a[n]:=a2[i]; end; end;beginwrite('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-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种苗所用的总时间最少的安排方案和所花费的时间。
学生 A B C D1 52 4 52 43 5 33 5 24 24 3 2 3 3program wsh;constmaxn=100; maxm = 100;vara: array[1..maxn, 1..maxm] of integer;m, n: integer;i, j, t: integer;procedure work(k,t1: integer);var i: integer;beginif ____(1)____ thenbeginif t1 < t then t1:=t;exit;end;for i:= ___(2)___ to ___(3)___ dowork(k+1,___(4)___);end;beginreadln(n,m);for i:=1 to n dobeginfor j:=1 to m do read (a[i,j]);readlnend;t:= maxint;work(1,0);writeln(t)end.答案:k>n1mt1+t[k,i]第3题(10分)程序的任务是用0…9中的数字填入如下乘法运算的*处,数字可重复使用,且所用的数字至少有一个是素数,要求输出满足下列算式的方案数。
* * *x * *-------------------------* * ** * *-------------------------* * *program wsh;const p:set of 0...9 = [2,3,5,7];vars:set of 0..9;n: integer;ans: longint;f: text;procedure init;vari: integer;t:byte;beginreadln(n);s:=[];for i:=1 to n dobeginread(t);s:=s+[t];end;close(f);end;function ok(x,l:integer):boolean; {此函数判断x是否符合条件}var t: byte;beginok:=false;if ___(1)___< > l then exit;while x< >0 dobegint:=x mod 10;if not ( t in s) then exit;x:=x div 10;end;ok:=true;end;function inset(x:integer):boolean; {此函数判断x中是否包含素数字}var t: byte;begininset:= false;while ___(2)___ dobegint:=x mod 10;if t in p thenbegininset:= true;exit;end;___(3)___;end;end;procedure work;var i,i1,i2,i3,j1,j2:integer;beginans:=0;for i1:=1 to 9 doif i1 in s thenfor i2:=1 to 9 doif i2 in s thenfor i3:=1 to 9 doif i3 in s thenbegin___(4)___;for j1:=1 to 9 doif (j1 in s) and ok(j1*i,3) thenfor j2:=1 to 9 doif (j2 in s) and ok(j2*i,3) and ___(5)___thenbeginif (i1 in p) or (i2 in p) or (i3 in p)or (j1 in p) or (j2 in p) or inset(j1*i) orinset(j2*i)then inc(ans);end;end;writeln(ans);end;begininit;work;end.答案:trunc(ln(x)/ln(10))+1x>0x:=x div 10i:=i1*100+i2*10+i3ok(j1*i*10+j2*i,4)第4题(15分)下列程序是对冒泡排序的一种改进,数组elem中有n个元素elem[1]、elem[2]…、elem[n]。