同創(chuàng)杯全國(guó)青少年信息學(xué)(計(jì)算機(jī))奧林匹克競(jìng)賽

1、NOI95 “同創(chuàng)杯同創(chuàng)杯”全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克競(jìng)賽全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克競(jìng)賽分區(qū)聯(lián)賽初賽試題（初中組）分區(qū)聯(lián)賽初賽試題（初中組） 競(jìng)賽用時(shí)：競(jìng)賽用時(shí)：2 小時(shí)小時(shí)一、基礎(chǔ)題： 執(zhí)行CDIR 命令后，屏幕上顯示如下畫(huà)面： FORMAT COM 12145 SYS COM 4878 PUC BAT 126 XCOPY EXE 11216 4 FILE（S） 123456 bytes free接著又順序執(zhí)行了如下幾條 DOS 命令： CDIR DF.TXT /表示將列表顯示的目錄作為文件寫(xiě)盤(pán) / CTYPE DF.TXT CDIR 試問(wèn):執(zhí)行命令和 在屏幕上顯示的結(jié)果是否

2、與相同?答 題 要 求一、全部試題答案均應(yīng)寫(xiě)在答卷紙上，寫(xiě)在試卷紙上一概無(wú)效。二、算法描述中，可以使用下列過(guò)程、函數(shù)或算符：（1）算術(shù)運(yùn)算：，DIV，MOD整數(shù)除（DIV）：是取二整數(shù)相除的商的整數(shù)部分。如：11 DIV 2 = 5取模（MOD）：是取二整數(shù)相除的余數(shù)。 如：11 MOD 2 = 1（2）關(guān)系運(yùn)算：，=，=，=（3）邏輯運(yùn)算：AND，OR，NOT（4）函數(shù)：ABS(X)：求 X 的絕對(duì)值。如：ABS（3.14）=3.14 ABS(-3.14)=3.14SQR(X)：求 X 的平方值。如：SQR（3）=9 SQR（-15）=225SQRT(X)：求 X 的平方根值。如：SQRT(

3、9)=3 SQRT(225)=15TRUNC(X)：去掉 X 的小數(shù)部分：如 TRUNC(6.3)=6 TRUNC(-7.9)=-7ROUND(X)：函數(shù)值是小數(shù)四舍五入后的整數(shù)值。 如：ROUND(3.14)=3 ROUND(3.16)=4 ROUND(-3.14)=-4ORD(X)：函數(shù)值是字符在 ASCII 碼中的序號(hào)。 如：ORD(A)=65 ORD(B)=66 ORD(Z)=90 ORD(0)=48CHR(X)：X 表示 ASCII 碼中的序號(hào)，函數(shù)值是該序號(hào)代表的字符值。 如：CHR(48)=0 CHR(65)=A CHR(90)=Z（5）過(guò)程： DEC(A,X)：變量遞減，A 為

4、有序變量，X 缺省時(shí)為 1。INC(A,X)：變量遞增，A 為有序變量，X 缺省時(shí)為 1。 請(qǐng)將以下程序段表示的計(jì)算公式寫(xiě)出來(lái)（假設(shè) X 的值已給出） E：=1 ； A：=1 ； FOR N：=1 TO 10 DO A：=A*X/N ； E：=E+A ； ENDFOR ； 寫(xiě)出所表示的公式。寫(xiě)出所表示的公式。 列舉一個(gè)算法，使算法的解能對(duì)應(yīng)相應(yīng)的問(wèn)題。例如，設(shè)問(wèn)題為：學(xué)生答題，答對(duì)一題可得 10 分，答錯(cuò)一題則要扣去 5 分，輸入答對(duì)的題數(shù)（M）與答錯(cuò)的題數(shù)（N） ，求最后得分（S）是多少？列舉出相應(yīng)算法為：X：=10；Y：=5； READ（M，N） ； S：=X*M-Y*N；現(xiàn)有以下問(wèn)題：用

5、五角錢(qián)換成 5 分、2 分與 1 分的硬幣，可有多少種換法？請(qǐng)列出該問(wèn)題的算法。請(qǐng)列出該問(wèn)題的算法。 已知如下 N*(N+1)/2 個(gè)數(shù)據(jù)，按行的順序存入數(shù)組 A1，A2，中：a11a21 a22a31 a32 a33an1 an2 an3 ann其中：第一個(gè)下標(biāo)表示行 第二個(gè)下標(biāo)表示列。若：aij(ij,j,i=1,2,n)存貯在 Ak中，試問(wèn)：（1）k 和和 i，j 之間的關(guān)系如何表示？之間的關(guān)系如何表示？（2）給定給定 k 值（值（kn*(n+1)/2)后，寫(xiě)出能決定相應(yīng)的后，寫(xiě)出能決定相應(yīng)的 i，j 值的算法。值的算法。 有紅、黃、黑、白四色球各一個(gè)，放置在一個(gè)內(nèi)存編號(hào)為 1、2、3、

