【題目1】N皇后問(wèn)題（八皇后問(wèn)題的擴(kuò)展）【題目2】排球隊(duì)員站位問(wèn)題【題目3】把自然數(shù)N分解為若干個(gè)自然數(shù)之和?！绢}目4】把自然數(shù)N分解為若干個(gè)自然數(shù)之積?！绢}目5】馬的遍歷問(wèn)題。【題目6】加法分式分解【題目7】地圖著色問(wèn)題【題目8】在n*n的正方形中放置長(zhǎng)為2,寬為1的長(zhǎng)條塊，【題目9】找迷宮的最短路徑。（廣度優(yōu)先搜索算法）【題目10】火車(chē)調(diào)度問(wèn)題【題目11】農(nóng)夫過(guò)河【題目12】七段數(shù)碼管問(wèn)題?！绢}目13】把1-8這8個(gè)數(shù)放入下圖8個(gè)格中，要求相鄰的格（橫，豎，對(duì)角線(xiàn)）上填的數(shù)不連續(xù).【題目14】在4x4的棋盤(pán)上放置8個(gè)棋，要求每一行，每一列上只能放置2個(gè).【題目15】迷宮問(wèn)題.求迷宮的路徑.（深度優(yōu)先搜索法）【題目16】一筆畫(huà)問(wèn)題【題目17】城市遍歷問(wèn)題.【題目18】棋子移動(dòng)問(wèn)題【題目19】求集合元素問(wèn)題（1,2x+1,3X+1類(lèi)）【題目】N皇后問(wèn)題（含八皇后問(wèn)題的擴(kuò)展，規(guī)則同八皇后）：在N*N的棋盤(pán)上，放置N個(gè)皇后，要求每一橫行每一列，每一對(duì)角線(xiàn)上均只能放置一個(gè)皇后，問(wèn)可能的方案及方案數(shù)。constmax=8;vari,j:integer;a:array[1..max]of0..max;｛放皇后數(shù)組｝b:array[2..2*max]ofboolean;｛/對(duì)角線(xiàn)標(biāo)志數(shù)組｝c:array[-（max-1）..max-1]ofboolean;｛'對(duì)角線(xiàn)標(biāo)志數(shù)組｝col:array[1..max]ofboolean;｛歹。標(biāo)志數(shù)組｝total:integer;｛統(tǒng)計(jì)總數(shù)｝procedureoutput;｛輸出｝vari:integer;beginwrite('No.':4,'[',total+1:2,']');fori:=1tomaxdowrite(a[i]:3);write('');if(total+1)mod2=0thenwriteln;inc(total);end;functionok(i,dep:integer):boolean;｛判斷第dep行第i歹?？煞欧瘢齜eginok:=false;if(b[i+dep]=true)and(c[dep-i]=true)｛and(a[dep]=0)｝and(col[i]=true)thenok:=trueend;proceduretry(dep:integer);vari,j:integer;beginfori:=1tomaxdo｛每一行均有max種放法｝ifok(i,dep)thenbegina[dep]:=i;b[i+dep]:=false;｛/對(duì)角線(xiàn)已放標(biāo)志｝c[dep-i]:=false;｛'對(duì)角線(xiàn)已放標(biāo)志｝col[i]:=false;｛歹已放標(biāo)志｝ifdep=maxthenoutputelsetry(dep+1);｛遞歸下一層｝a[dep]:=0;｛取走皇后,回溯｝b[i+dep]:=true;｛恢復(fù)標(biāo)志數(shù)組｝c[dep-i]:=true;col[i]:=true;end;end;beginfori:=1tomaxdobegina[i]:=0;col[i]:=true;end;fori:=2to2*maxdob[i]:=true;fori:=-(max-1)tomax-1doc[i]:=true;total:=0;try(1);

writeln('total:',total);end.【測(cè)試數(shù)據(jù)】n=8八皇后問(wèn)題No.[1]15863724No.[2]16837425No.[3]17468253No.[4]17582463No.[5]24683175No.[6]25713864No.[7]25741863No.[8]26174835No.[9]26831475No.[10]27368514No.[11]27581463No.[12]28613574No.[13]31758246No.[14]35281746No.[15]35286471No.[16]35714286No.[17]35841726No.[18]36258174No.[19]36271485No.[20]36275184No.[21]36418572No.[22]36428571No.[23]36814752No.[24]36815724No.[25]36824175No.[26]37285146No.[27]37286415No.[28]38471625No.[29]41582736No.[30]41586372No.[31]42586137No.[32]42736815No.[33]42736851No.[34]42751863No.[35]42857136No.[36]42861357No.[37]46152837No.[38]46827135No.[39]46831752No.[40]47185263No.[41]47382516No.[42]47526138No.[43]47531682No.[44]48136275No.[45]48157263No.[46]48531726No.[47]51468273No.[48]51842736No.[49]51863724No.[50]52468317No.[51]52473861No.[52]52617483No.[53]52814736No.[54]53168247No.[55]53172864No.[56]53847162No.[57]57138642No.[58]57142863No.[59]57248136No.[60]57263148No.[61]57263184No.[62]57413862

