高中信息學(xué)競賽各種問題求解試題及答案

1、高中信息學(xué)競賽各種問題求解試題及答案 第1題(5分)，將n個(gè)不同顏色的球放人k個(gè)無標(biāo)號(hào)的盒子中( n>=k，且盒子不允許為空)的方案數(shù)為S(n，k)，例如：n=4，k=3時(shí)，S(n，k)=6。當(dāng)n=6，k=3時(shí)，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本不同的數(shù)學(xué)書分給5個(gè)男同學(xué)，有4本不同的英語書分給4個(gè)女同學(xué)，將全部書收回來后再從新發(fā)給他們，與原方案都不相同的方案有_種。答案： 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等分，過每一分點(diǎn)分別做各邊的平行線，得到一些由三角形的邊和這些平行線所組成的平行四邊形。n為已知整數(shù)，能組成_個(gè)平行四邊形。答案：3*C(n+2,4) 第4題(6分)，由a，b，c3個(gè)不同的數(shù)字組成一個(gè)N位數(shù)，要求不出現(xiàn)兩個(gè)a相鄰，也不出現(xiàn)兩個(gè)b相鄰，這樣的N位數(shù)的個(gè)數(shù)為AN，用AN-1和AN-2表示AN的關(guān)系式為：AN_。答案：AN= 2*AN-1+AN-2 第5題(6分)，在m*n的棋盤上，每個(gè)方格(單位正方形，即邊長為1的正方形)的頂點(diǎn)稱為格點(diǎn)。以格點(diǎn)為頂點(diǎn)的多邊形稱為格

3、點(diǎn)多邊形。若設(shè)格點(diǎn)凸N邊形面積的最小值為gn，格點(diǎn)凸N邊形內(nèi)部(非頂點(diǎn)的)格點(diǎn)的個(gè)數(shù)的最小值為fn，則gn和fn的關(guān)系式為：gn=_。答案：Gn= fn+N/2-1 ( N >= 3 ) 第6題(4分)，編號(hào)為1到13的紙牌順時(shí)針排成一圈，有人從編號(hào)為1的牌從數(shù)字1開始順時(shí)針數(shù)下去，1、2、3、20、21、，一圈又一圈。問：當(dāng)數(shù)到數(shù)字N時(shí)，所在紙牌的編號(hào)為多少?答案：1+(N-1) mod 13 第7題(8分)，有位小同學(xué)喜歡在方陣中填數(shù)字，規(guī)則是按下圖示例從右上角開始，按斜線填數(shù)字，碰到邊界就重新。顯然，數(shù)字1在坐標(biāo)(1，5)位置，數(shù)字25在坐標(biāo)(5，1)位置。后來這位小朋友想知道，對(duì)

4、于N階的方陣，隨機(jī)取一個(gè)位置(x，y)，并規(guī)定xy，問這個(gè)位置上應(yīng)該填的數(shù)字是多少?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分)，設(shè)有質(zhì)量為1、3、9、27、81、3ng.的砝碼各一枚，如果砝碼允許放在天平的兩邊，則用它們來稱物體的質(zhì)量，最多可稱出1g到3n+3n/2g之間的所有質(zhì)量，如n=4時(shí)，可稱出18到121g之間的所有質(zhì)量；當(dāng)物體質(zhì)量為M=14時(shí)，有14+9+3+1=27，即天平一端放M=14g的物體和9g、3g、

5、1g的砝碼，另一端放27g的砝碼，即可稱出M的質(zhì)量。當(dāng)M=518g時(shí)，請(qǐng)你寫出稱出該物體的質(zhì)量的方法，并用上述所示的等式來表示。答案：518+243+3+1= 729+27+9 第9題(7分)，在圓周上有N個(gè)點(diǎn)(N>=6)，在任意兩個(gè)點(diǎn)之間連一條弦，假設(shè)任何3條弦在圓的內(nèi)部都沒有公共點(diǎn)，問這些弦彼此相交能在圓內(nèi)構(gòu)成多少個(gè)三角形(只要求寫出三角形總數(shù)的表示式而無需化簡)? 提示：下圖是N=6的情況，圖中所示的4個(gè)三角形從某種意義上說具有一定的代表性。答案：C(N,3)+4*C(N,4)+5*C(N,5)+6*C(N,6) 第10題(6分)，用1個(gè)或多個(gè)互不相同的正整數(shù)之和表示1511之間的

