信息學(xué)奧賽基礎(chǔ)知識(shí)講解

信息學(xué)奧賽基礎(chǔ)知識(shí)講解第一頁(yè)，共一百一十三頁(yè)，2022年，8月28日精心備課，突破疑點(diǎn)難點(diǎn)，追求直觀(guān)高效。第二頁(yè)，共一百一十三頁(yè)，2022年，8月28日

分析：將十進(jìn)數(shù)轉(zhuǎn)換成二進(jìn)制數(shù),一般采用除二取余法。如果用一個(gè)數(shù)組b來(lái)存放二進(jìn)制數(shù),可以依次把所得的余數(shù)存入b[0]、b[1]、…、b[n],最后按b[n]、b[n-1]、…、b[1]、b[0]的順序輸出這些余數(shù),就得到了所求的二進(jìn)制數(shù)。

1、讀入一個(gè)十進(jìn)制自然數(shù)，將其轉(zhuǎn)換成二進(jìn)制數(shù)后輸出。第三頁(yè)，共一百一十三頁(yè)，2022年，8月28日例如：余數(shù)：2521226232120輸出結(jié)果為：11001010110123456第四頁(yè)，共一百一十三頁(yè)，2022年，8月28日vari,j,n:longint;b:array[0..31]of0..1;beginreadln(n);write(n,'=(');i:=0;while（）dobegin（）;i:=i+1;{指定下一個(gè)余數(shù)的存放位置}

n:=ndiv2{產(chǎn)生的商將作為新的被除數(shù)}

end;forj:=（）dowrite(b[j]);writeln(')2')end.n<>0

b[i]:=nmod2

i-1downto0

后進(jìn)先出第五頁(yè)，共一百一十三頁(yè)，2022年，8月28日Str1=‘3210’Str2=‘98765’a0123b567895791101j對(duì)位相加進(jìn)位2、高精度加法第六頁(yè)，共一百一十三頁(yè)，2022年，8月28日varstr1,str2:string;a,b:array[1..100]of0..9;l1,l2,i,j,k:integer;beginreadln(str1);readln(str2);

l1:=length(str1);l2:=length(str2);ifl1>l2thenj:=l1elsej:=l2;

k:=0;fori:=l1downto1dobegink:=k+1;a[k]:=ord(str1[i])-ord('0');end;

k:=0;fori:=l2downto1dobegink:=k+1;b[k]:=ord(str2[i])-ord('0');end;fori:=1tojdobegina[i]:=a[i]+b[i];

ifa[i]>=10thenbegin

a[i]:=（）;a[i+1]:=（）;end;end;ifa[i+1]=0thenj:=j-1;fori:=j+1downto1dowrite(a[i]);

writeln;end.處理進(jìn)位從低位到高位依次將各位數(shù)相加用字符串形式輸入加數(shù)和被加數(shù)a[i]-10a[i+1]+1第七頁(yè)，共一百一十三頁(yè)，2022年，8月28日

分析：類(lèi)似加法，可以用豎式求乘法。在做乘法運(yùn)算時(shí)，同樣也有進(jìn)位，同時(shí)對(duì)每一位進(jìn)行乘法運(yùn)算時(shí)，必須進(jìn)行錯(cuò)位相加。84823×25441696195043*8+0+0=24c[1]=4x=a[i]*b[j]+xdiv10+c[i+j-1]

c[i+j-1]=xmod103*4+2+0=14c[2]=43*8+1+0=25c[3]=5

c[4]=22*8+0+4=20c[2]=02*4+2+5=15c[3]=52*8+1+2=19c[4]=9

c[5]=13、高精度乘法第八頁(yè)，共一百一十三頁(yè)，2022年，8月28日vars1,s2:string;a,b:array[1..100]of0..9;c:array[1..200]of0..9;la,lb,lc,i,j,x,y,z,w:integer;beginreadln(s1);readln(s2);la:=length(s1);lb:=length(s2);lc:=la+lb;{積的位數(shù)為la+lb-1或者la+lb；}fori:=ladownto1doa[la-i+1]:=ord(s1[i])-ord('0');fori:=lbdownto1dob[lb-i+1]:=ord(s2[i])-ord('0');fori:=lcdownto1doc[i]:=0;fori:=1toladobeginx:=0;{上次乘積進(jìn)位初始化}

forj:=1tolbdo{對(duì)乘數(shù)的每一位進(jìn)行處理}

beginx:=a[i]*b[j]+xdiv10+c[i+j-1];c[i+j-1]:=xmod10;end;c[i+j]:=xdiv10;end;while(c[lc]=0)and(lc>1)dolc:=lc-1;

fori:=lcdownto1dowrite(c[i]);writeln;end.第九頁(yè)，共一百一十三頁(yè)，2022年，8月28日varyh:array[1..5,1..5]ofinteger;i,j:integer;beginyh[1,1]:=1;fori:=2to5dobeginyh[i,1]:=1;yh[i,i]:=1;forj:=2toi-1do

yh[i,j]:=yh[i-1,j-1]+yh[i-1,j];end;fori:=1to5dobeginforj:=1toidowrite(yh[i,j]:3);

writeln;end;end.1111121133114644、閱讀程序，寫(xiě)出運(yùn)行結(jié)果。第十頁(yè)，共一百一十三頁(yè)，2022年，8月28日5、2001年普及組、提高組初賽試題（窮舉法）在A(yíng)、B兩個(gè)城市之間設(shè)有N個(gè)路站(如下圖中的S1，且N<100)，城市與路站之間、路站和路站之間各有若干條路段(各路段數(shù)<=20，且每條路段上的距離均為一個(gè)整數(shù))。

