2013寧波小學(xué)生程序設(shè)計(jì)試卷解題報(bào)告by slzxlzw

1、問(wèn)題 E: 哈夫曼編碼（coding.pas）題目描述哈夫曼編碼是一種編碼方式， 是可變字長(zhǎng)編碼的一種， 由 Huffman 于 1952 年提出。該方法完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)造異字頭的平均長(zhǎng)度最短的碼字， 有時(shí)稱之為最佳編碼，一般就叫 Huffman 編碼。簡(jiǎn)單地來(lái)說(shuō)，就是出現(xiàn)概率高的字符使用較短的編碼， 反之出現(xiàn)概率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均期望長(zhǎng)度降低， 從而達(dá)到無(wú)損壓縮數(shù)據(jù)的目的?，F(xiàn)在請(qǐng)你模擬這樣的原則對(duì)給定的一個(gè)字符串進(jìn)行字母統(tǒng)計(jì)。輸入輸入文件 coding.in，只有一行，是一個(gè)字符串，由小寫英文字母組成，長(zhǎng)度不超過(guò)255 個(gè)字符。輸出輸出文件 codin

2、g.out，有若干行，每行有兩部分組成：一個(gè)字母和該字母出現(xiàn)的頻率，中間用一個(gè)空格分隔，并按頻率高低排列，頻率相同時(shí)則按字母的 ASC 碼的先后順序排列。樣例輸入soon樣例輸出o 2n 1s 1提示【題目分析】 給出一段字符串，在字符串中出現(xiàn)的字符按出現(xiàn)次數(shù)從多到少輸出，出現(xiàn)次數(shù)一樣按字母表順序輸出?！舅惴ǚ治觥磕M。開(kāi)一個(gè)記錄字符出現(xiàn)次數(shù)的數(shù)組，然后按照題意輸出?！緟⒖汲绦颉縱ar ch:char;a:array'a'.'z'of longint;max,i:longint;begin while not eoln do begin read(ch); in

3、c(ach); /記錄出現(xiàn)次數(shù) if ach>max then max:=ach; /記錄出現(xiàn)最大出現(xiàn)次數(shù) end; for i:=max downto 1 do /按出現(xiàn)次數(shù)從大到小輸出 for ch:='a' to 'z' do /相同的按字母表順序輸出 if ach=i then writeln(ch,' ',ach); end.問(wèn)題 F: 立方和（cubsum.pas）時(shí)間限制: 1 Sec  內(nèi)存限制: 128 MB提交: 37  解決: 21提交狀態(tài)討論版題目描述現(xiàn)給出一個(gè)三位數(shù)， 先對(duì)這

4、個(gè)三位數(shù)的各位數(shù)字的立方求和，然后再對(duì)求出的和中的各位數(shù)字的立方求和， 如此一直繼續(xù)下去， 判斷最后能否得到一個(gè)不再變化的固定值。如能得到一個(gè)固定值，就求出這個(gè)固定值；如果不能，則輸出提示信息“error” 。另外請(qǐng)注意，在求解過(guò)程中，若某一次求和過(guò)程中得到的值超過(guò)三位數(shù)，則取該數(shù)的低三位繼續(xù)往下運(yùn)算例如，對(duì)于三位數(shù) 111，則第一次計(jì)算應(yīng)是 1×1×1+1×1×1+1×1×1=3，第二次計(jì)算應(yīng)是 0×0×0+0×0×0+3×3×3=27，第三次計(jì)算應(yīng)是0×0

5、15;0+2×2×2+7×7×7=351，第四次計(jì)算應(yīng)是 3×3×3+5×5×5+1×1×1=153，第五次計(jì)算應(yīng)是 1×1×1+5×5×5+3×3×3=153，與第四次計(jì)算的結(jié)果相同，這時(shí)可不再計(jì)算，輸出固定值 153。親愛(ài)的同學(xué)，請(qǐng)你也來(lái)計(jì)算一下。輸入輸入文件 cubsum.in，只有一行，是一個(gè)三位數(shù)。輸出輸出文件 cubsum.out，也只有一行，如能得到一個(gè)固定值，則輸出這個(gè)固定值；如不能，則輸出一個(gè)提示信息“error” 。

6、樣例輸入111樣例輸出153提示輸入樣例 2：102輸出樣例 2：error【題目分析】 對(duì)一個(gè)三位數(shù)字（多于三位取最低三位，少于三位添零計(jì)算）進(jìn)行各個(gè)數(shù)位立方求和。判斷是否最后變成一個(gè)固定的數(shù)?！舅惴ǚ治觥繉?duì)于一個(gè)固定不變的數(shù)，則是與前一次相同，就是求立方和前相同。而沒(méi)有固定值的數(shù)，則是在前面所有變化的數(shù)中出現(xiàn)過(guò)（當(dāng)然排除前一次），因?yàn)闀?huì)形成一個(gè)循環(huán)。像這樣我們只要開(kāi)一個(gè)記錄是否出現(xiàn)過(guò)某個(gè)數(shù)的數(shù)組（0.1000）(不包括前一次），如果出現(xiàn)過(guò)就沒(méi)有固定值。最壞情況也就o(1000),是個(gè)常數(shù)?！緟⒖汲绦颉縱ar x,y,t:longint;a:Array0.10000of boolean;be

7、gin read(x); repeat t:=x; /保存一遍，因?yàn)橄旅鎥會(huì)變 y:=sqr(x mod 10)*(x mod 10); /求立方和 x:=x div 10; y:=y+sqr(x mod 10)*(x mod 10); x:=x div 10; y:=y+sqr(x mod 10)*(x mod 10); if y=t then begin writeln(y);halt;end; /求立方和與前一次相等就輸出。 if ay then begin writeln('error');halt;end; /出現(xiàn)過(guò)這個(gè)數(shù) ay:=true; /這個(gè)數(shù)出現(xiàn)過(guò) x:=y

