noip競賽試題1995題目

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

2、掉 X 的小數(shù)部分：如TRUNC(6.3)=6ROUND(X) ：函數(shù)值是小數(shù)四舍五入后的整數(shù)值。ABS(-3.14)=3.14SQR（ -15） =225SQRT(225)=15TRUNC(-7.9)=-7如： ROUND(3.14)=3ROUND(3.16)=4ROUND(-3.14)=-4ORD(X) ：函數(shù)值是字符在ASCII 碼中的序號。如： ORD( A )=65 ORD( B )=66 ORD( Z )=90ORD( 0 )=48CHR(X) ： X 表示 ASCII 碼中的序號，函數(shù)值是該序號代表的字符值。如： CHR(48)= 0 CHR(65)= A CHR(90)= Z

3、（ 5）過程：DEC(A,X) ：變量遞減，A 為有序變量，X 缺省時(shí)為1。INC(A,X) ：變量遞增，A 為有序變量，X 缺省時(shí)為1。一、基礎(chǔ)題： 執(zhí)行 CDIR命令后，屏幕上顯示如下畫面：FORMATCOM12145SYSCOM4878PUCBAT126XCOPYEXE112164 FILE （ S）123456bytesfree接著又順序執(zhí)行了如下幾條 CDIRDF.TXTCTYPEDF.TXTCDIRDOS 命令：/表示將列表顯示的目錄作為文件寫盤/試問 :執(zhí)行命令 和 在屏幕上顯示的結(jié)果是否與相同 ?請將以下程序段表示的計(jì)算公式寫出來（假設(shè)E：=1 ；A：=1 ；X 的值已給出）F

4、ORN：=1TOA ： =A*X/NE： =E+A；ENDFOR；10；DO寫出所表示的公式。 列舉一個(gè)算法，使算法的解能對應(yīng)相應(yīng)的問題。例如，設(shè)問題為：學(xué)生答題，答對一題可得 10 分，答錯(cuò)一題則要扣去 5 分，輸入答對的題數(shù)（ M ）與答錯(cuò)的題數(shù)（ N ），求最后得分（ S）是多少？列舉出相應(yīng)算法為：X ： =10；Y：=5；READ （ M ，N ）；S： =X*M-Y*N；現(xiàn)有以下問題：用五角錢換成5 分、 2 分與 1 分的硬幣，可有多少種換法？請列出該問題的算法。 已知如下N*(N+1)/2 個(gè)數(shù)據(jù)，按行的順序存入數(shù)組A1 ， A2 ，中：a11a21a22a31a32a33an1

5、an2an3ann其中：第一個(gè)下標(biāo)表示行第二個(gè)下標(biāo)表示列。若： aij(i j,j,i=1,2,存貯在 n) Ak 中，試問：（ 1）k 和 i， j 之間的關(guān)系如何表示？（ 2）給定 k 值（ kn*(n+1)/2)后，寫出能決定相應(yīng)的i，j值的算法。 有紅、黃、黑、白四色球各一個(gè)，放置在一個(gè)內(nèi)存編號為1、2、3、4 四個(gè)格子的盒中，每個(gè)格子放置一只球，它們的順序不知。甲、乙、丙三人猜測放置順序如下：甲：黑編號1，黃編號2；乙：黑編號2，白編號3；丙：紅編號2，白編號4 。結(jié)果證明甲乙丙三人各猜中了一半。寫出四色球在盒子中放置情況及推理過程。二、根據(jù)根據(jù)題目要求，補(bǔ)充完善以下偽代碼程序： 求

6、出所有滿足下列條件的二位數(shù)：將此二位數(shù)的個(gè)位數(shù)字與十位數(shù)字進(jìn)行交換，可得到一個(gè)新的數(shù)，要求新數(shù)與原數(shù)之和小于100。程序要求：每行輸出6 個(gè)滿足條件的數(shù)。 算法提要 分解每一個(gè)二位數(shù)，然后重新組成一個(gè)新數(shù)，當(dāng)滿足條件時(shí)，用計(jì)數(shù)器來統(tǒng)計(jì)個(gè)數(shù)。程序：K:=0;FOR i := _ _X := _;J := x * 10 + y;IF _ _K := k + 1;Write(I: 4);TO99DOY := _;THEN_ _THEN WRITELN;ENDIFENDFOR; 找出小于33 的 6 個(gè)正整數(shù)，用這些整數(shù)進(jìn)行加法運(yùn)算，使得包括原來的整數(shù)在內(nèi)能組成盡可能多的不同整數(shù)。例如：用 2， 3，