No.[63]58413627No.[64]58417263No.[65]61528374No.[66]62713584No.[67]62714853No.[68]63175824No.[69]63184275No.[70]63185247No.[71]63571428No.[72]63581427No.[73]63724815No.[74]63728514No.[75]63741825No.[76]64158273No.[77]64285713No.[78]64713528No.[79]64718253No.[80]68241753No.[81]71386425No.[82]72418536No.[83]72631485No.[84]73168524No.[85]73825164No.[86]74258136No.[87]74286135No.[88]75316824No.[89]82417536No.[90]82531746No.[91]83162574No.[92]84136275total:92對(duì)于N皇后:I11|皇后NI41II11I5111611I7111I8I9I111101I11|方案數(shù)I2|1111110111I411I40111I92I352111I7241【題目】排球隊(duì)員站位問(wèn)題I圖為排球場(chǎng)的平面圖，其中一、二、三、四、五、六為位置編號(hào)，I|二、三、四號(hào)位置為前排，一、六、五號(hào)位為后排。某隊(duì)比賽時(shí)，I|一、四號(hào)位放主攻手，二、五號(hào)位放二傳手，三、六號(hào)位放副攻I11手。隊(duì)員所穿球衣分別為1，2，3，4，5，6號(hào)，但每個(gè)隊(duì)I四I三I二|員的球衣都與他們的站位號(hào)不同。已知1號(hào)、6號(hào)隊(duì)員不在后排，I112號(hào)、3號(hào)隊(duì)員不是二傳手，3號(hào)、4號(hào)隊(duì)員不在同一排，5號(hào)、I五I六I一|6號(hào)隊(duì)員不是副攻手。1111編程求每個(gè)隊(duì)員的站位情況?！舅惴ǚ治觥勘绢}可用一般的窮舉法得出答案。也可用回溯法。以下為回溯解法?！緟⒖汲绦颉縯ypesset=setof1..6;vara:array[1..6]of1..6;d:array[1..6]ofsset;i:integer;procedureoutput;｛輸出｝beginifnot((a[3]in[2,3,4])=(a[4]in[2,3,4]))thenbegin｛3,4號(hào)隊(duì)員不在同一排｝write('number:');fori:=1to6dowrite(i:8);writeln;write('weizhi:');fori:=1to6dowrite(a[i]:8);writeln;end;end;proceduretry(i:integer;s:sset);｛遞歸過(guò)程i:第i個(gè)人,s:哪些位置已安排人了｝varj,k:integer;beginforj:=1to6dobegin｛每個(gè)人都有可能站1-6這6個(gè)位置｝if(jind[i])andnot(jins)thenbegin｛j不在d[i]中，則表明第i號(hào)人不能站j位.j如在s集合中，表明j位已排人了｝a[i]:=j;｛第i人可以站j位｝ifi<6thentry(i+1,s+[j])｛未安排妥測(cè)繼續(xù)排下去｝elseoutput;｛6個(gè)人都安排完，則輸出｝end;end;end;beginfori:=1to6dod[i]:=[1..6]-[i];｛每個(gè)人的站位都與球衣的號(hào)碼不同｝d[1]:=d[1]-[1,5,6];d[6]:=d[6]-[1,5,6];｛1,6號(hào)隊(duì)員不在后排｝d[2]:=d[2]-[2,5];d[3]:=d[3]-[2,5];｛2,3號(hào)隊(duì)員不是二傳手｝d[5]:=d[5]-[3,6];{5,6號(hào)隊(duì)員不是副攻手{5,6號(hào)隊(duì)員不是副攻手}try(1,[]);end.【題目】把自然數(shù)N分解為若干個(gè)自然數(shù)之和?！緟⒖即鸢浮縩|totalTOC\o"1-5"\h\z|7|11|1510|42100|190569291【參考程序】varn:byte;num:array[0..255]ofbyte;total:word;procedureoutput(dep:byte);varj:byte;beginforj:=1todepdowrite(num[j]:3);writeln;inc(total);end;procedurefind(n,dep:byte);｛N:待分解的數(shù),DEP:深度｝vari,j,rest:byte;beginfori:=1tondo｛每一位從N到1去試｝ifnum[dep-1]<=ithen｛保證選用的數(shù)大于前一位｝beginnum[dep]:=i;rest:=n-i;｛剩余的數(shù)進(jìn)行下一次遞歸調(diào)用｝if(rest>0)thenbeginfind(rest,dep+1);endelseifrest=0thenoutput(dep);｛剛好相等則輸出｝num[dep]:=0;end;end;begin｛主程序｝writeln('inputn:');readln(n);fillchar(num,sizeof(num),0);total:=0;num[0]:=0;find(n,1);writeln('sum=',total);end.【題目】把自然數(shù)N分解為若干個(gè)自然數(shù)之積。【參考程序】varpath:array[1..1000]ofinteger;total,n:integer;procedurefind(k,sum,dep:integer);{K:}varb,d:Integer;beginifsum=nthen{積等于N}beginwrite(n,'=',path[1]);ford:=2todep-1dowrite('*',path[d]);writeln;inc(total);exit;end;ifsum>nthenexit;{累積大于N}forb:=trunc(n/sum)+1downtokdo{每一種可能都去試}beginpath[dep]:=b;find(b,sum*b,dep+1);end;end;beginreadln(n);total:=0;find(2,1,1);writeln('total:',total);readln;end.【題目】馬的遍歷問(wèn)題。在N大M的棋盤(pán)中，馬只能走日字。馬從位置(x,y)處出發(fā)，把棋盤(pán)的每一格都走一次，且只走一次。找出所有路徑?！緟⒖汲绦颉浚疃葍?yōu)先搜索法｝constn=5;m=4;fx:array[1..8,1..2]of-2..2=((1,2),(2,1),(2廣1),(1廣2),(-1,-2),(-2廣1),(-2,1),(-1,2));｛八個(gè)方向增量｝vardep,i:byte;x,y:byte;cont:integer;｛統(tǒng)計(jì)總數(shù)｝a:array[1..n,1..m]ofbyte;｛記錄走法數(shù)組｝procedureoutput;｛輸出，并統(tǒng)計(jì)總數(shù)｝varx,y:byte;begincont:=cont+1;writeln;writeln('count=',cont);fory:=1tondobeginforx:=1tomdowrite(a[y,x]:3);writeln;end;｛readln;halt;｝end;procedurefind(y,x,dep:byte);vari,xx,yy:integer;beginfori:=1to8dobeginxx:=x+fx[i,1];yy:=y+fx[i,2];｛加上方向增量，形成新的坐標(biāo)｝if((xxin[1..m])and(yyin[1..n]))and(a[yy,xx]=0)then｛判斷新坐標(biāo)是否出界，是否已走過(guò)？｝begina[yy,xx]:=dep;｛走向新的坐標(biāo)｝if(dep=n*m)thenoutputelsefind(yy,xx,dep+1);｛從新坐標(biāo)出發(fā),遞歸下一層｝a[yy,xx]:=0｛回溯，恢復(fù)未走標(biāo)志｝end;end;begincont:=0;fillchar(a,sizeof(a),0);dep:=1;writeln('inputy,x');readln(y,x);{x:=1;y:=1;}if(y>n)or(x>m)thenbeginwriteln('x,yerror!');halt;end;a[y,x]:=1;find(y,x,2);ifcont=0thenwriteln('Noanswer!')elsewrite('TheEnd!');readln;end.【題目】加法分式分解。如：1/2=1/4+1/4.找出所有方案。輸A：NMN為要分解的分?jǐn)?shù)的分母M為分解成多少項(xiàng)【參考程序】programfenshifenjie;constnums=5;vart,m,dep:integer;n,maxold,max,j:longint;path:array[0..nums]oflongint;maxok,p:boolean;sum,sum2:real;procedureprint;vari:integer;begint:=t+1;ifmaxok=truethenbeginmaxold:=path[m];maxok:=false;end;write('NO.',t);fori:=1tomdowrite('',path[i]:4);writeln;ifpath[1]=path[m]thenbeginwriteln('Ok!total:',t:4);readln;halt;end;end;procedureinput;beginwriteln('inputN:');readln(n);writeln('inputM(M<=',nums:1,'):');readln(m);if(n<=0)or(m<=0)or(m>4)or(n>maxlongint)thenbeginwriteln('InvalidInput!');readln;halt;end;end;functionsum1(ab:integer):real;vara,b,c,d,s1,s2:real;i:integer;beginifab=1thensum1:=1/path[1]elsebegina:=path[1];b:=1;c:=path[2];d:=1;fori:=1toab-1dobegins2:=(c*b+a*d);s1:=(a*c);a:=s1;b:=s2;c:=path[i+2];end;sum1:=s2/s1;end;end;procedureback;begindep:=dep-1;ifdep<=m-2thenmax:=maxold;sum:=sum-1/path[dep];j:=path[dep];end;procedurefind;beginrepeatdep:=dep+1;j:=path[dep-1]-1;p:=false;repeatj:=j+1;if(dep<>m)and(j<=max)thenif(sum+1/j)>=1/nthenp:=falseelsebeginp:=true;path[dep]:=j;sum:=sum+1/path[dep];endelseifj>maxthenback;ifdep=mthenbeginpath[dep]:=j;sum2:=sum1(m);if(sum2)>1/nthenp:=false;if(sum2)=1/nthenbeginprint;max:=j;back;end;if(sum2<1/n)thenback;if(j>=max)thenback;end;untilpuntildep=0;end;beginINPUT;maxok:=true;fort:=0tomdopath[t]:=n;dep:=0;t:=0;sum:=0;max:=maxlongint;find;readln;end.【題目】地圖著色問(wèn)題【參考程序1】constlin:array[1..12,1..12]of0..1｛區(qū)域相鄰數(shù)組,1表示相鄰｝=((0,1,1,1,1,1,0,0,0,0,0,0),(1,0,1,0,0,1,1,1,0,0,0,0),(1,1,0,1,0,0,0,1,1,0,0,0),(1,0,1,0,1,0,1,0,1,1,0,0),(1,0,0,1,0,1,0,0,0,1,1,0),(1,1,0,0,1,0,1,0,0,0,1,0),(0,1,0,0,0,1,0,1,0,0,1,1),(0,1,1,0,0,0,1,0,1,0,0,1),(0,0,1,1,0,0,0,1,0,1,0,1),(0,0,0,1,1,0,0,0,1,0,1,1),(0,0,0,0,1,1,1,0,0,1,0,1),(0,0,0,0,0,0,1,1,1,1,1,1));varcolor:array[1..12]ofbyte;｛color數(shù)組放已填的顏色｝total:integer;functionok(dep,i:byte):boolean;｛判斷選用色i是否可用｝vark:byte;｛條件:相鄰的區(qū)域顏色不能相同｝beginfork:=1todepdoif(lin[dep,k]=1)and(i=color[k])thenbeginok:=false;exit;end;ok:=true;procedureoutput;｛輸出｝vark:byte;beginfork:=1to12dowrite(color[k],'');writeln;total:=total+1;end;procedurefind(dep:byte);｛參數(shù)dep:當(dāng)前正在填的層數(shù)｝vari:byte;beginfori:=1to4dobegin｛每個(gè)區(qū)域都可能是1-4種顏色｝ifok(dep,i)thenbegincolor[dep]:=i;ifdep=12thenoutputelsefind(dep+1);color[dep]:=0;｛恢復(fù)初始狀態(tài)，以便下一次搜索｝end;end;end;begintotal:=0;｛總數(shù)初始化｝fillchar(color,sizeof(color),0);find(1);writeln('total:=',total);end.【參考程序2】const｛lin數(shù)組:代表區(qū)域相鄰情況｝lin:array[1..12]ofsetof1..12=([2,3,4,5,6],[1,3,6,7,8],[1,2,4,8,9],[1,3,5,9,10],[1,4,6,10,11],[125,7,11],[12,8,11,6,2],[12,9,723],[12,8,10,3,4],[12,9,11,4,5],[12,7,10,5,6],[7,8,9,10,11]);color:array[1..4]ofchar=('r','y','b','g');vara:array[1..12]ofbyte;｛因有12個(gè)區(qū)域，故a數(shù)組下標(biāo)為1-12｝total:integer;functionok(dep,i:integer):boolean;｛判斷第dep塊區(qū)域是否可填第i種色｝varj:integer;｛j為什么設(shè)成局部變量？｝beginok:=true;forj:=1to12doif(jinlin[dep])and(a[j]=i)thenok:=false;end;procedureoutput;｛輸出過(guò)程｝varj:integer;｛j為什么設(shè)成局部變量？｝begininc(total);｛方案總數(shù)加1｝write(total:4);｛輸出一種方案｝forj:=1to12dowrite(color[a[j]]:2);writeln;end;procedurefind(dep:byte);vari:byte;｛i為什么設(shè)成局部變量？｝beginfori:=1to4do｛每一區(qū)域均可從4種顏色中選一｝beginifok(dep,i)thenbegin｛可填該色｝a[dep]:=i;｛第dep塊區(qū)域填第i種顏色｝if(dep=12)thenoutput｛填完12個(gè)區(qū)域｝elsefind(dep+1);｛未填完｝a[dep]:=0;｛取消第dep塊區(qū)域已填的顏色｝end;end;end;begin｛主程序｝fillchar(a,sizeof(a),0);｛記得要給變量賦初值!｝total:=0;find(1);writeln('End.');end.【題目】在n*n的正方形中放置長(zhǎng)為2,寬為1的長(zhǎng)條塊，問(wèn)放置方案如何【參考程序1】constn=4;vark,u,v,result:integer;a:array[1..n,1..n]ofchar;procedureprintf;｛輸出｝beginresult:=result+1;｛方案總數(shù)加1｝writeln('---',result,'---');forv:=1tondobeginforu:=1tondowrite(a[u,v]);writelnend;writeln;end;proceduretry;｛填放長(zhǎng)條塊｝vari,j,x,y:integer;full:boolean;beginfull:=true;ifk<>trunc(n*n/2)thenfull:=false;｛測(cè)試是否已放滿(mǎn)｝iffullthenprintf;｛放滿(mǎn)則可輸出｝ifnotfullthenbegin｛未滿(mǎn)｝x:=0;y:=1;｛以下先搜索未放置的第一個(gè)空位置｝repeatx:=x+1;ifx>nthenbeginx:=1;y:=y+1enduntila[x,y]='';｛找到后，分兩種情況討論｝ifa[x+1,y]=''thenbegin｛第一種情況:橫向放置長(zhǎng)條塊｝k:=k+1;｛記錄已放的長(zhǎng)條數(shù)｝a[x,y]:=chr(k+ord('@'));｛放置｝a[x+1,y]:=chr(k+ord('@'));try;｛遞歸找下一個(gè)空位置放｝k:=k-1;a[x,y]:='';a[x+1,y]:='｛回溯，恢復(fù)原狀｝end;ifa[x,y+1]=''thenbegin｛第二種情況:豎向放置長(zhǎng)條塊｝k:=k+1;｛記錄已放的長(zhǎng)條數(shù)｝a[x,y]:=chr(k+ord('0'));｛放置｝a[x,y+1]:=chr(k+ord('0'));try;｛遞歸找下一個(gè)空位置放｝k:=k-1;a[x,y]:='';｛回溯，恢復(fù)原狀｝a[x,y+1]:=''end;end;end;begin｛主程序｝fillchar(a,sizeof(a),'');｛記錄放置情況的字符數(shù)組，初始值為空格｝result:=0;k:=0;｛k記錄已放的塊數(shù)，如果k=n*n/2,則說(shuō)明已放滿(mǎn)｝try;｛每找到一個(gè)空位置，把長(zhǎng)條塊分別橫放和豎放試驗(yàn)｝end.【參考程序2】constdai:array[1..2,1..2]ofinteger=((0,1),(1,0));typenode=recordw,f:integer;end;vara:array[1..20,1..20]ofinteger;path:array[0..200]ofnode;s,m,n,nn,i,j,x,y,dx,dy,dep:integer;p,px:boolean;procedureinputn;begin｛write('inputn');readln(n);｝n:=4;nn:=n*n;m:=nndiv2;procedureprint;vari,j:integer;begininc(s);writeln('no',s);fori:=1tondobeginforj:=1tondowrite(a[i,j]:3);writeln;end;writeln;end;functionfg(h,v:integer):boolean;varp:boolean;beginp:=false;if(h<=n)and(v<=n)thenifa[h,v]=0thenp:=true;fg:=p;end;procedureback;begindep:=dep-1;ifdep=0thenbeginp:=true;px:=true;endelsebegini:=path[dep].w;j:=path[dep].f;x:=((i-1)divn)+1;y:=imodn;ify=0theny:=n;dx:=x+dai[j,1];dy:=y+dai[j,2];a[x,y]:=0;a[dx,dy]:=0;end;end;begininputn;s:=0;fillchar(a,sizeof(a),0);x:=0;y:=0;dep:=0;path[0].w:=0;path[0].f:=0;repeatdep:=dep+1;i:=path[dep-1].w;repeati:=i+1;x:=((i-1)divn)+1;y:=imodn;ify=0theny:=n;px:=false;iffg(x,y)thenbeginj:=0;p:=false;repeatinc(j);dx:=x+dai[j,1];dy:=y+dai[j,2];iffg(dx,dy)and(j<=2)thenbegina[x,y]:=dep;a[dx,dy]:=dep;path[dep].w:=i;path[dep].f:=j;ifdep=mthenbeginprint;dep:=m+1;back;endelsebeginp:=true;px:=true;end;endelseifj>=2thenbackelsep:=false;untilp;endelseifi>=nnthenbackelsepx:=false;untilpx;untildep=0;readln;end.【題目】找迷宮的最短路徑。（廣度優(yōu)先搜索算法）【參考程序】usescrt;constmigong:array[1..5,1..5]ofinteger=((0,0廣1,0,0),(0廣1,0,0廣1),(0,0,0,0,0),(0,-1,0,0,0),(-1,0,0,-1,0));｛迷宮數(shù)組｝fangxiang:array[1..4,1..2]of-1..1=((1,0),(0,1),(-1,0),(0,-1));｛方向增量數(shù)組｝typenode=recordlastx:integer;｛上一位置坐標(biāo)｝lasty:integer;nowx:integer;｛當(dāng)前位置坐標(biāo)｝nowy:integer;pre:byte;｛本結(jié)點(diǎn)由哪一步擴(kuò)展而來(lái)｝dep:byte;｛本結(jié)點(diǎn)是走到第幾步產(chǎn)生的｝end;varlujing:array[1..25]ofnode;｛記錄走法數(shù)組｝closed,open,x,y,r:integer;procedureoutput;vari,j:integer;beginfori:=1to5dobeginforj:=1to5dowrite(migong[i,j]:4);writeln;end;i:=open;repeatwithlujing[i]dowrite(nowy:2,',',nowx:2,'<--');i:=lujing[i].pre;untillujing[i].pre=0;withlujing[i]dowrite(nowy:2,',',nowx:2);beginclrscr;withlujing[1]dobegin｛初始化第一步｝lastx:=0;lasty:=0;nowx:=1;nowy:=1;pre:=0;dep:=1;end;closed:=0;open:=1;migong[1,1]:=1;repeatinc(closed);｛隊(duì)列首指針加1,取下一結(jié)點(diǎn)｝forr:=1to4dobegin｛以4個(gè)方向擴(kuò)展當(dāng)前結(jié)點(diǎn)｝x:=lujing[closed].nowx+fangxiang[r,1];｛擴(kuò)展形成新的坐標(biāo)值｝y:=lujing[closed].nowy+fangxiang[r,2];ifnot((x>5)or(y>5)or(x<1)or(y<1)or(migong[y,x]<>0))thenbegin｛未出界,未走過(guò)則可視為新的結(jié)點(diǎn)｝inc(open);｛隊(duì)列尾指針加1｝withlujing[open]dobegin｛記錄新的結(jié)點(diǎn)數(shù)據(jù)｝nowx:=x;nowy:=y;lastx:=lujing[closed].nowx;｛新結(jié)點(diǎn)由哪個(gè)坐標(biāo)擴(kuò)展而來(lái)｝lasty:=lujing[closed].nowy;dep:=lujing[closed].dep+1;｛新結(jié)點(diǎn)走到第幾步｝pre:=closed;｛新結(jié)點(diǎn)由哪個(gè)結(jié)點(diǎn)擴(kuò)展而來(lái)｝end;migong[y,x]:=lujing[closed].dep+1;｛當(dāng)前結(jié)點(diǎn)的覆蓋范圍｝if(x=5)and(y=5)thenbegin｛輸出找到的第一種方案｝