A，B的一條通路是指：從A出發(fā)，可經(jīng)過(guò)任一路段到達(dá)S1，再?gòu)腟1出發(fā)經(jīng)過(guò)任一路段，…最后到達(dá)B。通路上路段距離之和稱(chēng)為通路距離(最大距離<=1000)。當(dāng)所有的路段距離給出之后，求出所有不同距離的通路個(gè)數(shù)(相同距離僅記一次)。

例如：下圖所示是當(dāng)N=1時(shí)的情況：從A到B的通路條數(shù)為6，但因其中通路5+5=4+6，所以滿(mǎn)足條件的不同距離的通路條數(shù)為5。

數(shù)據(jù)結(jié)構(gòu)：N記錄A，B間路站的個(gè)數(shù)；

數(shù)組D[i，0]記錄第i-1個(gè)到第i個(gè)路站間路段的個(gè)數(shù);

D[i，1]，D[i，2]，…，記錄每個(gè)路段的距離;

數(shù)組G記錄可取到的距離。第十一頁(yè)，共一百一十三頁(yè)，2022年，8月28日864537401118+4+3=15g[15]=101128+4+4=16g[16]=101218+5+3=16g[16]=101228+5+4=17g[17]=101318+7+3=18g[18]=101328+7+4=19g[19]=102116+4+3=13g[13]=102126+4+4=14g[14]=102216+5+3=14g[14]=102226+5+4=15g[15]=102316+7+3=16g[16]=102326+7+4=17g[17]=1b[0]b[1]b[2]b[3]1111窮舉結(jié)束D[1，0]=2,D[1，1]=8,D[1，2]=6D[2，0]=3,D[2，1]=4,D[2，2]=5，

D[2，3]=7D[3，0]=2,D[3，1]=3,D[3，2]=4第十二頁(yè)，共一百一十三頁(yè)，2022年，8月28日vari,j,n,s:integer;

b:array[0..100]ofinteger;

d:array[0..100,0..20]ofinteger;

g:array[0..1000]of0..1;

begin

readln(n);

fori:=1ton+1do

begin

readln(d[i,0]);

forj:=1tod[i,0]doread(d[i,j]);

end;

d[0,0]:=1;

fori:=1ton+1dob[i]:=1;

b[0]:=0;

fori:=1to1000dog[i]:=0;while()do

begin

s:=0;

fori:=1ton+1do

s:=();

g[s]:=1;

j:=n+1;

while()doj:=j-1;

b[j]:=b[j]+1;

fori:=j+1ton+1dob[i]:=1;

end;

s:=0;

fori:=1to1000do();

writeln(s);readln;

end.b[0]<>1s+d[i,b[i]]b[j]=d[j,0]s:=s+g[i]窮舉用循環(huán)開(kāi)關(guān)求當(dāng)前通路的距離統(tǒng)計(jì)不同的通路條數(shù)作記錄產(chǎn)生一種新的方案第十三頁(yè)，共一百一十三頁(yè)，2022年，8月28日要求在國(guó)際象棋棋盤(pán)上放置八個(gè)皇后，使她們不能互相攻擊，即任何兩個(gè)皇后不能處在同一行、同一列、同一條線(xiàn)上。請(qǐng)找出所有的擺法。分析：

如果我們把8*8的棋盤(pán)看成是一個(gè)平面直角坐標(biāo)系，那么任意兩個(gè)皇后在平面上的坐標(biāo)應(yīng)同時(shí)滿(mǎn)足以下三個(gè)條件：⑴兩個(gè)皇后的橫坐標(biāo)不相等。⑵兩個(gè)皇后的縱坐標(biāo)不相等。⑶兩個(gè)皇后的橫坐標(biāo)之差的絕對(duì)值不等于縱坐標(biāo)之差的絕對(duì)值。

我們用數(shù)組x[i]來(lái)描述八個(gè)皇后在棋盤(pán)上的狀態(tài)，x[i]

=j表示在第i行的第j列放置了一個(gè)皇后。I≠K當(dāng)I≠K時(shí)，X[I]≠X[K]當(dāng)I≠K時(shí)，|I-K|≠|(zhì)X[I]-X[K]|6、八皇后問(wèn)題（回溯法）第十四頁(yè)，共一百一十三頁(yè)，2022年，8月28日constn=8;

vari,j,k:integer;

x:array[1..n]ofinteger;

functionplace(k:integer):boolean;

vari:integer;

begin

place:=true;

fori:=1tok-1do

if()or(abs(x[i]-x[k])=abs(i-k))then()

;

end;

procedureprint;

vari:integer;

begin

fori:=1tondowrite(x[i]:4);

writeln;

end;proceduretry(k:integer);

vari:integer;

begin

if()thenbeginprint;exitend;

fori:=1tondo

begin

();

if()thentry(k+1);

end;

end;

begin

try(1);