7、5 這三個(gè)數(shù)能可組成下面的數(shù)2,3,52+3=5,2+5=7,但 5 已經(jīng)存在3+5=8,2+3+5=10所以用 2， 3， 5 能組成 6 個(gè)不同的數(shù)。程序要求：輸出所選的這6 個(gè)數(shù)，以及能組成不同整數(shù)的個(gè)數(shù)。算法提要 ：選擇的這6 個(gè)數(shù)，用來組成數(shù)時(shí)應(yīng)該盡可能不重復(fù)，6程序：A1:= 1; t := 0;For i := 2 to 6 do_;for j := 1 to i - 1 do引入數(shù)組A 保存找出s := _;ENDFOR;ai := _;ENDFOR;FOR i:=1 TO 6DOT := _WRITE(ai, );ENDFOR;Writeln( 能組成不同整數(shù)的個(gè)數(shù)：, t)

8、End. 求出 21000 之間長度最長的、成等差數(shù)列的素?cái)?shù)（質(zhì)數(shù)）。例如：在 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，其長度為 2公差為 2的素?cái)?shù)數(shù)列為3,5, 7，其長度為 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 dobi := i;ENDFORFor i := 2t

9、o_ doIf_thenk := i + i;While k = num doBk:= 0;K := k + iENDWHILE;ENDIF;ENDFOR;For i := 2tonum - 1 doIf _thenJ:=1;Dj:= bi;For i1 := _doIfbi1 0 thenDelta := _;k := delta;While(i+kmax then beginMax := j;C :=d/ 數(shù)組 D 的每個(gè)元素值分別送放數(shù)組C 的相應(yīng)元素中去 /ENDIF;J:=1ENDIF;ENDFOR;ENDIF;ENDFOR;writeln(Themax length is: , m

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

11、設(shè)有 2 個(gè)正整數(shù)的數(shù)組a， b，長度為n，當(dāng) n=5 時(shí)：a=(34,26,15,44,12)b=(23,46,4,0,18)對 a、b 進(jìn)行錯(cuò)位相加，可能有下列情況3426154412+)23464018342615441223464018或：3426154412+）23464018-3426154435464018或：3426154412+）2346401834261567584018或：最后有：3426154412+)23464018-234640183426154412可以看到：由于錯(cuò)位不同，相加的結(jié)果也不同。程序要求：找出一個(gè)錯(cuò)位相加的方案，使得輸出的數(shù)組面積為最大。 算法提要 ：

12、 設(shè) a，b 的長度為10，用 a,b: array1.10of integer 表示，其結(jié)果用數(shù)組C,D: array1.30 of integer 表示。錯(cuò)位相加的過程可以從開始不重疊，然后逐步重疊，再到最后的不重疊。梯形面積的計(jì)算公式為：(上底 +下底 ) 高2其中由于約定高為1，故可寫為 ( 上底 +下底 ) 2。程序：n = 10;Function sea : real; 計(jì)算數(shù)組C 面積 BeginJ1 := 1;While _ doj1 := j1 + 1;ENDWHILE;Ifj1 = 3 *nthen sea := 0Else beginJ2 := 3 * n;While _doj2 := j2 - 1;Ifj1 = j2then sea := 0Else beginJ3 := cj1+ cj2;Forj4 := j1 + 1 to j2 -1 doINC(j3,cj4*2);ENDFOR;Sea := j3 / 2endENDIF;End;/ 主程序 /Fori := 1 to n do read(aI);endfor;Forj := 1 to n do read(bj);endfor;_ _;fori := 1 to 2 * n + 1 doforj := 1