8、; until false;End.問(wèn)題 G: 智力大獎(jiǎng)賽（energy.pas）時(shí)間限制: 1 Sec  內(nèi)存限制: 128 MB提交: 59  解決: 34提交狀態(tài)討論版題目描述一年一度的校園智力大獎(jiǎng)賽是小明最喜愛(ài)的活動(dòng)， 今年的比賽中學(xué)校新設(shè)了一個(gè)智取能量棒的項(xiàng)目，小明很想?yún)⒓?。這個(gè)項(xiàng)目的比賽規(guī)則是這樣的：考官在一個(gè)儀器上輸入一個(gè)數(shù)， 儀器屏幕上就會(huì)出現(xiàn)一個(gè)由許多能量棒組成的大三角形（一個(gè)大三角形有若干個(gè)小三角形組成） ，已知每根能量棒的長(zhǎng)度都是一樣的，每個(gè)小三角形由三根能量棒組成，若誰(shuí)能快速答出其中小三角形的個(gè)數(shù)和能量棒的總個(gè)數(shù)，則誰(shuí)就贏得了比賽

9、， 這些能量棒作為獎(jiǎng)勵(lì)也就屬于他了?，F(xiàn)在小明想邀請(qǐng)你和他一起參加這項(xiàng)比賽。輸入輸入文件 energy.in，只有一行，有一個(gè)整數(shù) N，表示大三角形的層數(shù)（N45000）輸出輸出文件 energy.out，有二行。第一行只有一個(gè)數(shù)，表示小三角形的個(gè)數(shù)；第二行也只有一個(gè)數(shù)，表示能量棒的個(gè)數(shù)。樣例輸入8樣例輸出64108提示在 40%的數(shù)據(jù)中，1N150在 70%的數(shù)據(jù)中，1N30000在 100%的數(shù)據(jù)中，1N45000【題目分析】求組成如圖的邊長(zhǎng)為n的等邊三角形要多少個(gè)小三角形和多少木棒【算法分析】小三角形個(gè)數(shù)：仔細(xì)觀察，第一行只有一個(gè)三角形，最后一行有2n-1個(gè)三角形，而每?jī)尚兄g只相差兩個(gè)三

10、角形，這樣我們就可以用等差數(shù)列求和的公式（1+2n-1)*n/2木棒個(gè)數(shù)：我們可以看成第i行有i個(gè)三角形，每個(gè)三角形占3根棒。而每行也是等差的，所以也可以用等差數(shù)列的公式（1+n)n/2*3【參考程序】var x:int64;begin read(x); writeln(1+x*2-1)*x div 2); writeln(1+x)*x div 2*3);End.問(wèn)題 H: 求素?cái)?shù)（prime.pas）時(shí)間限制: 1 Sec  內(nèi)存限制: 128 MB提交: 29  解決: 13提交狀態(tài)討論版題目描述現(xiàn)給你 N 個(gè) 09 的數(shù)字并排成了一列，同時(shí)還給出了

11、一個(gè)取數(shù)長(zhǎng)度 L。規(guī)定先從第 1 個(gè)數(shù)字開(kāi)始從左往右連續(xù)取 L 個(gè)數(shù)字， 拼成一個(gè)長(zhǎng)度為 L 位 （最高位為 0 的 L-1 位數(shù)除外）的數(shù)，然后從第 2 個(gè)數(shù)字開(kāi)始從左往右連續(xù)取 L 個(gè)數(shù)字，這樣，最后最多可以得到 N-L+1 個(gè) L 位數(shù)。 現(xiàn)在請(qǐng)你將這些 L 位數(shù)中的素?cái)?shù)按從小到大的順序輸出 （如果產(chǎn)生重復(fù)，只需輸出一個(gè)） 。輸入輸入文件 prime.in，共有二行。第一行為 N 和 L，中間用空格隔開(kāi)。(1N100，1L7)第二行為 N 個(gè) 09 的數(shù)字，中間用空格隔開(kāi)。輸出輸出文件 prime.out，只有一行，含全部滿足條件的素?cái)?shù)，中間用逗號(hào)隔開(kāi)。樣例輸入10 38 9 1 0 2

12、 3 5 4 7 6樣例輸出547提示【題目分析】給出n個(gè)數(shù)，連續(xù)的取L個(gè)數(shù)組成一組數(shù)（開(kāi)頭不能為0),求其中為素?cái)?shù)的數(shù)，要去重復(fù)，輸出從小到大，且中間以逗號(hào)隔開(kāi)?！舅惴ǚ治觥磕M。從每個(gè)位置開(kāi)始取，判斷是否為素?cái)?shù)，是素?cái)?shù)就判斷有無(wú)重復(fù)出現(xiàn)，無(wú)重復(fù)出現(xiàn)就加入數(shù)列中，然后排序，最后輸出。【參考程序】var n,l,x,s,i,j:longint;b,a:array0.10000of longint;function pd(x:longint):boolean;var i:longint;begin if x<2 then exit(false); for i:=2 to trunc(sqrt(x)do if x mod i=0 then exit(false); exit(true);end;begin readln(n,l); for i:=1 to n do reaD(ai); for i:=1 to n-l+1 do if ai>0 then /首位字母不能為0 begin x:=0; for j:=i to i+l-1 do x:=x*10+aj; if pd(x) then /判斷是否為素?cái)?shù) begin for j:=1 to s do /去重復(fù) if x=bj then break; if x=bj then continue; s:=s+1;bs:=