end.x[i]=x[k]k=n+1place:=falsex[k]:=iplace(k)第十五頁(yè)，共一百一十三頁(yè)，2022年，8月28日如下圖所示為一個(gè)數(shù)字三角形，請(qǐng)編程計(jì)算從頂?shù)降椎哪程幍囊粭l路徑，使該路徑所經(jīng)過(guò)的數(shù)字總和最大。（只要求輸出總和）規(guī)定：⑴一步可沿左斜線(xiàn)向下或右斜線(xiàn)向下走；⑵圖形行數(shù)小于等于100；⑶三角形中的數(shù)字為0，1，…，99;測(cè)試數(shù)據(jù)通過(guò)鍵盤(pán)逐行輸入，如下圖數(shù)據(jù)應(yīng)以如下所示格式輸入：5738810274445265輸出：307、數(shù)字三角形（動(dòng)態(tài)規(guī)劃）第十六頁(yè)，共一百一十三頁(yè)，2022年，8月28日

逆推法:按三角形的行劃分階段，若行數(shù)為n，則可把問(wèn)題看做一個(gè)n-1個(gè)階段的決策問(wèn)題。先求出第n-1階段(第n-1行上各點(diǎn))到第n行的最大和，再依次求出第n-2階段、第n-3階段…第1階段(起始點(diǎn))各決策點(diǎn)至第n行的最大和。設(shè)f[i,j]為從第i階段中的點(diǎn)j至第n行的最大的數(shù)字和；則f[n,j]=a[n,j]（1<=j<=n）

f[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]}（1<=j<=i）

f[1,1]即為所求。第十七頁(yè)，共一百一十三頁(yè)，2022年，8月28日constmaxn=100;varn,i,j:integer;a:array[1..maxn,1..maxn]ofinteger;f:array[1..maxn,1..maxn]ofinteger;beginreadln(n);fori:=1tondoforj:=1toidoread(a[i,j]);

fori:=1tondof[n,i]:=a[n,i];fori:=n-1downto1doforj:=1toido

iff[i+1,j]>f[i+1,j+1]thenf[i,j]:=f[i+1,j]+a[i,j]elsef[i,j]:=f[i+1,j+1]+a[i,j];

writeln(f[1,1]);end.階段狀態(tài)決策狀態(tài)轉(zhuǎn)移方程452657121010201310232130第十八頁(yè)，共一百一十三頁(yè)，2022年，8月28日8、深度優(yōu)先遍歷基本思想：第一步，從圖中某個(gè)頂點(diǎn)V0出發(fā)，首先訪(fǎng)問(wèn)V0；第二步，找出剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)Vi的第一個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)，然后訪(fǎng)問(wèn)該頂點(diǎn)。以該頂點(diǎn)為新頂點(diǎn)，重復(fù)本步驟，直到當(dāng)前的頂點(diǎn)沒(méi)有未被訪(fǎng)問(wèn)的鄰接點(diǎn)為止；第三步，返回前一個(gè)訪(fǎng)問(wèn)過(guò)的且仍有未被訪(fǎng)問(wèn)的鄰接點(diǎn)的頂點(diǎn)，找出并訪(fǎng)問(wèn)該頂點(diǎn)的下一個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)，然后執(zhí)行第二步步驟；若此時(shí)圖中尚有頂點(diǎn)未訪(fǎng)問(wèn)，則另選圖中一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)第一步至第三步，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。第十九頁(yè)，共一百一十三頁(yè)，2022年，8月28日123754689ABDCEFGHI該圖的深度優(yōu)先搜索的輸出序列為：ABCFEGDHI以F作為起始點(diǎn)，該圖的深度優(yōu)先搜索的輸出序列為：FCBADGEHI或FCBADGHIE或FCBAEGDHI或FCBAEGHID或FCBEADGHI或FCBEGHIDA或FCBEGDAHI第二十頁(yè)，共一百一十三頁(yè)，2022年，8月28日任取一個(gè)頂點(diǎn)加入生成樹(shù)，然后對(duì)那些一個(gè)端點(diǎn)在生成樹(shù)中，而另一個(gè)端點(diǎn)不在生成樹(shù)中的邊進(jìn)行排序，取權(quán)值最小的邊，將它和另一個(gè)端點(diǎn)加進(jìn)生成樹(shù)中。重復(fù)上述步驟直到所有頂點(diǎn)都進(jìn)入了生成樹(shù)為止。9、構(gòu)造最小生成樹(shù)的prim算法第二十一頁(yè)，共一百一十三頁(yè)，2022年，8月28日12345616192133111418656121635第一步，U＝{1}，V－U＝{2,3,4,5,6}，TE＝第二步，U＝{1,2}，V－U＝{3,4,5,6}，TE＝{(1,2)}第三步，U＝{1,2,3}，V－U＝{4,5,6}，TE＝{(1,2)，(2,3)}第四步，U＝{1,2,3,4}，V－U＝{5,6}，TE＝{(1,2)，(2,3)，(2,4)}第五步，U＝{1,2,3,4,6}，V－U＝{5}，TE＝{(1,2)，(2,3)，(2,4)，(2,6)}第六步，U＝{1,2,3,4,6,5}，V－U＝，TE＝{(1,2)，(2,3)，(2,4)，(2,6)，(4,5)}46611518第二十二頁(yè)，共一百一十三頁(yè)，2022年，8月28日第一步，U＝{1}，V－U＝{2,3,4,5,6}，TE＝第二步，U＝{1,2}，V－U＝{3,4,5,6}，TE＝{(1,2)}第三步，U＝{1,2,3}，V－U＝{4,5,6}，TE＝{(1,2)，(2,3)}第四步，U＝{1,2,3,4}，V－U＝{5,6}，TE＝{(1,2)，(2,3)，(3,4)}第五步，U＝{1,2,3,4,6}，V－U＝{5}，TE＝{(1,2)，(2,3)，(3,4)，(2,6)}第六步，U＝{1,2,3,4,6,5}，V－U＝，TE＝{(1,2)，(2,3)，(3,4)，(2,6)，(4,5)}12163546115186說(shuō)明：最小生成樹(shù)也不是唯一的12345616192133111418656第二十三頁(yè)，共一百一十三頁(yè)，2022年，8月28日所謂后綴表達(dá)式是指這樣的一種表達(dá)式：式中不再引入括號(hào)，運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象之后。所有計(jì)算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格地由左而右進(jìn)行，不再考慮運(yùn)算符的優(yōu)先規(guī)則。例如5*（7-3）+9對(duì)應(yīng)的后綴表達(dá)式為573-*9+，其中每個(gè)操作數(shù)后都有一個(gè)空格。輸入：后綴表達(dá)式a

