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

問題E:哈夫曼編碼(coding.pas)題目描述哈夫曼編碼是一種編碼方式，是可變字長編碼的一種，由Huffman于1952年提出。該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時(shí)稱之為最佳編碼，一般就叫Huffman編碼。簡單地來說，就是出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長的編碼，這便使編碼之后的字符串的平均期望長度降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的?，F(xiàn)在請(qǐng)你模擬這樣的原則對(duì)給定的一個(gè)字符串進(jìn)行字母統(tǒng)計(jì)。輸入輸入文件coding.in,只有一行，是一個(gè)字符串，由小寫英文字母組成，長度不超過255個(gè)字符。輸出輸出文件coding.out，有若干行，每行有兩部分組成：一個(gè)字母和該字母出現(xiàn)的頻率，中間用一個(gè)空格分隔，并按頻率高低排列，頻率相同時(shí)則按字母的ASC碼的先后順序排列。樣例輸入soon樣例輸出o2n1s1提示【題目分析】給出一段字符串，在字符串中出現(xiàn)的字符按出現(xiàn)次數(shù)從多到少輸出，出現(xiàn)次數(shù)一樣按字母表順序輸出?！舅惴ǚ治觥磕M。開一個(gè)記錄字符出現(xiàn)次數(shù)的數(shù)組，然后按照題意輸出?！緟⒖汲绦颉縱arch:char;a:array['a'..'z']oflongint;max,i:longint;beginwhilenoteolndobeginread(ch);inc(a[ch]);//記錄出現(xiàn)次數(shù)ifa[ch]>maxthenmax:=a[ch];//記錄出現(xiàn)最大出現(xiàn)次數(shù)end;fori:=maxdownto1do//按出現(xiàn)次數(shù)從大到小輸出forch:='a'to'z'do//相同的按字母表順序輸出ifa[ch]=ithenwriteln(ch,'',a[ch]);end.問題F:立方和(cubsum.pas)時(shí)間限制:1Sec內(nèi)存限制:128MB提交:37解決:21[提交][狀態(tài)][討論版]題目描述現(xiàn)給出一個(gè)三位數(shù)，先對(duì)這個(gè)三位數(shù)的各位數(shù)字的立方求和，然后再對(duì)求出的和中的各位數(shù)字的立方求和，如此一直繼續(xù)下去，判斷最后能否得到一個(gè)不再變化的固定值。如能得到一個(gè)固定值，就求出這個(gè)固定值；如果不能，則輸出提示信息“error”。另外請(qǐng)注意，在求解過程中，若某一次求和過程中得到的值超過三位數(shù)，則取該數(shù)的低三位繼續(xù)往下運(yùn)例如，對(duì)于三位數(shù)111,則第一次計(jì)算應(yīng)是1x1x1+1x1x1+1x1x1=3,第二次計(jì)算應(yīng)是0乂0乂0+0乂0乂0+3乂3乂3=27，第三次計(jì)算應(yīng)是0x0x0+2x2x2+7x7x7=351，第四次計(jì)算應(yīng)是3x3x3+5x5x5+1x1x1=153，第五次計(jì)算應(yīng)是1x1x1+5x5x5+3x3x3=153，與第四次計(jì)算的結(jié)果相同，這時(shí)可不再計(jì)算，輸出固定值153。親愛的同學(xué)，請(qǐng)你也來計(jì)算一下。輸入輸入文件cubsum.in，只有一行，是一個(gè)三位數(shù)。輸出輸出文件cubsum.out,也只有一行，如能得到一個(gè)固定值，則輸出這個(gè)固定值；如不能，則輸出一個(gè)提示信息“error”。樣例輸入111樣例輸出153提示輸入樣例2：102輸出樣例2：error【題目分析】對(duì)一個(gè)三位數(shù)字(多于三位取最低三位，少于三位添零計(jì)算)進(jìn)行各個(gè)數(shù)位立方求和。判斷是否最后變成一個(gè)固定的數(shù)?！舅惴ǚ治觥繉?duì)于一個(gè)固定不變的數(shù)，則是與前一次相同，就是求立方和前相同。而沒有固定值的數(shù)，則是在前面所有變化的數(shù)中出現(xiàn)過(當(dāng)然排除前一次)，因?yàn)闀?huì)形成一個(gè)循環(huán)。像這樣我們只要開一個(gè)記錄是否出現(xiàn)過某個(gè)數(shù)的數(shù)組(0..1000)(不包括前一次)，如果出現(xiàn)過就沒有固定值。最壞情況也就0(1000)，是個(gè)常數(shù)?！緟⒖汲绦颉縱arx,y,t:longint;a:Array[0..10000]ofboolean;beginread(x);repeatt:=x;〃保存一遍，因?yàn)橄旅鎥會(huì)變y:=sqr(xmod10)*(xmod10);//求立方和x:=xdiv10;y:=y+sqr(xmod10)*(xmod10);x:=xdiv10;y:=y+sqr(xmod10)*(xmod10);ify=tthenbeginwriteln(y);halt;end;//求立方和與前一次相等就輸出。ifa[y]thenbeginwriteln('error');halt;end;//出現(xiàn)過這個(gè)數(shù)a[y]:=true;//這個(gè)數(shù)出現(xiàn)過x:=y;untilfalse;End.問題G:智力大獎(jiǎng)賽（energy.pas）時(shí)間限制:1Sec內(nèi)存限制:128MB提交:59解決:34［提交］［狀態(tài)］［討論版］題目描述一年一度的校園智力大獎(jiǎng)賽是小明最喜愛的活動(dòng)，今年的比賽中學(xué)校新設(shè)了一個(gè)智取能量棒的項(xiàng)目，小明很想?yún)⒓?。這個(gè)項(xiàng)目的比賽規(guī)則是這樣的：考官在一個(gè)儀器上輸入一個(gè)數(shù)，儀器屏幕上就會(huì)出現(xiàn)一個(gè)由許多能量棒組成的大三角形（一個(gè)大三角形有若干個(gè)小三角形組成），已知每根能量棒的長度都是一樣的，每個(gè)小三角形由三根能量棒組成，若誰能快速答出其中小三角形的個(gè)數(shù)和能量棒的總個(gè)數(shù)，則誰就贏得了比賽，這些能量棒作為獎(jiǎng)勵(lì)也就屬于他了。現(xiàn)在小明想邀請(qǐng)你和他一起參加這項(xiàng)比賽。輸入輸入文件energy.in,只有一行，有一個(gè)整數(shù)N,表示大三角形的層數(shù)（NW45000）輸出輸出文件energy.out，有二行。第一行只有一個(gè)數(shù)，表示小三角形的個(gè)數(shù)；第二行也只有一個(gè)數(shù)，表示能量棒的個(gè)數(shù)。樣例輸入8樣例輸出64108提示在40%的數(shù)據(jù)中，1WNW150在70%的數(shù)據(jù)中，1WN三30000在100%的數(shù)據(jù)中，1WN三45000【題目分析】求組成如圖的邊長為n的等邊三角形要多少個(gè)小三角形和多少木棒【算法分析】小三角形個(gè)數(shù)：仔細(xì)觀察，第一行只有一個(gè)三角形，最后一行有2n-1個(gè)三角形，而每兩行之間只相差兩個(gè)三角形，這樣我們就可以用等差數(shù)列求和的公式（1+2n-1）*n/2木棒個(gè)數(shù)：我們可以看成第i行有i個(gè)三角形，每個(gè)三角形占3根棒。而每行也是等差的，所以也可以用等差數(shù)列的公式（1+n）n/2*3【參考程序】varx:int64;beginread(x);writeln((1+x*2-1)*xdiv2);writeln((1+x)*xdiv2*3);End.問題H:求素?cái)?shù)（prime.pas）時(shí)間限制:1Sec內(nèi)存限制:128MB提交:29解決:13［提交］［狀態(tài)］［討論版］題目描述現(xiàn)給你N個(gè)0?9的數(shù)字并排成了一列，同時(shí)還給出了一個(gè)取數(shù)長度L。規(guī)定先從第1個(gè)數(shù)字開始從左往右連續(xù)取L個(gè)數(shù)字，拼成一個(gè)長度為L位（最高位為0的L-1位數(shù)除外）的數(shù)，然后從第2個(gè)數(shù)字開始從左往右連續(xù)取L個(gè)數(shù)字……，這樣，最后最多可以得到N-L+1個(gè)L位數(shù)?，F(xiàn)在請(qǐng)你將這些L位數(shù)中的素?cái)?shù)按從小到大的順序輸出（如果產(chǎn)生重復(fù)，只需輸出一個(gè)）。輸入輸入文件prime.in,共有二行。第一行為N和L,中間用空格隔開。（1WN三100,1三LW7）第二行為N個(gè)0?9的數(shù)字，中間用空格隔開。輸出輸出文件prime.out,只有一行，含全部滿足條件的素?cái)?shù)，中間用逗號(hào)隔開。樣例輸入1038910235476樣例輸出547提示【題目分析】給出n個(gè)數(shù)，連續(xù)的取L個(gè)數(shù)組成一組數(shù)（開頭不能為0）,求其中為素?cái)?shù)的數(shù)，要去重復(fù)，輸出從小到大，且中間以逗號(hào)隔開。【算法分析】是素?cái)?shù)就判斷有無重復(fù)出現(xiàn)，無重復(fù)出現(xiàn)就加模擬。從每個(gè)位置開始取，判斷是否為素?cái)?shù)，入數(shù)列中，然后排序，最后輸出。是素?cái)?shù)就判斷有無重復(fù)出現(xiàn)，無重復(fù)出現(xiàn)就加【參考程序】varn,l,x,s,i,j:longint;b,a:array[0..10000]oflongint;functionpd(x:longint):boolean;vari:longint;beginifx<2thenexit(false);fori:=2totrunc(sqrt(x))doifxmodi=0thenexit(false);exit(true);end;beginreadln(n,l);fori:=1tondoreaD(a[i]);fori:=1ton-l+1doifa[i]>0then//首位字母不能為0beginx:=0;forj:=itoi+l-1dox:=x*10+a[j];ifpd(x)then//判斷是否為素?cái)?shù)beginforj:=1tosdo//去重復(fù)ifx=b[j]thenbreak;ifx=b[j]thencontinue;s:=s+1;b[