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

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

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

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

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

b[i]:=nmod2

i-1downto0

后進先出第五頁，共一百一十三頁，2022年，8月28日Str1=‘3210’Str2=‘98765’a0123b567895791101j對位相加進位2、高精度加法第六頁，共一百一十三頁，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.處理進位從低位到高位依次將各位數(shù)相加用字符串形式輸入加數(shù)和被加數(shù)a[i]-10a[i+1]+1第七頁，共一百一十三頁，2022年，8月28日

分析：類似加法，可以用豎式求乘法。在做乘法運算時，同樣也有進位，同時對每一位進行乘法運算時，必須進行錯位相加。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、高精度乘法第八頁，共一百一十三頁，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;{上次乘積進位初始化}

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

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

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

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

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

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

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

數(shù)組G記錄可取到的距離。第十一頁，共一百一十三頁，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第十二頁，共一百一十三頁，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)開關(guān)求當前通路的距離統(tǒng)計不同的通路條數(shù)作記錄產(chǎn)生一種新的方案第十三頁，共一百一十三頁，2022年，8月28日要求在國際象棋棋盤上放置八個皇后，使她們不能互相攻擊，即任何兩個皇后不能處在同一行、同一列、同一條線上。請找出所有的擺法。分析：

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

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

=j表示在第i行的第j列放置了一個皇后。I≠K當I≠K時，X[I]≠X[K]當I≠K時，|I-K|≠|(zhì)X[I]-X[K]|6、八皇后問題（回溯法）第十四頁，共一百一十三頁，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)第十五頁，共一百一十三頁，2022年，8月28日如下圖所示為一個數(shù)字三角形，請編程計算從頂?shù)降椎哪程幍囊粭l路徑，使該路徑所經(jīng)過的數(shù)字總和最大。（只要求輸出總和）規(guī)定：⑴一步可沿左斜線向下或右斜線向下走；⑵圖形行數(shù)小于等于100；⑶三角形中的數(shù)字為0，1，…，99;測試數(shù)據(jù)通過鍵盤逐行輸入，如下圖數(shù)據(jù)應(yīng)以如下所示格式輸入：5738810274445265輸出：307、數(shù)字三角形（動態(tài)規(guī)劃）第十六頁，共一百一十三頁，2022年，8月28日

逆推法:按三角形的行劃分階段，若行數(shù)為n，則可把問題看做一個n-1個階段的決策問題。先求出第n-1階段(第n-1行上各點)到第n行的最大和，再依次求出第n-2階段、第n-3階段…第1階段(起始點)各決策點至第n行的最大和。設(shè)f[i,j]為從第i階段中的點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]即為所求。第十七頁，共一百一十三頁，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第十八頁，共一百一十三頁，2022年，8月28日8、深度優(yōu)先遍歷基本思想：第一步，從圖中某個頂點V0出發(fā)，首先訪問V0；第二步，找出剛訪問過的頂點Vi的第一個未被訪問的鄰接點，然后訪問該頂點。以該頂點為新頂點，重復(fù)本步驟，直到當前的頂點沒有未被訪問的鄰接點為止；第三步，返回前一個訪問過的且仍有未被訪問的鄰接點的頂點，找出并訪問該頂點的下一個未被訪問的鄰接點，然后執(zhí)行第二步步驟；若此時圖中尚有頂點未訪問，則另選圖中一個未被訪問的頂點作起始點，重復(fù)第一步至第三步，直至圖中所有頂點都被訪問到為止。第十九頁，共一百一十三頁，2022年，8月28日123754689ABDCEFGHI該圖的深度優(yōu)先搜索的輸出序列為：ABCFEGDHI以F作為起始點，該圖的深度優(yōu)先搜索的輸出序列為：FCBADGEHI或FCBADGHIE或FCBAEGDHI或FCBAEGHID或FCBEADGHI或FCBEGHIDA或FCBEGDAHI第二十頁，共一百一十三頁，2022年，8月28日任取一個頂點加入生成樹，然后對那些一個端點在生成樹中，而另一個端點不在生成樹中的邊進行排序，取權(quán)值最小的邊，將它和另一個端點加進生成樹中。重復(fù)上述步驟直到所有頂點都進入了生成樹為止。9、構(gòu)造最小生成樹的prim算法第二十一頁，共一百一十三頁，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第二十二頁，共一百一十三頁，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說明：最小生成樹也不是唯一的12345616192133111418656第二十三頁，共一百一十三頁，2022年，8月28日所謂后綴表達式是指這樣的一種表達式：式中不再引入括號，運算符放在兩個運算對象之后。所有計算按運算符出現(xiàn)的順序，嚴格地由左而右進行，不再考慮運算符的優(yōu)先規(guī)則。例如5*（7-3）+9對應(yīng)的后綴表達式為573-*9+，其中每個操作數(shù)后都有一個空格。輸入：后綴表達式a

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