6、4 四個(gè)格子的盒中，每個(gè)格子放置一只球，它們的順序不知。甲、乙、丙三人猜測(cè)放置順序如下： 甲：黑編號(hào) 1，黃編號(hào) 2； 乙：黑編號(hào) 2，白編號(hào) 3； 丙：紅編號(hào) 2，白編號(hào) 4 。結(jié)果證明甲乙丙三人各猜中了一半。寫(xiě)出四色球在盒子中放置情況及推理過(guò)程。寫(xiě)出四色球在盒子中放置情況及推理過(guò)程。二、根據(jù)根據(jù)題目要求，補(bǔ)充完善以下偽代碼程序： 求出所有滿足下列條件的二位數(shù)：將此二位數(shù)的個(gè)位數(shù)字與十位數(shù)字進(jìn)行交換，可得到一個(gè)新的數(shù)，要求新數(shù)與原數(shù)之和小于 100。程序要求程序要求：每行輸出 6 個(gè)滿足條件的數(shù)。 算法提要算法提要 分解每一個(gè)二位數(shù)，然后重新組成一個(gè)新數(shù)，當(dāng)滿足條件時(shí)，用計(jì)數(shù)器來(lái) 統(tǒng)計(jì)個(gè)數(shù)。

7、 程序： K := 0; FOR i := _ TO 99 DO X := _; Y := _; J := x * 10 + y; IF _ THEN K := k + 1; Write(I : 4); _ THEN WRITELN; ENDIF ENDFOR; 找出小于 33 的 6 個(gè)正整數(shù)，用這些整數(shù)進(jìn)行加法運(yùn)算，使得包括原來(lái)的整數(shù)在內(nèi)能組成盡可能多的不同整數(shù)。 例如：用 2，3，5 這三個(gè)數(shù)能可組成下面的數(shù) 2, 3, 5 2 + 3 = 5, 但 5 已經(jīng)存在 2 + 5 = 7, 3 + 5 = 8, 2 + 3 + 5 = 10 所以用 2，3，5 能組成 6 個(gè)不同的數(shù)。 程序

8、要求：程序要求：輸出所選的這 6 個(gè)數(shù)，以及能組成不同整數(shù)的個(gè)數(shù)。 算法提要算法提要 ：選擇的這 6 個(gè)數(shù)，用來(lái)組成數(shù)時(shí)應(yīng)該盡可能不重復(fù)，引入數(shù)組 A 保存找出的這 6 個(gè)整數(shù)。 程序： A1 := 1; t := 0; For i := 2 to 6 do _; for j := 1 to i - 1 do s := _; ENDFOR; ai := _; ENDFOR; FOR i:=1 TO 6 DO T := _ WRITE(ai, ); ENDFOR; Writeln(能組成不同整數(shù)的個(gè)數(shù)：, t) End. 求出 21000 之間長(zhǎng)度最長(zhǎng)的、成等差數(shù)列的素?cái)?shù)（質(zhì)數(shù)） 。 例如：在

9、250 之間的全部素?cái)?shù)有 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 其中公差為 1 的素?cái)?shù)數(shù)列為 2, 3，其長(zhǎng)度為 2 公差為 2 的素?cái)?shù)數(shù)列為 3, 5, 7，其長(zhǎng)度為 3 程序要求：程序要求：輸出滿足條件的素?cái)?shù)數(shù)列。 算法提要算法提要 ：首先用篩選法求出此范圍內(nèi)的全部素?cái)?shù)，存放在數(shù)組 B 中，然后用 2個(gè)變量 i,j，逐步求出滿足條件的素?cái)?shù)數(shù)列。 程序: Max := 0; num := 1000; For i := 2 to num do bi := i; ENDFOR For i := 2 to _ do If _