輸出：表達(dá)式的值10、計(jì)算后綴表達(dá)式的值第二十四頁(yè)，共一百一十三頁(yè)，2022年，8月28日分析：

設(shè)后綴表達(dá)式串為a，操作數(shù)、中間結(jié)果和最終結(jié)果都存放在棧S中，S的元素類(lèi)型為實(shí)型。計(jì)算過(guò)程如下：由左向右處理a中的每一個(gè)字符。若遇到一個(gè)操作數(shù)，就送入棧S中保存；遇到一個(gè)操作符，就從棧中取出棧頂?shù)膬蓚€(gè)操作數(shù)進(jìn)行計(jì)算，然后將計(jì)算結(jié)果重新壓入棧中。依次類(lèi)推，直至表達(dá)式最后一個(gè)操作符處理完畢，這時(shí)的棧頂元素值即為最終計(jì)算結(jié)果。第二十五頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top第二十六頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top5第二十七頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top57第二十八頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top573第二十九頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top573第三十頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top573-=4第三十一頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top54第三十二頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top54第三十三頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top54*=20第三十四頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top20第三十五頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top209第三十六頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top209第三十七頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top209+=29第三十八頁(yè)，共一百一十三頁(yè)，2022年，8月28日表達(dá)式：573-*9+top29第三十九頁(yè)，共一百一十三頁(yè)，2022年，8月28日typestack=recorddata:array[1..100]ofreal;top:0..100;end;vars:stack;i:integer;x:real;a:string;ch:char;functionpop(vars:stack):real;{出棧}

beginpop:=s.data[s.top];s.top:=s.top-1;end;procedurepush(vars:stack;x:real);{入棧}

begins.top:=s.top+1;s.data[s.top]:=x;end;begin{主程序}

readln(a);s.top:=0;{置空棧}第四十頁(yè)，共一百一十三頁(yè)，2022年，8月28日

i:=1;ch:=a[i];while（）dobegin

casechof‘0’..‘9’:begin{取出操作數(shù)}

x:=0;while（）dobeginx:=x*10+ord(ch)-ord('0');i:=i+1;ch:=a[i];end;end;'+‘:x:=pop(s)+pop(s);‘-’:beginx:=pop(s);x:=pop(s)-x;end;'*‘:x:=pop(s)*pop(s);‘/’:beginx:=pop(s);x:=pop(s)/x;end;end;（）;i:=i+1;ch:=a[i];{繼續(xù)掃描字符串a(chǎn)}end;writeln(:0:0);end.i<=length(a)ch<>''push(s,x)pop(s)第四十一頁(yè)，共一百一十三頁(yè)，2022年，8月28日

現(xiàn)有1g、2g、3g、5g、10g、20g的砝碼各若干枚，問(wèn)用這些砝碼可以稱(chēng)出多少種不同的重量。（設(shè)砝碼的總重不超過(guò)1000g，且砝碼只能放在天平的一端）輸入：a1a2a3a4a5a6（表示1g砝碼有a1個(gè)，2g砝碼有a2個(gè)，…，20g砝碼有a6個(gè)）輸出：total=n（n表示用這些砝碼能稱(chēng)出的不同重量的個(gè)數(shù)，但不包括一個(gè)砝碼也不用的情況）如輸入：110000則輸出：total=3（表示可以稱(chēng)出1g，2g，3g三種不同的重量）

由一個(gè)砝碼也不取開(kāi)始擴(kuò)展結(jié)點(diǎn)，當(dāng)擴(kuò)展出的某一個(gè)結(jié)點(diǎn)所對(duì)應(yīng)的質(zhì)量數(shù)在前面已經(jīng)出現(xiàn)過(guò)時(shí)，則不再?gòu)脑摻Y(jié)點(diǎn)擴(kuò)展下去，并刪掉該結(jié)點(diǎn)；如此重復(fù)，直到?jīng)]有結(jié)點(diǎn)可擴(kuò)展為止。統(tǒng)計(jì)擴(kuò)展的結(jié)點(diǎn)總數(shù)，就可得到可以稱(chēng)出的質(zhì)量總數(shù)。11、砝碼稱(chēng)重：第四十二頁(yè)，共一百一十三頁(yè)，2022年，8月28日constw:array[1..6]ofinteger=(1,2,3,5,10,20);{每種砝碼的單位質(zhì)量}

maxweight=1000;{隊(duì)列的最大長(zhǎng)度}typetlist=array[0..maxweight]ofrecord