設(shè)后綴表達式串為a，操作數(shù)、中間結(jié)果和最終結(jié)果都存放在棧S中，S的元素類型為實型。計算過程如下：由左向右處理a中的每一個字符。若遇到一個操作數(shù)，就送入棧S中保存；遇到一個操作符，就從棧中取出棧頂?shù)膬蓚€操作數(shù)進行計算，然后將計算結(jié)果重新壓入棧中。依次類推，直至表達式最后一個操作符處理完畢，這時的棧頂元素值即為最終計算結(jié)果。第二十五頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top第二十六頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top5第二十七頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top57第二十八頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top573第二十九頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top573第三十頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top573-=4第三十一頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top54第三十二頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top54第三十三頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top54*=20第三十四頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top20第三十五頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top209第三十六頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top209第三十七頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top209+=29第三十八頁，共一百一十三頁，2022年，8月28日表達式：573-*9+top29第三十九頁，共一百一十三頁，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;{置空棧}第四十頁，共一百一十三頁，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)第四十一頁，共一百一十三頁，2022年，8月28日

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

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

maxweight=1000;{隊列的最大長度}typetlist=array[0..maxweight]ofrecord

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

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

end;vara:tlist;{隊列}

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

b:array[1..1000]ofboolean;{標記某個質(zhì)量是否可被稱出}

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

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

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

head:=0;tail:=0;{置隊空}

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

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

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

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

if（）thenbegin{入隊}

tail:=tail+1;（）b[cw]:=true;{標記}

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

（）;{出隊}

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

v[j1]*w[j1]+v[j2]*w[j2]+…+v[jk]*w[jk]請你幫助金明設(shè)計一個滿足要求的購物單。開心的金明(2006年普及組復(fù)賽)第四十六頁，共一百一十三頁，2022年，8月28日【輸入文件】輸入文件happy.in的第1行，為兩個正整數(shù)，用一個空格隔開：Nm（其中N（<30000）表示總錢數(shù)，m（<25）為希望購買物品的個數(shù)。）從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數(shù)據(jù)，每行有2個非負整數(shù)vp（其中v表示該物品的價格(v<=10000)，p表示該物品的重要度(1~5)）【輸出文件】輸出文件happy.out只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（<100000000）。【輸入樣例】1000580024005300540032002【輸出樣例】3900第四十七頁，共一百一十三頁，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.可以通過8個測試點1、用窮舉法解第四十八頁，共一百一十三頁，2022年，8月28日

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

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

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

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

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

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

數(shù)組G記錄可取到的距離。第四十九頁，共一百一十三頁，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]第五十頁，共一百一十三頁，2022年，8月28日

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

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

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

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

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

數(shù)組:a[1],a[2],...a[n]存放原數(shù)s[1],s[2],...,s[k]存放每個部分的和b[1],b[2],...,b[n]窮舉用臨時空間d[1],d[2],...,d[n]存放最佳方案2002年普及組初賽試題第五十三頁，共一百一十三頁，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第五十四頁，共一百一十三頁，2022年，8月28日有n種基本物質(zhì)(n≤10),分別記為P1,P2,……,Pn,用n種基本物質(zhì)構(gòu)造物品,這些物品使用在k個不同地區(qū)(k≤20),每個地區(qū)對物品提出自己的要求,這些要求用一個n位的數(shù)表示:α1α2……αn,其中:αi=1表示所需物質(zhì)中必須有第i種基本物質(zhì)=-1表示所需物質(zhì)中必須不能有第i種基本物質(zhì)=0無所謂問題求解:

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

程序說明:

數(shù)組b[1],b[2],...,b[nJ表示某種物品a[1..k,1..n]記錄k個地區(qū)對物品的要求,其中:a[i,j]=1表示第i個地區(qū)對第j種物品是需要的a[i,j]=0表示第i個地區(qū)對第j種物品是無所謂的a[i,j]=-1表示第i個地區(qū)對第j種物品是不需要的2002年提高組初賽試題第五十五頁，共一百一十三頁，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第五十六頁，共一百一十三頁，2022年，8月28日

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

算法說明：讀入一個整數(shù)n，首先求出它的所有的因子以及每個因子可能的次數(shù)。例如：整數(shù)48因子：23468121624次數(shù)：41211111將上面的結(jié)果存入二維數(shù)組a中，其中：a[i，1]表示因子；a[i，2]表示次數(shù)。然后用窮舉法求出所有可能的表示：數(shù)組b記錄取數(shù)情況； 數(shù)組c工作單元。1997年普及組、提高組初賽試題第五十七頁，共一百一十三頁，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第五十八頁，共一百一十三頁，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]輸出表達式第五十九頁，共一百一十三頁，2022年，8月28日

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

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

樣例

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

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

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

{K為待選購物品的序號，use是已用去的錢，now是現(xiàn)有的價值和}

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

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

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

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

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

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

求全排列（2006年普及組初賽）第六十五頁，共一百一十三頁，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)第六十六頁，共一百一十三頁，2022年，8月28日設(shè)有一個n*m的棋盤（2≤n≤20，2≤m≤20），如下圖，在棋盤上左下角有一個中國象棋馬。（n,m）

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

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

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

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

73輸出：

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