writeln('ok,thatsallright');output;halt;end;end;end;untilclosed>=open;｛直到首指針大于等于尾指針，即所有結(jié)點(diǎn)已擴(kuò)展完｝end.【題目】火車(chē)調(diào)度問(wèn)題【參考程序】constmax=10;typeshuzu=array[1..max]of0..max;varstack,exitout:shuzu;n,total:integer;procedureoutput(exitout:shuzu);vari:integer;beginfori:=1tondowrite(exitout[i]:2);writeln;inc(total);end;procedurefind(dep,have,rest,exit_weizhi:integer;stack,exitout:shuzu);｛dep:步數(shù),have:入口處有多少輛車(chē);rest:車(chē)站中有多少車(chē);｝｛exit_weizhi:從車(chē)站開(kāi)出后，排在出口處的位置;｝｛stack:車(chē)站中車(chē)輛情況數(shù)組;exitout:出口處車(chē)輛情況數(shù)組｝vari:integer;begin｛分入站,出站兩種情況討論｝ifhave>0thenbegin｛還有車(chē)未入站｝stack[rest+1]:=n+1-have;｛入站｝ifdep=2*nthenoutput(exitout)elsefind(dep+1,have-1,rest+1,exit_weizhi,stack,exitout);end;ifrest>0thenbegin｛還有車(chē)可出站｝exitout[exit_weizhi+1]:=stack[rest];｛出站｝ifdep=2*nthenoutput(exitout)｛經(jīng)過(guò)2n步后，輸出一種方案｝elsefind(dep+1,have,rest-1,exit_weizhi+1,stack,exitout);end;end;beginwriteln('inputn:');readln(n);fillchar(stack,sizeof(stack),0);fillchar(exitout,sizeof(exitout),0);total:=0;find(1,n,0,0,stack,exitout);writeln('total:',total);readln;【解法2】用窮舉二進(jìn)制數(shù)串的方法完成.usescrt;vari,n,m,t:integer;a,s,c:array[1..1000]ofinteger;proceduretest;vart1,t2,k:integer;notok:boolean;begint1:=0;k:=0;t2:=0;i:=0;notok:=false;repeat｛二進(jìn)制數(shù)串中,0表示出棧,1表示入棧｝i:=i+1;｛數(shù)串中第I位｝ifa[i]=1thenbegin｛第I位為1,則表示車(chē)要入棧｝inc(k);｛棧中車(chē)數(shù)｝inc(t1);｛入棧記錄,T1為棧指針,S為棧數(shù)組｝s[t1]:=k;endelse｛第I位為0,車(chē)要出棧｝ift1<1thennotok:=true｛已經(jīng)無(wú)車(chē)可出，當(dāng)然NOT_OK了｝elsebegininc(t2);c[t2]:=s[t1];dec(t1);end;｛棧中有車(chē)，出棧，放到C數(shù)組中去,T2為C的指針，棧指針T1下調(diào)1｝until(i=2*n)ornotok;｛整個(gè)數(shù)串均已判完，或中途出現(xiàn)不OK的情況｝if(t1=0)andnotnotokthenbegin｛該數(shù)串符合出入棧的規(guī)律則輸出｝inc(m);write('[',m,']');fori:=1tot2dowrite(c[i]:2);writeln;end;end;beginclrscr;write('N=');readln(n);m:=0;fori:=1to2*ndoa[i]:=0;｛repeat｛循環(huán)產(chǎn)生N位二進(jìn)制數(shù)串｝test;｛判斷該數(shù)串是否符合車(chē)出入棧的規(guī)律｝t:=2*n;a[t]:=a[t]+1;｛產(chǎn)生下一個(gè)二進(jìn)制數(shù)串｝while(t>1)and(a[t]>1)dobegina[t]:=0;dec(t);a[t]:=a[t]+1;end;untila[1]=2;readln;end.N:4678TOTAL:141324291430【題目】農(nóng)夫過(guò)河。一個(gè)農(nóng)夫帶著一只狼，一只羊和一些菜過(guò)河。河邊只有一條一船，由于船太小，只能裝下農(nóng)夫和他的一樣?xùn)|西。在無(wú)人看管的情況下，狼要吃羊，羊要吃菜，請(qǐng)問(wèn)農(nóng)夫如何才能使三樣?xùn)|西平安過(guò)河?！舅惴ǚ治觥繉?wèn)題數(shù)字化。用1代表狼，2代表羊，3代表菜。則在河某一邊物體的分布有以下8種情況。1111物體個(gè)數(shù)|o|1111111|21|113|11111|分布情況|o|1111111|2|111111|3|1,2|1,31111|2,3111|1,2,3|11111|代碼之和|0|1111111|2111111|3|3|41II1|5|1116|11111|是否相克11111111|111111||相克|1111|相克|111|11當(dāng)(兩物體在一起而且)代碼和為3或5時(shí)，必然是相克物體在一起的情況?！緟⒖汲绦颉縞onstwt:array[0..3]ofstring[5]=('','WOLF','SHEEP','LEAVE');varleft,right:array[1..3]ofinteger;what,i,total,left_rest,right_rest:integer;procedureprint_left;｛輸出左岸的物體｝vari:integer;begintotal:=total+1;write('(',total,')');｛第幾次渡河｝fori:=1to3dowrite(wt[left[i]]);write('|','':4);end;procedureprint_right;｛輸出右岸的物體｝vari:integer;beginwrite('':4,'|');fori:=1to3doifright[i]<>0thenwrite(wt[right[i]]);writeln;end;procedureprint_back(who:integer);｛右岸矛盾時(shí)，需從右岸捎物體…左岸｝vari:integer;beginfori:=1to3dobeginifnot((i=who)or(right[i]=0))thenbegin｛要捎回左岸的物體不會(huì)時(shí)剛剛從左岸帶來(lái)的物體，也不會(huì)是不在右岸的物體｝what:=right[i];right[i]:=0;print_left;｛輸出返回過(guò)程｝write('<-',wt[i]);print_right;left[i]:=what;｛物體到達(dá)左岸｝end;end;end;begintotal:=0;fori:=1to3dobeginleft[i]:=i;right[i]:=0;end;repeatfori:=1to3do｛共有3種物體｝ifleft[i]<>0then｛第I種物體在左岸｝beginwhat:=left[i];left[i]:=0;｛what:放置將要過(guò)河的物體編號(hào)｝left_rest:=left[1]+left[2]+left[3];｛求左岸剩余的物體編號(hào)總和｝if(left_rest=3)or(left_rest=5)thenleft[i]:=what｛假如左岸矛盾，則不能帶第I種過(guò)河，嘗試下一物體｝else｛否則可帶過(guò)河｝beginprint_left;｛輸出過(guò)河過(guò)程｝write('->',wt[i]);print_right;right[i]:=what;｛物體到達(dá)右岸｝ifleft_rest=0thenhalt;｛左岸物體已悉數(shù)過(guò)河｝right_rest:=right[1]+right[2]+right[3];｛求右岸剩余的物體編號(hào)總和｝if(right_rest=3)or(right_rest=5)thenprint_back(i)｛右岸有矛盾，要捎物體回左岸｝elsebeginprint_left;｛右岸有矛盾，空手回左岸｝write('<-','':5);print_right;end;end;end;untilfalse;｛不斷往返｝end.【題目】七段數(shù)碼管問(wèn)題。從一個(gè)數(shù)字變化到其相鄰的數(shù)字只需要通過(guò)某些段（數(shù)目不限）1或拿走某些段（數(shù)目不限）來(lái)實(shí)現(xiàn).但不允許既增加段又拿起段.I~|例如:3可以變到9,也可以變到1要求:(1)判斷從某一數(shù)字可以變到其它九個(gè)數(shù)字中的哪幾個(gè).(2)找出一種排列這十個(gè)數(shù)字的方案，便這樣組成的十位數(shù)數(shù)值最小.typekkk=setof0..9;consta:array[-1..9]ofsetof1..7=([5,6],[1,2,3,4,5,6],[2,3],[1,2,4,5,7],[1,2,3,4,7],[2,3,6,7],[1,3,4,6,7],[1,3,4,5,6,7],[1,2,3],[1,2,3,4,5,6,7],[1,2,3,4,6,7]);vari,j:integer;b:array[-2..9]ofsetof0..9;procedurenumber(p:string;s,l:integer;k:kkk);｛P:生成的數(shù);s:用了幾個(gè)數(shù)字;i:前一個(gè)是哪個(gè)數(shù)字;k:可用的數(shù)字｝vari:integer;beginfori:=0to9doif(iink)and(iinb[l])thenbegin｛數(shù)字i未用過(guò)，且i可由前一個(gè)采用的數(shù)字變化而來(lái)｝ifs=10thenbeginwriteln('Min:',p,i);readln;halt;endelsenumber(p+chr(48+i),s+1,i,k-[i]);end;end;beginfori:=1to9dob[i]:=[];b[-2]:=[0..9];fori:=-1to8doforj:=i+1to9doif(a[i]<=a[j])or(a[j]<=a[i])thenbeginb[i]:=b[i]+[j];b[j]:=b[j]+[abs(i)];end;b[1]:=b[1]+b[-1];fori:=0to9dobeginwrite(i,'mayturnto:');forj:=0to9doifjinb[i]thenwrite(j,'');writeln;number('',1,-2,[0..9]);end.【題目】把1-8這8個(gè)數(shù)放入下圖8個(gè)格中，要求相鄰的格(橫，豎，對(duì)角線(xiàn))上填的數(shù)不連續(xù).【參考程序】constlin:array[1..8]ofsetof1..8=([3,2,4],[1,6,3,5],[5,7,1,2,4,6],[1,6,3,7],[3,8,2,6],[2,4,3,5,7,8],[3,8,4,6],[5,7,6]);vara:array[1..8]ofinteger;total,i:integer;had:setof1..8;functionok(dep,i:integer):boolean;｛判斷是否能在第dep格放數(shù)字i｝varj:integer;beginok:=true;forj:=1to8do｛相鄰且連續(xù)則不行｝if(jinlin[dep])and(abs(i-a[j])=1)thenok:=false;ifiinhadthenok:=false;｛已用過(guò)的也不行｝end;procedureoutput;｛輸出一種方案｝varj:integer;begininc(total);write(total,':');forj:=1to8dowrite(a[j]:2);writeln;procedurefind(dep:byte);vari:byte;beginfori:=1to8dobegin｛每一格可能放1-8這8個(gè)數(shù)字中的一個(gè)｝ifok(dep,i)thenbegina[dep]:=i;｛把i放入格中｝had:=had+[i];｛設(shè)置已放過(guò)標(biāo)志｝if(dep=8)thenoutputelsefind(dep+1);a[dep]:=10;｛回溯，恢復(fù)原狀態(tài)｝had:=had-[i];end;end;end;beginfillchar(a,sizeof(a),10);total:=0;had:=[];find(1);writeln('End.');end.【題目】在4x4的棋盤(pán)上放置8個(gè)棋，要求每一行，每一列上只能放置2個(gè).【參考程序1】算法:8個(gè)棋子，填8次.深度為8.注意判斷是否能放棋子時(shí)，兩個(gè)兩個(gè)為一行.vara:array[1..8]of0..4;line,bz:array[1..4]of0..2;｛line數(shù)組:每行已放多少個(gè)的計(jì)數(shù)器｝｛bz數(shù)組：每列已放多少個(gè)的計(jì)數(shù)器｝total:integer;procedureoutput;｛輸出｝vari:integer;begininc(total);write(total,':');fori:=1to8dowrite(a[i]);writeln;functionok(dep,i:integer):boolean;beginok:=true;ifdepmod2=0then｛假如是某一行的第2個(gè)，其位置必定要在第1個(gè)之后｝if(i<=a[dep-1])thenok:=false;if(bz[i]=2)or(line[depdiv2]=2)thenok:=false;｛某行或某列已放滿(mǎn)2個(gè)｝end;procedurefind(dep:integer);vari:integer;beginfori:=1to4dobeginifok(dep,i)thenbegina[dep]:=i;｛放在dep行i列｝inc(bz[i]);｛某一列記數(shù)器加1｝inc(line[depdiv2]);｛某一行記數(shù)器加1｝ifdep=8thenoutputelsefind(dep+1);dec(bz[i]);｛回溯｝dec(line[depdiv2]);a[dep]:=0;end;end;end;begintotal:=0;fillchar(a,sizeof(a),0);fillchar(bz,sizeof(bz),0);find(1);end.【參考程序2】算法:某一行的放法可能性是(1,2格),(1,3格),(1,4格)....共6種放法constfa:array[1..6]ofarray[1..2]of1..4=((1,2),(1,3),(1,4),(2,3),(2,4),(3,4));｛六種可能放法的行坐標(biāo)｝vara:array[1..8]of0..4;bz:array[1..4]of0..2;｛列放了多少個(gè)的記數(shù)器｝total:integer;procedureoutput;vari:integer;begininc(total);write(total,':');fori:=1to8dowrite(a[i]);writeln;end;functionok(dep,i:integer):boolean;beginok:=true;｛判斷現(xiàn)在的放法中，相應(yīng)的兩列是否已放夠2個(gè)｝if(bz[fa[i,1]]=2)or(bz[fa[i,2]]=2)thenok:=false;end;procedurefind(dep:integer);vari:integer;beginfori:=1to6dobegin｛共有6種可能放法｝ifok(dep,i)thenbegina[(dep-1)*2+1]:=fa[i,1];｛一次連續(xù)放置2個(gè)｝a[(dep-1)*2+2]:=fa[i,2];inc(bz[fa[i,1]]);｛相應(yīng)的兩列，記數(shù)器均加1｝inc(bz[fa[i,2]]);ifdep=4thenoutputelsefind(dep+1);dec(bz[fa[i,1]]);｛回溯｝dec(bz[fa[i,2]]);a[(dep-1)*2+1]:=0;a[(dep-1)*2+2]:=0;end;end;end;begintotal:=0;fillchar(a,sizeof(a),0);fillchar(bz,sizeof(bz),0);find(1);end.【題目】迷宮問(wèn)題.求迷宮的路徑.(深度優(yōu)先搜索法)【參考程序1】constRoad:array[1..8,1..8]of0..3=((1,0,0,0,0,0,0,0),(0,1,1,1,1,0,1,0),(0,0,0,0,1,0,1,0),(0,1,0,0,0,0,1,0),(0,1,0,1,1,0,1,0),(0,1,0,0,0,0,1,1),(0,1,0,0,1,0,0,0),(0,1,1,1,1,1,1,0));｛迷宮數(shù)組｝FangXiang:array[1..4,1..2]of-1..1=((1,0),(0,1),(-1,0),(0廣1));｛四個(gè)移動(dòng)方向｝WayIn:array[1..2]ofbyte=(1,1);｛入口坐標(biāo)｝WayOut:array[1..2]ofbyte=(8,8);｛出口坐標(biāo)｝Vari,j,Total:integer;ProcedureOutput;vari,j:integer;BeginFori:=1to8dobeginforj:=1to8dobeginifRoad[i,j]=1thenwrite(#219);｛1:墻｝ifRoad[i,j]=2thenwrite('');｛2:曾走過(guò)但不通的路｝ifRoad[i,j]=3thenwrite(#03);｛3:沿途走過(guò)的暢通的路｝ifRoad[i,j]=0thenwrite('');｛0:原本就可行的路｝end;writeln;end;inc(total);｛統(tǒng)計(jì)總數(shù)｝readln;end;FunctionOk(x,y,i:byte):boolean;｛判斷坐標(biāo)(X,Y)在第I個(gè)方向上是否可行｝VarNewX,NewY:shortint;BeginOk:=True;Newx:=x+FangXiang[i,1];Newy:=y+FangXiang[i,2];Ifnot((NewXin[1..8])and(NewYin[1..8]))thenOk:=False;｛超界？｝IfRoad[NewX,NewY]=3thenok:=false;｛是否已走過(guò)的路？｝IfRoad[NewX,NewY]=1thenok:=false;｛是否墻？｝End;ProcedureHowgo(x,y:integer);Vari,NewX,NewY:integer;BeginFori:=1to4doBegin｛每一步均有4個(gè)方向可選擇｝IfOk(x,y,i)thenBegin｛判斷某一方向是否可前進(jìn)｝Newx:=x+FangXiang[i,1];｛前進(jìn)，產(chǎn)生新的坐標(biāo)｝Newy:=y+FangXiang[i,2];Road[Newx,Newy]:=3;｛來(lái)到新位置后，設(shè)置已走過(guò)標(biāo)志｝If(NewX=WayOut[1])and(NewY=WayOut[2])ThenOutputElseHowgo(Newx,NewY);｛如到出口則輸出，否則下一步遞歸｝Road[Newx,Newy]:=2;｛堵死某一方向，不讓再走，以免打轉(zhuǎn)｝end;end;End;Begintotal:=0;Road[wayin[1],wayin[2]]:=3;｛入口坐標(biāo)設(shè)置已走標(biāo)志｝Howgo(wayin[1],wayin[2]);｛從入口處開(kāi)始搜索｝writeln('Totalis',total);｛統(tǒng)計(jì)總數(shù)｝【題目】一筆畫(huà)問(wèn)題從某一點(diǎn)出發(fā)，經(jīng)過(guò)每條邊一次且僅一次.(具體圖見(jiàn)高級(jí)本P160)【參考程序】constmax=6;｛頂點(diǎn)數(shù)為6｝typeshuzu=array[1..max,1..max]of0..max;consta:shuzu｛圖的描述與定義1:連通;0:不通｝=((0,1,0,1,1,1),(1,0,1,0,1,0),(0,1,0,1,1,1),(1,0,1,0,1,1),(1,1,1,1,0,0),(1,0,1,1,0,0));varbianshu:array[1..max]of0..max;｛與每一條邊相連的邊數(shù)｝path:array[0..1000]ofinteger;｛記錄畫(huà)法,只記錄頂點(diǎn)｝zongbianshu,ii,first,i,total:integer;procedureoutput(dep:integer);｛輸出各個(gè)頂點(diǎn)的畫(huà)法順序｝varsum,i,j:integer;begininc(total);writeln('total:',total);fori:=0todepdowrite(Path[i]);writeln;end;functionok(now,i:integer;varnext:integer):boolean;｛判斷第I條連接邊是否已行過(guò)｝varj,jj:integer;beginj:=0;jj:=0;whilejj<>idobegininc(j);ifa[now,j]<>0theninc(jj);end;next:=j;｛判斷當(dāng)前頂點(diǎn)的第I條連接邊的另一端是哪個(gè)頂點(diǎn)，找出后賦給NEXT傳回｝ok:=true;if(a[now,j]<>1)thenok:=false;｛A[I,J]=0:原本不通｝procedureinit;｛初始化｝vari,j:integer;begintotal:=0;｛方案總數(shù)｝zongbianshu:=0;｛總邊數(shù)｝fori:=1tomaxdoforj:=1tomaxdoifa[i,j]<>0thenbegininc(bianshu[i]);inc(zongbianshu);end;｛求與每一邊連接的邊數(shù)bianshu[i]｝zongbianshu:=zongbianshudiv2;｛圖中的總邊數(shù)｝end;procedurefind(dep,nowpoint:integer);｛dep:畫(huà)第幾條邊;nowpoint:現(xiàn)在所處的頂點(diǎn)｝vari,next,j:integer;beginfori:=1tobianshu[nowpoint]do｛與當(dāng)前頂點(diǎn)有多少條相接，則有多少種走法｝ifok(nowpoint,i,next)thenbegin｛與當(dāng)前頂點(diǎn)相接的第I條邊可行嗎？｝｛如果可行，其求出另一端點(diǎn)是NEXT｝a[nowpoint,next]:=2;a[next,nowpoint]:=2;｛置成已走過(guò)標(biāo)志｝path[dep]:=next;｛記錄頂點(diǎn)，方便輸出｝ifdep<zongbianshuthenfind(dep+1,next)｛未搜索完每一條邊｝elseoutput(dep);path[dep]:=0;｛回溯｝a[nowpoint,next]:=1;a[next,nowpoint]:=1;end;begininit;｛初始化，求邊數(shù)等｝forfirst:=1tomaxdo｛分別從各個(gè)頂點(diǎn)出發(fā),嘗試一筆畫(huà)｝fillchar(path,sizeof(path),0);path[0]:=first;｛記錄其起始的頂點(diǎn)｝writeln('frompoint',first,':');readln;find(1,first);｛從起始點(diǎn)first,一條邊一條邊地畫(huà)下去｝【題目】城市遍歷問(wèn)題.給出六個(gè)城市的道路連接圖，找出從某一城市出發(fā)，遍歷每個(gè)城市一次且僅一次的最短路徑及其路程長(zhǎng)度.(圖見(jiàn)高級(jí)本P147｝【參考程序】consta:array[1..6,1..6]of0..10｛城市間連接圖.數(shù)字表示兩城市間的路程｝=((0,4,8,0,0,0),(4,0,3,4,6,0),(8,3,0,2,2,0),(0,4,2,0,4,9),(0,6,2,4,0,4),(0,0,0,9,4,0));varhad:array[1..6]ofboolean;｛某個(gè)城市是否已到過(guò)｝pathmin,path:array[1..6]ofinteger;｛記錄遍歷順序｝ii,first,i,summin,total:integer;procedureoutput(dep:integer);sum,i,j:integer;sum:=0;i:=26｛求這條路的路程總長(zhǎng)｝ifsum><6thenfind(dep+1)elseoutput(dep);had[i]:=false;｛回溯｝path[dep]:=0;end;end;beginforfirst:=1to6dobegin｛輪流從每一個(gè)城市出發(fā),尋找各自的最短路｝fillchar(had,sizeof(had),false);fillchar(path,sizeof(path),0);total:=0;SumMin:=maxint;｛最短路程｝path[1]:=first;had[first]:=true;｛處理出發(fā)點(diǎn)的城市信息，記錄在冊(cè)并置到過(guò)標(biāo)志｝find(2);｛到下一城市｝writeln('fromcity',first,'start,totalis:',total,'theminsum:',summin);fori:=1to6dowrite(PathMin[i]);writeln;｛輸出某個(gè)城市出發(fā)的最短方案｝end;end.【題目】棋子移動(dòng)問(wèn)題[參考程序]constn=3;