10、then k := i + i; While k = num do Bk := 0; K := k + i ENDWHILE; ENDIF; ENDFOR; For i := 2 to num - 1 do If _ then J := 1; Dj := bi; For i1 := _ do If bi1 0 then Delta := _; k := delta; While (i+k max then begin Max := j; C :=d /數(shù)組 D 的每個(gè)元素值 分別送放數(shù)組 C 的相應(yīng) 元素中去/ ENDIF; J := 1 ENDIF; ENDFOR; ENDIF; ENDFO

11、R; writeln(The max length is: , max); write(The string is: ); for i := 1 to max do write(ci, ); writeln ENDFOR; 求出二個(gè)整形數(shù)組錯(cuò)位相加的最大面積。 1數(shù)組面積的定義：（限定數(shù)組頭尾不為 0） 設(shè)有一個(gè)數(shù)組 C=（4，8，12，0，6） 則 C 的面積為： Sc=(4+8)/2 + (8+12)/2 + 12/2 + 6/2也就是說(shuō)，Sc=各梯形面積之和（其中梯形的高約定為 1，三角形作為梯形的特殊情況處理） 。 又如 D=(12, 24, 6)時(shí)，其面積的定義為 Sd=(12+24

12、)/2 + (24+6)/2 2數(shù)組錯(cuò)位相加的定義 設(shè)有 2 個(gè)正整數(shù)的數(shù)組 a，b，長(zhǎng)度為 n，當(dāng) n=5 時(shí)： a=(34,26,15,44,12) b=(23,46,4,0,18) 對(duì) a、b 進(jìn)行錯(cuò)位相加，可能有下列情況 34 26 15 44 12 +) 23 46 4 0 18 34 26 15 44 12 23 46 4 0 18 或： 34 26 15 44 12 +） 23 46 4 0 18 - 34 26 15 44 35 46 4 0 18 或： 34 26 15 44 12 +） 23 46 4 0 18 34 26 15 67 58 4 0 18 或： 最后有： 3

13、4 26 15 44 12 +) 23 46 4 0 18 - 23 46 4 0 18 34 26 15 44 12 可以看到：由于錯(cuò)位不同，相加的結(jié)果也不同。 程序要求：程序要求：找出一個(gè)錯(cuò)位相加的方案，使得輸出的數(shù)組面積為最大。 算法提要算法提要 ： 設(shè) a，b 的長(zhǎng)度為 10，用 a,b: array1.10 of integer 表示，其結(jié)果用數(shù)組C,D: array1.30 of integer 表示。 錯(cuò)位相加的過(guò)程可以從開(kāi)始不重疊，然后逐步重疊，再到最后的不重疊。 梯形面積的計(jì)算公式為：(上底+下底)高2 其中由于約定高為 1，故可寫(xiě)為(上底+下底)2。122464812161

14、1111 程序： n = 10; Function sea : real; 計(jì)算數(shù)組 C 面積 Begin J1 := 1; While _ do j1 := j1 + 1; ENDWHILE; If j1 = 3 * n then sea := 0 Else begin J2 := 3 * n; While _ do j2 := j2 - 1; If j1 = j2 then sea := 0 Else begin J3 := cj1 + cj2; For j4 := j1 + 1 to j2 - 1 do INC(j3,cj4*2); ENDFOR; Sea := j3 / 2 end E

15、NDIF; End; /主程序/ For i := 1 to n do read(aI); endfor; For j := 1 to n do read(bj); endfor; _; for i := 1 to 2 * n + 1 do for j := 1 to 3 * n do _ endfor; for j := 1 to n do cj + n := aj endfor; for j := 1 to n do _; endfor; p := sea; if p s then begin d := c; s := p end; endif; endfor; for I := 1 to

16、 3 * n do write(dI, ); endfor; write(s); End. /主程序結(jié)束/NOI95 “同創(chuàng)杯同創(chuàng)杯”全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克競(jìng)賽全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克競(jìng)賽分區(qū)聯(lián)賽初賽試題（初中組）分區(qū)聯(lián)賽初賽試題（初中組） 試題參考答案試題參考答案一、基礎(chǔ)題：共 34 分 本題共 4 分顯示結(jié)果不相同，和比多出一個(gè)文件目錄。 本題共 5 分所表示的公式是：E=1+X/1！+ X2/2！+ X3/3！+ X10/10！ 本題共 7 分列出的算法是： K：=0 FOR i：=0 TO 10 DO K：=K+（50-I*5） DIV 2+1； ENDFOR；

17、本題共 10 分（1）k 和 i，j 之間的關(guān)系表示為：4% k:=(i-1)*i/2+j（2）給定 k 值后，決定相應(yīng)的 i,j 值的算法為：6%j:=k;i:=1; While ji do j:=j-I; i:=i+1; Endwhile; 本題共 8 分四色球在盒子中放置的情況為：4%1234黑紅白黃推理過(guò)程是：4%假定： 黑為 1 黃為 2黑為 2 白為 3紅為 2 白為 4黃為 4 二、根據(jù)題日要求，補(bǔ)充完善以下偽代碼程序：（共 66 分） 共 10 分（每空二分） for i:=10 to 99 do x:=i mod 10; y:=i div 10; If (i+j)100 if k mod 6=0