we:integer;{當(dāng)前結(jié)點(diǎn)所對(duì)應(yīng)砝碼組合的總質(zhì)量}

sn:array[1..6]ofinteger;{各砝碼個(gè)數(shù)}

end;vara:tlist;{隊(duì)列}

s:array[1..6]ofinteger;{存放每種砝碼的數(shù)量}

b:array[1..1000]ofboolean;{標(biāo)記某個(gè)質(zhì)量是否可被稱(chēng)出}

i,head,tail:integer;cw:integer;beginfori:=1to6doread(s[i]);readln;{讀入每種砝碼的數(shù)量}

fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);1220001231213212223313233132133231

2322333313321332233123321332223321第四十三頁(yè)，共一百一十三頁(yè)，2022年，8月28日

head:=0;tail:=0;{置隊(duì)空}

while（）do{還有結(jié)點(diǎn)可擴(kuò)展,則執(zhí)行循環(huán)體}

beginfori:=1to6do{試探每種砝碼}

if（）{新組合可以得到}

thenbegincw:=a[head].we+w[i];{cw為新組合的總質(zhì)量}

if（）thenbegin{入隊(duì)}

tail:=tail+1;（）b[cw]:=true;{標(biāo)記}

a[tail].sn:=a[head].sn;（）end;end;

（）;{出隊(duì)}

end;writeln('total=',tail);end.head<=taila[head].sn[i]<s[i]notb[cw]a[tail].we:=cw;inc(a[tail].sn[i])head:=head+1第四十四頁(yè)，共一百一十三頁(yè)，2022年，8月28日多做老題，立足基本算法，引導(dǎo)一題多解。窮舉法、回溯法、動(dòng)態(tài)規(guī)劃第四十五頁(yè)，共一百一十三頁(yè)，2022年，8月28日【問(wèn)題描述】金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專(zhuān)用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說(shuō)：“你的房間需要購(gòu)買(mǎi)哪些物品，怎么布置，你說(shuō)了算，只要不超過(guò)N元錢(qián)就行”。今天一早金明就開(kāi)始做預(yù)算，但是他想買(mǎi)的東西太多了，肯定會(huì)超過(guò)媽媽限定的N元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是整數(shù)元）。他希望在不超過(guò)N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。設(shè)第j件物品的價(jià)格為v[j]，重要度為w[j]，共選中了k件物品，編號(hào)依次為j1，j2，……，jk，則所求的總和為：

v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿(mǎn)足要求的購(gòu)物單。開(kāi)心的金明(2006年普及組復(fù)賽)第四十六頁(yè)，共一百一十三頁(yè)，2022年，8月28日【輸入文件】輸入文件happy.in的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：Nm（其中N（<30000）表示總錢(qián)數(shù)，m（<25）為希望購(gòu)買(mǎi)物品的個(gè)數(shù)。）從第2行到第m+1行，第j行給出了編號(hào)為j-1的物品的基本數(shù)據(jù)，每行有2個(gè)非負(fù)整數(shù)vp（其中v表示該物品的價(jià)格(v<=10000)，p表示該物品的重要度(1~5)）【輸出文件】輸出文件happy.out只有一個(gè)正整數(shù)，為不超過(guò)總錢(qián)數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（<100000000）。【輸入樣例】1000580024005300540032002【輸出樣例】3900第四十七頁(yè)，共一百一十三頁(yè)，2022年，8月28日varv,p:array[1..25]ofinteger;b:array[0..25]of0..1;n,m,i,j,max,s,yu,l:longint;beginreadln(n,m);fori:=1tomdoreadln(v[i],p[i]);fori:=0tomdob[i]:=0;whileb[0]=0dobegin

j:=m;whileb[j]=1doj:=j-1;

b[j]:=1;

forl:=j+1tomdob[l]:=0;s:=0;yu:=0;fori:=1tomdoif(b[i]=1)thenbeginyu:=yu+v[i];s:=s+v[i]*p[i];end;if(yu<=n)and(s>max)thenmax:=s;end;writeln(max);end.可以通過(guò)8個(gè)測(cè)試點(diǎn)1、用窮舉法解第四十八頁(yè)，共一百一十三頁(yè)，2022年，8月28日

2001年普及組、提高組初賽試題在A(yíng)、B兩個(gè)城市之間設(shè)有N個(gè)路站(如下圖中的S1，且N<100)，城市與路站之間、路站和路站之間各有若干條路段(各路段數(shù)<=20，且每條路段上的距離均為一個(gè)整數(shù))。

A，B的一條通路是指：從A出發(fā)，可經(jīng)過(guò)任一路段到達(dá)S1，再?gòu)腟1出發(fā)經(jīng)過(guò)任一路段，…最后到達(dá)B。通路上路段距離之和稱(chēng)為通路距離(最大距離<=1000)。當(dāng)所有的路段距離給出之后，求出所有不同距離的通路個(gè)數(shù)(相同距離僅記一次)。

例如：下圖所示是當(dāng)N=1時(shí)的情況：從A到B的通路條數(shù)為6，但因其中通路5+5=4+6，所以滿(mǎn)足條件的不同距離的通路條數(shù)為5。

數(shù)據(jù)結(jié)構(gòu)：N記錄A，B間路站的個(gè)數(shù)；

數(shù)組D[i，0]記錄第i-1個(gè)到第i個(gè)路站間路段的個(gè)數(shù);

