2013寧波小學(xué)生程序設(shè)計試卷解題報告by slzxlzw.doc

問題 E: 哈夫曼編碼（coding.pas）題目描述哈夫曼編碼是一種編碼方式， 是可變字長編碼的一種， 由 Huffman 于 1952 年提出。該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字， 有時稱之為最佳編碼，一般就叫 Huffman 編碼。簡單地來說，就是出現(xiàn)概率高的字符使用較短的編碼， 反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低， 從而達到無損壓縮數(shù)據(jù)的目的?，F(xiàn)在請你模擬這樣的原則對給定的一個字符串進行字母統(tǒng)計。輸入輸入文件 coding.in，只有一行，是一個字符串，由小寫英文字母組成，長度不超過255 個字符。輸出輸出文件 coding.out，有若干行，每行有兩部分組成：一個字母和該字母出現(xiàn)的頻率，中間用一個空格分隔，并按頻率高低排列，頻率相同時則按字母的 ASC 碼的先后順序排列。樣例輸入soon樣例輸出o 2n 1s 1提示【題目分析】 給出一段字符串，在字符串中出現(xiàn)的字符按出現(xiàn)次數(shù)從多到少輸出，出現(xiàn)次數(shù)一樣按字母表順序輸出?！舅惴ǚ治觥磕M。開一個記錄字符出現(xiàn)次數(shù)的數(shù)組，然后按照題意輸出?！緟⒖汲绦颉縱ar ch:char;a:arraya.zof longint;max,i:longint;begin while not eoln do begin read(ch); inc(ach); /記錄出現(xiàn)次數(shù) if achmax 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.問題 F: 立方和（cubsum.pas）時間限制: 1 Sec內(nèi)存限制: 128 MB提交: 37解決: 21提交狀態(tài)討論版題目描述現(xiàn)給出一個三位數(shù)， 先對這個三位數(shù)的各位數(shù)字的立方求和，然后再對求出的和中的各位數(shù)字的立方求和， 如此一直繼續(xù)下去， 判斷最后能否得到一個不再變化的固定值。如能得到一個固定值，就求出這個固定值；如果不能，則輸出提示信息“error” 。另外請注意，在求解過程中，若某一次求和過程中得到的值超過三位數(shù)，則取該數(shù)的低三位繼續(xù)往下運算例如，對于三位數(shù) 111，則第一次計算應(yīng)是 111+111+111=3，第二次計算應(yīng)是 000+000+333=27，第三次計算應(yīng)是000+222+777=351，第四次計算應(yīng)是 333+555+111=153，第五次計算應(yīng)是 111+555+333=153，與第四次計算的結(jié)果相同，這時可不再計算，輸出固定值 153。親愛的同學(xué)，請你也來計算一下。輸入輸入文件 cubsum.in，只有一行，是一個三位數(shù)。輸出輸出文件 cubsum.out，也只有一行，如能得到一個固定值，則輸出這個固定值；如不能，則輸出一個提示信息“error” 。樣例輸入111樣例輸出153提示輸入樣例 2：102輸出樣例 2：error【題目分析】 對一個三位數(shù)字（多于三位取最低三位，少于三位添零計算）進行各個數(shù)位立方求和。判斷是否最后變成一個固定的數(shù)?！舅惴ǚ治觥繉τ谝粋€固定不變的數(shù)，則是與前一次相同，就是求立方和前相同。而沒有固定值的數(shù)，則是在前面所有變化的數(shù)中出現(xiàn)過（當然排除前一次），因為會形成一個循環(huán)。像這樣我們只要開一個記錄是否出現(xiàn)過某個數(shù)的數(shù)組（0.1000）(不包括前一次），如果出現(xiàn)過就沒有固定值。最壞情況也就o(1000),是個常數(shù)。【參考程序】var x,y,t:longint;a:Array0.10000of boolean;begin read(x); repeat t:=x; /保存一遍，因為下面x會變 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)過這個數(shù) ay:=true; /這個數(shù)出現(xiàn)過 x:=y; until false;End.問題 G: 智力大獎賽（energy.pas）時間限制: 1 Sec內(nèi)存限制: 128 MB提交: 59解決: 34提交狀態(tài)討論版題目描述一年一度的校園智力大獎賽是小明最喜愛的活動， 今年的比賽中學(xué)校新設(shè)了一個智取能量棒的項目，小明很想?yún)⒓印＿@個項目的比賽規(guī)則是這樣的：考官在一個儀器上輸入一個數(shù)， 儀器屏幕上就會出現(xiàn)一個由許多能量棒組成的大三角形（一個大三角形有若干個小三角形組成） ，已知每根能量棒的長度都是一樣的，每個小三角形由三根能量棒組成，若誰能快速答出其中小三角形的個數(shù)和能量棒的總個數(shù)，則誰就贏得了比賽， 這些能量棒作為獎勵也就屬于他了?，F(xiàn)在小明想邀請你和他一起參加這項比賽。輸入輸入文件 energy.in，只有一行，有一個整數(shù) N，表示大三角形的層數(shù)（N45000）輸出輸出文件 energy.out，有二行。第一行只有一個數(shù)，表示小三角形的個數(shù)；第二行也只有一個數(shù)，表示能量棒的個數(shù)。樣例輸入8樣例輸出64108提示在 40%的數(shù)據(jù)中，1N150在 70%的數(shù)據(jù)中，1N30000在 100%的數(shù)據(jù)中，1N45000【題目分析】求組成如圖的邊長為n的等邊三角形要多少個小三角形和多少木棒【算法分析】小三角形個數(shù)：仔細觀察，第一行只有一個三角形，最后一行有2n-1個三角形，而每兩行之間只相差兩個三角形，這樣我們就可以用等差數(shù)列求和的公式（1+2n-1)*n/2木棒個數(shù)：我們可以看成第i行有i個三角形，每個三角形占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.問題 H: 求素數(shù)（prime.pas）時間限制: 1 Sec內(nèi)存限制: 128 MB提交: 29解決: 13提交狀態(tài)討論版題目描述現(xiàn)給你 N 個 09 的數(shù)字并排成了一列，同時還給出了一個取數(shù)長度 L。規(guī)定先從第 1 個數(shù)字開始從左往右連續(xù)取 L 個數(shù)字， 拼成一個長度為 L 位 （最高位為 0 的 L-1 位數(shù)除外）的數(shù)，然后從第 2 個數(shù)字開始從左往右連續(xù)取 L 個數(shù)字，這樣，最后最多可以得到 N-L+1 個 L 位數(shù)。 現(xiàn)在請你將這些 L 位數(shù)中的素數(shù)按從小到大的順序輸出 （如果產(chǎn)生重復(fù)，只需輸出一個） 。輸入輸入文件 prime.in，共有二行。第一行為 N 和 L，中間用空格隔開。(1N100，1L7)第二行為 N 個 09 的數(shù)字，中間用空格隔開。輸出輸出文件 prime.out，只有一行，含全部滿足條件的素數(shù)，中間用逗號隔開。樣例輸入10 38 9 1 0 2 3 5 4 7 6樣例輸出547提示【題目分析】給出n個數(shù)，連續(xù)的取L個數(shù)組成一組數(shù)（開頭不能為0),求其中為素數(shù)的數(shù)，要去重復(fù)，輸出從小到大，且中間以逗號隔開?！舅惴ǚ治觥磕M。從每個位置開始取，判斷是否為素數(shù)，是素數(shù)就判斷有無重復(fù)出現(xiàn)，無重復(fù)出現(xiàn)就加入數(shù)列中，然后排序，最后輸出?！緟⒖汲绦颉縱ar n,l,x,s,i,j:longint;b,a:array0.10000of longint;function pd(x:longint):boolean;var i:longint;begin if x0 then /首位字母不能為0 begin x:=0; for j:=i to i+l-1 do x:=x*10+aj; if pd(x) then /判斷是否為素數(shù) begin for j:=1 to s do /去重復(fù) if x=bj then break; if x=bj then continue; s:=s+1;bs:=x; end;