6、所有整數(shù) 至少要多少個(gè)不同的正整數(shù)_; 這些正整數(shù)是_答案：91,2,4,6,16,32,64,128,256 第11題(7分)，在有m行n列格子的棋盤內(nèi)，一枚棋子從棋盤的左上角格子沿上、下、左、右方向行走，最后走到棋盤的右下角格子。該棋子走過的格子數(shù)為奇數(shù)的充分必要條件是_答案： m+n為偶數(shù)完善程序試題及其答案第1題(14分)以下程序是將一組整數(shù)按從小到大的順序排列。排序的方法是將長度為n的數(shù)a分為兩個(gè)長度分別為(n div 2)與(n-n div 2)的子數(shù)組a1，a2。然后遞歸調(diào)用排序過程，將a1，a2分別排序，最后將a1，a2歸并成數(shù)組a。例如a=(3，1，2，4)，那么a1=(3，

7、1)，a2=(2，4)。調(diào)用排序過程將a1，a2排序，得到a1=(1，3)，a2=(2，4)，然后進(jìn)行合并排序。從鍵盤輸入數(shù)的長度n以及n個(gè)整數(shù)，存在數(shù)組a中，調(diào)用子過程sort進(jìn)行排序，最后輸出排序結(jié)果。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)個(gè)同學(xué)種m(1nm100)種小樹苗，例如：4個(gè)同學(xué)（1、2、3、4）每小時(shí)種4種樹苗（A、B、C、D）的數(shù)量估算如下表所示，編程輸出每人種1種苗所用的總時(shí)間最少的安排方案和所花費(fèi)的時(shí)間。 學(xué) 生 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分)程序的任務(wù)是用09中的數(shù)字填入如下乘法運(yùn)算的*處，數(shù)字可重復(fù)使用，且所用的數(shù)字至少有一個(gè)是素?cái)?shù)，要求輸出滿足下列算式的方案數(shù)。 * * *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; 此函數(shù)判斷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; 此函數(shù)判斷x中是否包含素?cái)?shù)字 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分)下列程序是對(duì)冒泡排序的一種改進(jìn)，數(shù)組elem中有n個(gè)元素elem1、elem2、elemn。要排序的關(guān)鍵字是key。先從一端開始掃描，進(jìn)行比較、交換，然后改變下一趟的掃描方向進(jìn)行同樣的處理。請(qǐng)完善下面的過程。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分)讀入一個(gè)10x10的數(shù)字矩陣，矩陣中的數(shù)字各不相同，輸出這個(gè)矩陣經(jīng)過旋轉(zhuǎn)、翻轉(zhuǎn)后的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個(gè)元素的集合S中，找最大和最小元素(設(shè)n的值為2m)解題思路把集合S分成兩個(gè)子集S1和S2，每個(gè)子集有n/2個(gè)元素應(yīng)用遞歸過程search(S，Y，M

21、AX，MIN)(S中有2k個(gè)元素)，過程返回一對(duì)(MAX，MIN)值，為最大和最小元素，最后，把S1和S2中的最大和最小元素進(jìn)行比較，從而得到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分)問題描述將一個(gè)含有運(yùn)算符為：(、)、+、-、*、/、(乘冪運(yùn)算)、(求負(fù)運(yùn)算)的中綴表達(dá)式，如：(1+2)*5)2-(3+5)/2轉(zhuǎn)化為后綴表達(dá)式，如：12+5*235+2/-解題思路將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式，首先規(guī)定運(yùn)算符的優(yōu)先數(shù)如下：運(yùn)算符 ( ) +， * ，/ 優(yōu)先數(shù) 0 1 2 3 4 5 1若輸入是運(yùn)算量，則將該運(yùn)算量輸出；2若是左括號(hào)“(”，則將該符號(hào)的優(yōu)先數(shù)壓入設(shè)置的運(yùn)算符堆棧ep中去；3輸入運(yùn)算符優(yōu)先數(shù)是2，3，4，5時(shí)，如果?？?，則將運(yùn)算符的優(yōu)先數(shù)進(jìn)棧。如果棧不空，則將它與棧頂元素進(jìn)行比較，倘若優(yōu)先數(shù)大于棧頂元素的優(yōu)先數(shù)，

26、則進(jìn)棧；小于頂元的，則頂元退棧并輸出該運(yùn)算符，然后再繼續(xù)比較，直到大于頂元或棧空時(shí)進(jìn)棧；4若是右括號(hào)“)”，同時(shí)棧頂元又為左括號(hào)“(”，則棧頂元退棧，并抹去右括號(hào)“)”否則轉(zhuǎn)3處理；5輸入完而棧非空，則將棧內(nèi)內(nèi)容逐一退棧并輸出。所有輸出的結(jié)果就為后綴表達(dá)式。過程中用到的相關(guān)數(shù)據(jù)結(jié)構(gòu)如下：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; 存儲(chǔ)運(yùn)算量及運(yùn)算符號(hào) 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分)以下程序完成對(duì)數(shù)組每個(gè)元素向后移動(dòng)n個(gè)單位。數(shù)組元素的下標(biāo)依次為0到m-1，對(duì)任意一個(gè)數(shù)組元素ai而言，它的值移動(dòng)后將存儲(chǔ)在數(shù)組元素a(i+n) mod m中。例如，m=10，n=3，移動(dòng)前數(shù)組中存儲(chǔ)的數(shù)據(jù)如下前一行所示，則程序運(yùn)行后數(shù)組中存儲(chǔ)的數(shù)據(jù)如下后一行所示。 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分)設(shè)m叉樹采用列表法表示，即每棵子樹對(duì)應(yīng)一個(gè)列表，表的結(jié)構(gòu)為：子樹根頂點(diǎn)的值部分(設(shè)為一個(gè)

33、字符)和用“( )”括起來的各樹的列表(如有子樹的話)，各子列表間用“,”分隔。例如下面的三叉樹可用表a(b(c,d),e,f(g,h,i)表示。 本程序輸入列表，生成一棵m叉樹，并由m叉樹輸出列表。假定輸入無錯(cuò)誤。程序清單：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(''); ''中間是一個(gè)空格 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,')