D[i，1]，D[i，2]，…，記錄每個(gè)路段的距離;

數(shù)組G記錄可取到的距離。第四十九頁(yè)，共一百一十三頁(yè)，2022年，8月28日vari,j,n,s:integer;

b:array[0..100]ofinteger;

d:array[0..100,0..20]ofinteger;

g:array[0..1000]of0..1;

begin

readln(n);

fori:=1ton+1do

begin

readln(d[i,0]);

forj:=1tod[i,0]doread(d[i,j]);

end;

d[0,0]:=1;

fori:=1ton+1dob[i]:=1;

b[0]:=0;

fori:=1to1000dog[i]:=0;while()do

begin

s:=0;

fori:=1ton+1do

s:=();

g[s]:=1;

j:=n+1;

while()doj:=j-1;

b[j]:=b[j]+1;

fori:=j+1ton+1dob[i]:=1;

end;

s:=0;

fori:=1to1000do();

writeln(s);readln;

end.b[0]<>1s+d[i,b[i]]b[j]=d[j,0]s:=s+g[i]第五十頁(yè)，共一百一十三頁(yè)，2022年，8月28日

將2n個(gè)0和2n個(gè)1，排成一圈。從任一個(gè)位置開(kāi)始，每次按逆時(shí)針的方向以長(zhǎng)度為n+1的單位進(jìn)行數(shù)二進(jìn)制數(shù)。要求給出一種排法，用上面的方法產(chǎn)生出來(lái)的2n+1個(gè)二進(jìn)制數(shù)都不相同。例如，當(dāng)n=2時(shí)，即22個(gè)0和22個(gè)1排成如下一圈：比如，從A位置開(kāi)始，逆時(shí)針?lè)较蛉∪齻€(gè)數(shù)000，然后再?gòu)腂位置上開(kāi)始取三個(gè)數(shù)001，接著從C開(kāi)始取三個(gè)數(shù)010，...可以得到000，001，010，101，011，111，110，100共8個(gè)二進(jìn)制數(shù)且都不相同。

程序說(shuō)明：以n=4為例，即有16個(gè)0，16個(gè)1，數(shù)組a用以記錄32個(gè)0，1的排法，數(shù)組b統(tǒng)計(jì)二進(jìn)制數(shù)出現(xiàn)的可能性。2000年提高組初賽試題第五十一頁(yè)，共一百一十三頁(yè)，2022年，8月28日var

a:array[1..36]of0..1;

b:array[0..31]ofinteger;

i,j,k,s,p:integer;

begin

fori:=1to36doa[i]:=0;

fori:=28to32doa[i]:=1;

p:=1;a[6]:=1;

fori:=1to32doforj:=itoi+4dowrite(a[j]);writeln

end.while(p=1)do

begin

j:=27

whilea[j]=1doj:=j-1;

()

fori:=j+1to27do()

fori:=0to31dob[i]:=0;

fori:=1to32do

begin

()

fork:=itoi+4dos:=s*2+a[k];

()

end;

s:=0;

fori:=0to31dos:=s+b[i];

if()thenp:=0

end;a[j]:=1a[i]:=0s:=0b[s]:=1s=32第五十二頁(yè)，共一百一十三頁(yè)，2022年，8月28日

將n個(gè)整數(shù)分成k組(k≤n,要求每組不能為空),顯然這k個(gè)部分均可得到一個(gè)各自的和s1,s2,……,sk,定義整數(shù)P為:

P=(S1-S2)2+(S1一S3)2+……+(S1-Sk)2+(s2-s3)2+……+(Sk-1-Sk)2

問(wèn)題求解:求出一種分法,使P為最小(若有多種方案僅記一種〉。程序說(shuō)明:

數(shù)組:a[1],a[2],...a[n]存放原數(shù)s[1],s[2],...,s[k]存放每個(gè)部分的和b[1],b[2],...,b[n]窮舉用臨時(shí)空間d[1],d[2],...,d[n]存放最佳方案2002年普及組初賽試題第五十三頁(yè)，共一百一十三頁(yè)，2022年，8月28日vari,j,n,k:integer;a:array[1..100]ofinteger;b,d:array[0..100]ofinteger;s:array[1..30]ofinteger;beginreadln(n,k);fori:=1tondoread(a[i]);fori:=0tondob[i]:=1;cmin:=1000000;while(b[0]=1)do

beginfori:=1tokdo();

fori:=1tondo();

sum:=0;fori:=1tok-1doforj:=()

sum:=sum+(s[i]-s[j])*(s[i]-s[j]);

if()thenbegincmin:=sum;

fori:=1tondod[i]:=b[i];end;

j:=n;while()j:=j-1;b[j]:=b[j]+1;fori:=j+1tondo()end;writeln(cmin);fori:=1tonwrite(d[i]:40);end.s[i]:=0s[b[i]]:=s[b[i]]+a[i]i+1tokdocmin>sumb[j]=kb[i]:=1第五十四頁(yè)，共一百一十三頁(yè)，2022年，8月28日有n種基本物質(zhì)(n≤10),分別記為P1,P2,……,Pn,用n種基本物質(zhì)構(gòu)造物品,這些物品使用在k個(gè)不同地區(qū)(k≤20),每個(gè)地區(qū)對(duì)物品提出自己的要求,這些要求用一個(gè)n位的數(shù)表示:α1α2……αn,其中:αi=1表示所需物質(zhì)中必須有第i種基本物質(zhì)=-1表示所需物質(zhì)中必須不能有第i種基本物質(zhì)=0無(wú)所謂問(wèn)題求解:

當(dāng)k個(gè)不同地區(qū)要求給出之后,給出一種方案,指出哪些物質(zhì)被使用,哪些物質(zhì)不被使用。

程序說(shuō)明:

數(shù)組b[1],b[2],...,b[nJ表示某種物品a[1..k,1..n]記錄k個(gè)地區(qū)對(duì)物品的要求,其中:a[i,j]=1表示第i個(gè)地區(qū)對(duì)第j種物品是需要的a[i,j]=0表示第i個(gè)地區(qū)對(duì)第j種物品是無(wú)所謂的a[i,j]=-1表示第i個(gè)地區(qū)對(duì)第j種物品是不需要的2002年提高組初賽試題第五十五頁(yè)，共一百一十三頁(yè)，2022年，8月28日vari,j,k,n:integer;p:boolean;b:array[0..20]of0..1;a:array[1..20,1..10]dinteger;beginreadln(n,k);fori:=1tokdobeginforj:=1tondoread(a[i,j]);readln;end;fori:=0tondob[i]:=0;p:=true;while()dobegin

j:=n;whileb[j]=1doj:=j-1;();fori:=j+1tondob[i]:=0;

();fori:=1tokdoforj:=1tondoif(a[i,j]=1)and(b[j]=0)or()thenp:=true;end;if()thenwriteln('找不到!‘)elsefori:=1tondoif(b[i]=1)thenwriteln('物質(zhì)',i,’需要')elsewriteln('物質(zhì)',i,'不需要');end.pand(b[0]=0)b[j]:=1p:=false(a[i,j]=-1)and(b[j]=1)p第五十六頁(yè)，共一百一十三頁(yè)，2022年，8月28日

一個(gè)正整數(shù)（非素?cái)?shù)）可以表示成它的因子（1與其本身除外）的乘積。例如：12有因子2，2，3，4，6，所以可表示為：12=2*2*3=4*3=2*6給出任一個(gè)整數(shù)n，求出它所有的因子乘積表達(dá)式（交換律得出的不同式子算同一種）。

算法說(shuō)明：讀入一個(gè)整數(shù)n，首先求出它的所有的因子以及每個(gè)因子可能的次數(shù)。例如：整數(shù)48因子：23468121624次數(shù)：41211111將上面的結(jié)果存入二維數(shù)組a中，其中：a[i，1]表示因子；a[i，2]表示次數(shù)。然后用窮舉法求出所有可能的表示：數(shù)組b記錄取數(shù)情況； 數(shù)組c工作單元。1997年普及組、提高組初賽試題第五十七頁(yè)，共一百一十三頁(yè)，2022年，8月28日vara:array[0..20,1..2]ofinteger;c,b:array[0..20]ofinteger;n,m,i,j,s,k,l:integer;beginreadln(n);fori:=1to20doa[i,1]:=0;j:=0;fori:=2ton-1dobegins:=0;m:=n;while(m<>0)and(mmodi=0)dobeginm:=mdivi;（

）;end;if（）thenbeginj:=j+1;（）;a[j,2]:=（）;endend;

s:=s+1

s>0

a[j,1]:=is第五十八頁(yè)，共一百一十三頁(yè)，2022年，8月28日

fori:=0tojdob[i]:=0;whileb[0]=0dobegin

k:=j;while（）dok:=k-1;b[k]:=b[k]+1;forl:=（）dob[l]:=0;s:=1;fori:=1tojdoifb[i]<>0thenforl:=1tob[i]do（）;ifs=nthenbegin

endendend.

fori:=1tojdoc[i]:=b[i];write('(');m:=1;fori:=1tojdowhile(c[i]>0)and(m<>n)dobeginm:=m*a[i,1];ifm=nthenwrite(a[i,1])elsebeginwrite(a[i,1],'*‘）;c[i]:=c[i]-1;end;end; writeln(')');b[k]=a[k,2]k+1tojs:=s*a[i,1]輸出表達(dá)式第五十九頁(yè)，共一百一十三頁(yè)，2022年，8月28日

有一個(gè)箱子容量為V（正整數(shù)，0≤V≤20000），同時(shí)有n個(gè)物品（0<n≤30），每個(gè)物品的體積值為正整數(shù)。要求從n個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間最小。輸入：一行整數(shù)，第一個(gè)數(shù)表示箱子的容量，第二個(gè)數(shù)表示有n個(gè)物品，后面n個(gè)數(shù)分別表示這n個(gè)物品各自的體積。輸出：一個(gè)整數(shù)，表示箱子的剩余空間。

樣例：輸入：2468312797輸出：0裝箱問(wèn)題（2001年普及組復(fù)賽第4題）第六十頁(yè)，共一百一十三頁(yè)，2022年，8月28日選數(shù)（2002年普及組復(fù)賽第2題）已知n（1<=n<=20）個(gè)整數(shù)x1,x2,…,xn（1<=xi<=5000000），以及一個(gè)整數(shù)k（k<n）。從n個(gè)整數(shù)中任選k個(gè)整數(shù)相加，可分別得到一系列的和。例如當(dāng)n=4，k=3，4個(gè)整數(shù)分別為3，7，12，19時(shí)，可得到的全部組合及它們的和為3+7+12=22，3+7+19=29，7+12+19=38，3+12+19=34?，F(xiàn)在，要求你計(jì)算出和為素?cái)?shù)的組合共有多少種。如上例中，只有一種組合的和為素?cái)?shù)：3+7+19=29。輸入：n,kx1，x2，…，xn輸出：一個(gè)整數(shù)(滿(mǎn)足條件的組合個(gè)數(shù))

樣例

輸入：43371219輸出：1第六十一頁(yè)，共一百一十三頁(yè)，2022年，8月28日問(wèn)題描述：辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說(shuō)：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大?！?/p>

如果你是辰辰，你能完成這個(gè)任務(wù)嗎？輸入文件medic.in：第一行有兩個(gè)整數(shù)T（1<=T<=1000）和M（1<=M<=100），用一個(gè)空格隔開(kāi)，T代表總共能夠用來(lái)采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。接下來(lái)的M行每行包括兩個(gè)在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。輸出文件medic.out：包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。樣例輸入：7037110069112樣例輸出：3采藥(2005年普及組第3題)第六十二頁(yè)，共一百一十三頁(yè)，2022年，8月28日

varw,v,a,s:array[0..100]oflongint;i,m,n,max:longint;proceduretry(k,use,now:longint);

{K為待選購(gòu)物品的序號(hào)，use是已用去的錢(qián)，now是現(xiàn)有的價(jià)值和}

beginifk=m+1thenbeginifnow>maxthenmax:=now;

exit;end;ifuse+w[k]<=nthentry(k+1,use+w[k],now+a[k]);{錢(qián)還夠，就買(mǎi)入此物品，待選下一物品}

try(k+1,use,now);{不買(mǎi)此物品,待選下一物品}

end;2、用回溯法解第六十三頁(yè)，共一百一十三頁(yè)，2022年，8月28日beginreadln(n,m);{總錢(qián)數(shù)和物品數(shù)}

fori:=1tomdobeginread(w[i],v[i]);a[i]:=w[i]*v[i];end;max:=0;try(1,0,0);writeln(max);

end.第六十四頁(yè)，共一百一十三頁(yè)，2022年，8月28日下面程序的功能是利用遞歸方法生成從1到n(n<10)的n個(gè)數(shù)的全部可能的排列（不一定按升序輸出）。例如，輸入3，則應(yīng)該輸出（每行輸出5個(gè)排列）：123132213231321312

求全排列（2006年普及組初賽）第六十五頁(yè)，共一百一十三頁(yè)，2022年，8月28日vari,n,k:integer;a:array[1..10]ofinteger;count:longint;procedureperm(k:integer);varj,p,t:integer;beginif

thenbegin

;forp:=1tokdowrite(a[p]:1);write('');if

thenwriteln;exit;end;forj:=ktondobegint:=a[k];a[k]:=a[j];a[j]:=t;perm(k+1);t:=a[k];

;

endend;beginread(n);count:=0;fori:=1tondoa[i]:=i;

;end.k=ninc(count)countmod5=0a[k]:=a[j];a[j]:=tperm(1)第六十六頁(yè)，共一百一十三頁(yè)，2022年，8月28日設(shè)有一個(gè)n*m的棋盤(pán)（2≤n≤20，2≤m≤20），如下圖，在棋盤(pán)上左下角有一個(gè)中國(guó)象棋馬。（n,m）

(1,1)馬走的規(guī)則為：①馬走日字；②馬只能向右走；即如下圖如示：

問(wèn)題：當(dāng)n，m輸入之后，找出一條從左下角到右上角的路徑。若不存在路徑，則輸出’NO’。樣例輸入：44輸出：（1，1）->(2,3)->(4,4)

馬騎士游歷問(wèn)題(1997年高中組第三題)第六十七頁(yè)，共一百一十三頁(yè)，2022年，8月28日

問(wèn)題描述:將整數(shù)n分成k份，且每份不能為空，任意兩種分法不能相同(不考慮順序)。例如：n=7，k=3，下面三種分法被認(rèn)為是相同的：1，1，5;1，5，1;5，1，1;問(wèn)有多少種不同的分法。輸入：n，k(6<n<=200，2<=k<=6)輸出：一個(gè)整數(shù)，即不同的分法。樣例：輸入：

73輸出：

4{四種分法為：1，1，5;1，2，4;1，3，3;2，2，3;}數(shù)的劃分（2001年提高組復(fù)賽第2題）第六十八頁(yè)，共一百一十三頁(yè)，2022年，8月28日【問(wèn)題描述】棋盤(pán)上A點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)B點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。同時(shí)在棋盤(pán)上C點(diǎn)有一個(gè)對(duì)方的馬，該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱(chēng)為對(duì)方馬的控制點(diǎn)。因此稱(chēng)之為“馬攔過(guò)河卒”。棋盤(pán)用坐標(biāo)表示，A點(diǎn)(0,0)、B點(diǎn)(n,m)(n,m為不超過(guò)15的整數(shù))，同樣馬的位置坐標(biāo)是需要給出的?，F(xiàn)在要求你計(jì)算出卒從A點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)，假設(shè)馬的位置是固定不動(dòng)的，并不是卒走一步馬走一步。【輸入】一行四個(gè)數(shù)據(jù)，分別表示B點(diǎn)坐標(biāo)和馬的坐標(biāo)。【輸出】一個(gè)數(shù)據(jù)，表示所有的路徑條數(shù)?！緲永枯斎?6633