1、【題目1】N皇后問題（八皇后問題的擴展）題目2】排球隊員站位問題【題目3】把自然數(shù)N分解為若干個自然數(shù)之和?！绢}目4】把自然數(shù)N分解為若干個自然數(shù)之積。題目5】馬的遍歷問題。題目6】加法分式分解題目7】地圖著色問題【題目8】在n*n的正方形中放置長為2,寬為1的長條塊，題目9】找迷宮的最短路徑。（廣度優(yōu)先搜索算法）題目10】火車調度問題題目11】農(nóng)夫過河題目12】七段數(shù)碼管問題。題目13】把1-8這8個數(shù)放入下圖8個格中,要求相鄰的格（橫,豎,對角線）上填的數(shù)不連續(xù).【題目14】在4x4的棋盤上放置8個棋，要求每一行，每一列上只能放置2個.題目15】迷宮問題.求迷宮的路徑.（深度優(yōu)先搜索法）題

2、目16】一筆畫問題題目17】城市遍歷問題.題目18】棋子移動問題【題目19】求集合元素問題（1,2x+1,3X+1類）【題目】N皇后問題（含八皇后問題的擴展，規(guī)則同八皇后）：在N*N的棋盤上，放置N個皇后，要求每一橫行每一列，每一對角線上均只能放置一個皇后，問可能的方案及方案數(shù)。constmax=8;vari,j:integer;a:array1.maxof0.max;放皇后數(shù)組b:array2.2*maxofboolean;/對角線標志數(shù)組c:array-（max-1）.max-1ofboolean;對角線標志數(shù)組col:array1.maxofboolean;列標志數(shù)組total:inte

3、ger;統(tǒng)計總數(shù)procedureoutput;輸出vari:integer;beginwrite(No.:4,total+1:2,);fori:=1tomaxdowrite(ai:3);write();if(total+1)mod2=0thenwriteln;inc(total);end;functionok(i,dep:integer):boolean;判斷第dep行第i列可放否beginok:=false;if(bi+dep=true)and(cdep-i=true)and(adep=0)and(coli=true)thenok:=trueend;proceduretry(dep:int

4、eger);vari,j:integer;beginfori:=1tomaxdo每一行均有max種放法ifok(i,dep)thenbeginadep:=i;bi+dep:=false;/對角線已放標志cdep-i:=false;對角線已放標志coli:=false;列已放標志ifdep=maxthenoutputelsetry(dep+1);遞歸下一層adep:=0;取走皇后,回溯bi+dep:=true;恢復標志數(shù)組cdep-i:=true;coli:=true;end;end;beginfori:=1tomaxdobeginai:=0;coli:=true;end;fori:=2to2*

5、maxdobi:=true;fori:=-(max-1)tomax-1doci:=true;total:=0;try(1);writeln(total:,total);end.【測試數(shù)據(jù)】n=8八皇后問題No.115863724No.216837425No.317468253No.417582463No.524683175No.625713864No.725741863No.826174835No.926831475No.1027368514No.1127581463No.1228613574No.1331758246No.1435281746No.1535286471No.163571428

6、6No.1735841726No.1836258174No.1936271485No.2036275184No.2136418572No.2236428571No.2336814752No.2436815724No.2536824175No.2637285146No.2737286415No.2838471625No.2941582736No.3041586372No.3142586137No.3242736815No.3342736851No.3442751863No.3542857136No.3642861357No.3746152837No.3846827135No.3946831752

7、No.4047185263No.4147382516No.4247526138No.4347531682No.4448136275No.4548157263No.4648531726No.4751468273No.4851842736No.4951863724No.5052468317No.5152473861No.5252617483No.5352814736No.5453168247No.5553172864No.5653847162No.5757138642No.5857142863No.5957248136No.6057263148No.6157263184No.6257413862N

8、o.6358413627No.6458417263No.6561528374No.6662713584No.6762714853No.6863175824No.6963184275No.7063185247No.7163571428No.7263581427No.7363724815No.7463728514No.7563741825No.7664158273No.7764285713No.7864713528No.7964718253No.8068241753No.8171386425No.8272418536No.8372631485No.8473168524No.8573825164No

9、.8674258136No.8774286135No.8875316824No.8982417536No.9082531746No.9183162574No.9284136275total:92對于N皇后:111皇后N丨41I1115|II6II11|71II118|9|IIII11011I1方案數(shù)丨2|11101141|401192|352111|7241【題目】排球隊員站位問題I圖為排球場的平面圖，其中一、二、三、四、五、六為位置編號,I|二、三、四號位置為前排，一、六、五號位為后排。某隊比賽時,I|一、四號位放主攻手，二、五號位放二傳手，三、六號位放副攻I11手。隊員所穿球衣分別為1,2

10、,3,4,5,6號，但每個隊I四丨三丨二I員的球衣都與他們的站位號不同。已知1號、6號隊員不在后排,I112號、3號隊員不是二傳手，3號、4號隊員不在同一排，5號、I五丨六丨一|6號隊員不是副攻手。1111編程求每個隊員的站位情況?！舅惴ǚ治觥勘绢}可用一般的窮舉法得出答案。也可用回溯法。以下為回溯解法?！緟⒖汲绦颉縯ypesset=setof1.6;vara:array1.6of1.6;d6:=d6-3,6;5,6號隊員不是副攻手d6:=d6-3,6;5,6號隊員不是副攻手d:array1.6ofsset;i:integer;procedureoutput;輸出beginifnot(a3in2

11、,3,4)=(a4in2,3,4)thenbegin3,4號隊員不在同一排write(number:);fori:=1to6dowrite(i:8);writeln;write(weizhi:);fori:=1to6dowrite(ai:8);writeln;end;end;proceduretry(i:integer;s:sset);遞歸過程i:第i個人,s:哪些位置已安排人了varj,k:integer;beginforj:=1to6dobegin每個人都有可能站1-6這6個位置if(jindi)andnot(jins)thenbeginj不在di中，則表明第i號人不能站j位.j如在s集合

12、中，表明j位已排人了ai:=j;第i人可以站j位ifi6thentry(i+1,s+j)未安排妥,則繼續(xù)排下去elseoutput;6個人都安排完,則輸出end;end;end;beginfori:=1to6dodi:=1.6-i;每個人的站位都與球衣的號碼不同d6:=d6-3,6;5,6號隊員不是副攻手d6:=d6-3,6;5,6號隊員不是副攻手d1:=d1-1,5,6;d6:=d6-1,5,6;d2:=d2-2,5;d3:=d3-2,5;d5:=d5-3,6;1,6號隊員不在后排2,3號隊員不是二傳手d6:=d6-3,6;5,6號隊員不是副攻手d6:=d6-3,6;5,6號隊員不是副攻手d

13、6:=d6-3,6;5,6號隊員不是副攻手d6:=d6-3,6;5,6號隊員不是副攻手try(1,);end.【題目】把自然數(shù)N分解為若干個自然數(shù)之和。參考答案】nItotal5176I117I1510I42100I190569291參考程序】varn:byte;num:array0.255ofbyte;total:word;procedureoutput(dep:byte);varj:byte;beginforj:=1todepdowrite(numj:3);writeln;inc(total);end;procedurefind(n,dep:byte);N:待分解的數(shù),DEP:深度vari

14、,j,rest:byte;beginfori:=1tondo每一位從N到1去試ifnumdep-10)thenbeginfind(rest,dep+1);endelseifrest=0thenoutput(dep);剛好相等則輸出numdep:=0;end;end;begin主程序writeln(inputn:);readln(n);fillchar(num,sizeof(num),0);total:=0;num0:=0;find(n,1);writeln(sum=,total);end.【題目】把自然數(shù)N分解為若干個自然數(shù)之積?！緟⒖汲绦颉縱arpath:array1.1000ofinteg

15、er;total,n:integer;procedurefind(k,sum,dep:integer);K:varb,d:Integer;beginifsum=nthen積等于Nbeginwrite(n,=,path1);ford:=2todep-1dowrite(*,pathd);writeln;inc(total);exit;end;ifsumnthenexit;累積大于Nforb:=trunc(n/sum)+1downtokdo每一種可能都去試beginpathdep:=b;find(b,sum*b,dep+1);end;end;beginreadln(n);total:=0;find(

16、2,1,1);writeln(total:,total);readln;end.【題目】馬的遍歷問題。在NM的棋盤中，馬只能走日字。馬從位置(x,y)處出發(fā)，把棋盤的每一格都走一次，且只走一次。找出所有路徑。end;end;【參考程序】深度優(yōu)先搜索法constn=5;m=4;fx:array1.8,1.2of-2.2=(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2);八個方向增量vardep,i:byte;x,y:byte;cont:integer;統(tǒng)計總數(shù)a:array1.n,1.mofbyte;記錄走法數(shù)組procedureou

17、tput;輸出,并統(tǒng)計總數(shù)varx,y:byte;begincont:=cont+1;writeln;writeln(count=,cont);fory:=1tondobeginforx:=1tomdowrite(ay,x:3);writeln;end;readln;halt;end;procedurefind(y,x,dep:byte);vari,xx,yy:integer;beginfori:=1to8dobeginxx:=x+fxi,1;yy:=y+fxi,2;加上方向增量,形成新的坐標if(xxin1.m)and(yyin1.n)and(ayy,xx=0)then判斷新坐標是否出界,是

18、否已走過?beginayy,xx:=dep;走向新的坐標if(dep=n*m)thenoutputelsefind(yy,xx,dep+1);從新坐標出發(fā),遞歸下一層ayy,xx:=0回溯,恢復未走標志end;end;beginend;begincont:=0;fillchar(a,sizeof(a),0);dep:=1;writeln(inputy,x);readln(y,x);x:=1;y:=1;if(yn)or(xm)thenbeginwriteln(x,yerror!);halt;end;ay,x:=1;find(y,x,2);ifcont=0thenwriteln(Noanswer!

19、)elsewrite(TheEnd!);readln;end.【題目】加法分式分解。如：1/2=1/4+1/4.找出所有方案。輸入：NMN為要分解的分數(shù)的分母M為分解成多少項【參考程序】programfenshifenjie;constnums=5;vart,m,dep:integer;n,maxold,max,j:longint;path:array0.numsoflongint;maxok,p:boolean;sum,sum2:real;procedureprint;vari:integer;begint:=t+1;ifmaxok=truethenbeginmaxold:=pathm;ma

20、xok:=false;end;write(NO.,t);fori:=1tomdowrite(,pathi:4);writeln;ifpath1=pathmthenbeginwriteln(Ok!total:,t:4);readln;halt;end;procedureinput;beginwriteln(inputN:);readln(n);writeln(inputM(M=,nums:1,):);readln(m);if(n=0)or(m4)or(nmaxlongint)thenbeginwriteln(InvalidInput!);readln;halt;end;end;functions

21、um1(ab:integer):real;vara,b,c,d,s1,s2:real;i:integer;beginifab=1thensum1:=1/path1elsebegina:=path1;b:=1;c:=path2;d:=1;fori:=1toab-1dobegins2:=(c*b+a*d);s1:=(a*c);a:=s1;b:=s2;c:=pathi+2;end;sum1:=s2/s1;end;end;procedureback;dep:=dep-1;ifdep=m-2thenmax:=maxold;sum:=sum-1/pathdep;j:=pathdep;end;procedu

22、refind;beginrepeatdep:=dep+1;j:=pathdep-1-1;p:=false;repeatj:=j+1;if(depm)and(j=1/nthenp:=falseelsebeginp:=true;pathdep:=j;sum:=sum+1/pathdep;endelseifjmaxthenback;ifdep=mthenbeginpathdep:=j;sum2:=sum1(m);if(sum2)1/nthenp:=false;if(sum2)=1/nthenbeginprint;max:=j;back;end;if(sum2=max)thenback;end;unt

23、ilpuntildep=0;beginINPUT;maxok:=true;fort:=0tomdopatht:=n;dep:=0;t:=0;sum:=0;max:=maxlongint;find;readln;end.【題目】地圖著色問題【參考程序1】constlin:array1.12,1.12of0.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,

24、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:array1.12ofbyte;color數(shù)組放已填的顏色total:integer;functionok(dep,i:byte):boolean;判斷選用色i是否可用vark:byte;條件:相鄰的區(qū)域顏色不能相同begi

25、nfork:=1todepdoif(lindep,k=1)and(i=colork)thenbeginok:=false;exit;end;ok:=true;end;procedureoutput;輸出vark:byte;beginfork:=1to12dowrite(colork,);writeln;total:=total+1;end;procedurefind(dep:byte);參數(shù)dep:當前正在填的層數(shù)vari:byte;beginfori:=1to4dobegin每個區(qū)域都可能是1-4種顏色ifok(dep,i)thenbegincolordep:=i;ifdep=12theno

26、utputelsefind(dep+1);colordep:=0;恢復初始狀態(tài),以便下一次搜索end;end;end;begintotal:=0;總數(shù)初始化fillchar(color,sizeof(color),0);find(1);writeln(total:=,total);end.【參考程序2】constlin數(shù)組:代表區(qū)域相鄰情況lin:array1.12ofsetof1.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,1,2,5,7,11,12,8,11,6,2,12,9,7,2,3,12,8,10,3,4,12,9

27、,11,4,5,12,7,10,5,6,7,8,9,10,11);color:array1.4ofchar=(r,y,b,g);vara:array1.12ofbyte;因有12個區(qū)域，故a數(shù)組下標為1-12total:integer;functionok(dep,i:integer):boolean;判斷第dep塊區(qū)域是否可填第i種色varj:integer;j為什么設成局部變量?beginok:=true;forj:=1to12doif(jinlindep)and(aj=i)thenok:=false;end;procedureoutput;輸出過程varj:integer;j為什么設成局

28、部變量?begininc(total);方案總數(shù)加1write(total:4);輸出一種方案forj:=1to12dowrite(coloraj:2);writeln;end;procedurefind(dep:byte);vari:byte;i為什么設成局部變量?beginfori:=1to4do每一區(qū)域均可從4種顏色中選一beginifok(dep,i)thenbegin可填該色adep:=i;第dep塊區(qū)域填第i種顏色if(dep=12)thenoutput填完12個區(qū)域elsefind(dep+1);未填完adep:=0;取消第dep塊區(qū)域已填的顏色end;end;end;begin

29、主程序fillchar(a,sizeof(a),0);記得要給變量賦初值!total:=0;find(1);writeln(End.);end.【題目】在n*n的正方形中放置長為2,寬為1的長條塊，問放置方案如何【參考程序1】constn=4;vark,u,v,result:integer;a:array1.n,1.nofchar;procedureprintf;輸出beginresult:=result+1;方案總數(shù)加1writeln(-,result,-);forv:=1tondobeginforu:=1tondowrite(au,v);writelnend;writeln;end;pro

30、ceduretry;填放長條塊vari,j,x,y:integer;full:boolean;beginfull:=true;ifktrunc(n*n/2)thenfull:=false;測試是否已放滿iffullthenprintf;放滿則可輸出ifnotfullthenbegin未滿x:=0;y:=1;以下先搜索未放置的第一個空位置repeatx:=x+1;ifxnthenbeginx:=1;y:=y+1enduntilax,y=;找到后,分兩種情況討論ifax+1,y=thenbegin第一種情況:橫向放置長條塊k:=k+1;記錄已放的長條數(shù)ax,y:=chr(k+ord();放置ax+

31、1,y:=chr(k+ord();try;遞歸找下一個空位置放k:=k-1;ax,y:=;ax+1,y:=回溯,恢復原狀end;ifax,y+1=thenbegin第二種情況:豎向放置長條塊k:=k+1;記錄已放的長條數(shù)ax,y:=chr(k+ord(0);放置ax,y+1:=chr(k+ord(0);try;遞歸找下一個空位置放k:=k-1;ax,y:=;回溯,恢復原狀ax,y+1:=end;end;end;begin主程序fillchar(a,sizeof(a),);記錄放置情況的字符數(shù)組,初始值為空格result:=O;k:=0;k記錄已放的塊數(shù)，如果k=n*n/2,則說明已放滿try;

32、每找到一個空位置,把長條塊分別橫放和豎放試驗end.【參考程序2】constdai:array1.2,1.2ofinteger=(0,1),(1,0);typenode=recordw,f:integer;end;vara:array1.20,1.20ofinteger;path:array0.200ofnode;s,m,n,nn,i,j,x,y,dx,dy,dep:integer;p,px:boolean;procedureinputn;beginwrite(inputn);readln(n);n:=4;nn:=n*n;m:=nndiv2;beginbeginend;procedurepri

33、nt;vari,j:integer;begininc(s);writeln(no,s);fori:=1tondobeginforj:=1tondowrite(ai,j:3);writeln;end;writeln;end;functionfg(h,v:integer):boolean;varp:boolean;beginp:=false;if(h=n)and(v=n)thenifah,v=0thenp:=true;fg:=p;end;procedureback;begindep:=dep-1;ifdep=0thenbeginp:=true;px:=true;endelsebegini:=pat

34、hdep.w;j:=pathdep.f;x:=(i-1)divn)+1;y:=imodn;ify=0theny:=n;dx:=x+daij,1;dy:=y+daij,2;ax,y:=0;adx,dy:=0;end;end;end.end.inputn;s:=0;fillchar(a,sizeof(a),0);x:=0;y:=0;dep:=0;path0.w:=0;path0.f:=0;repeatdep:=dep+1;i:=pathdep-1.w;repeati:=i+1;x:=(i-1)divn)+1;y:=imodn;ify=0theny:=n;px:=false;iffg(x,y)the

35、nbeginj:=0;p:=false;repeatinc(j);dx:=x+daij,1;dy:=y+daij,2;iffg(dx,dy)and(j=2thenbackelsep:=false;untilp;endelseifi=nnthenbackelsepx:=false;untilpx;untildep=0;readln;題目】找迷宮的最短路徑。（廣度優(yōu)先搜索算法）end;end;【參考程序】usescrt;constmigong:array1.5,1.5ofinteger=(0,0,-1,0,0),(0,-1,0,0,-1),(0,0,0,0,0),(0,-1,0,0,0),(-1,

36、0,0,-1,0);迷宮數(shù)組fangxiang:array1.4,1.2of-1.1=(1,0),(0,1),(-1,0),(0,-1);方向增量數(shù)組typenode=recordlastx:integer;上一位置坐標lasty:integer;nowx:integer;當前位置坐標nowy:integer;pre:byte;本結點由哪一步擴展而來dep:byte;本結點是走到第幾步產(chǎn)生的end;varlujing:array1.25ofnode;記錄走法數(shù)組closed,open,x,y,r:integer;procedureoutput;vari,j:integer;beginfori:

37、=1to5dobeginforj:=1to5dowrite(migongi,j:4);writeln;end;i:=open;repeatwithlujingidowrite(nowy:2,nowx:2,5)or(y5)or(x1)or(y1)or(migongy,x0)thenbegin未出界,未走過則可視為新的結點inc(open);隊列尾指針加1withlujingopendobegin記錄新的結點數(shù)據(jù)nowx:=x;nowy:=y;Iastx:=lujingclosed.nowx;新結點由哪個坐標擴展而來lasty:=lujingclosed.nowy;dep:=lujingclose

38、d.dep+1;新結點走到第幾步pre:=closed;新結點由哪個結點擴展而來end;migongy,x:=lujingclosed.dep+1;當前結點的覆蓋范圍if(x=5)and(y=5)thenbegin輸出找到的第一種方案writeln(ok,thatsallright);output;halt;end;end;end;untilclosed=open;直到首指針大于等于尾指針,即所有結點已擴展完end.【題目】火車調度問題【參考程序】constmax=10;typeshuzu=array1.maxof0.max;varstack,exitout:shuzu;n,total:int

39、eger;procedureoutput(exitout:shuzu);vari:integer;beginfori:=1tondowrite(exitouti:2);writeln;inc(total);end;procedurefind(dep,have,rest,exit_weizhi:integer;stack,exitout:shuzu);dep:步數(shù),have:入口處有多少輛車;rest:車站中有多少車;exit_weizhi:從車站開出后，排在出口處的位置;stack:車站中車輛情況數(shù)組;exitout:出口處車輛情況數(shù)組vari:integer;begin分入站,出站兩種情況討

40、論ifhave0thenbegin還有車未入站stackrest+1:=n+1-have;入站ifdep=2*nthenoutput(exitout)elsefind(dep+1,have-1,rest+1,exit_weizhi,stack,exitout);end;ifrest0thenbegin還有車可出站exitoutexit_weizhi+1:=stackrest;出站ifdep=2*nthenoutput(exitout)經(jīng)過2n步后，輸出一種方案elsefind(dep+1,have,rest-1,exit_weizhi+1,stack,exitout);end;end;begi

41、nwriteln(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;end.【解法2】用窮舉二進制數(shù)串的方法完成.usescrt;vari,n,m,t:integer;a,s,c:array1.1000ofinteger;proceduretest;vart1,t2,k:integer;notok:boolean;begint1:=0;k:=

42、0;t2:=0;i:=0;notok:=false;repeat二進制數(shù)串中,0表示出棧,1表示入棧i:=i+1;數(shù)串中第I位ifai=1thenbegin第I位為1,則表示車要入棧inc(k);棧中車數(shù)inc(tl);入棧記錄,T1為棧指針,S為棧數(shù)組st1:=k;endelse第I位為0,車要出棧ift11)and(at1)dobeginat:=0;dec(t);at:=at+1;end;untila1=2;readln;end.N:4678TOTAL:141324291430【題目】農(nóng)夫過河。一個農(nóng)夫帶著一只狼，一只羊和一些菜過河。河邊只有一條一船，由于船太小，只能裝下農(nóng)夫和他的一樣東西

43、。在無人看管的情況下，狼要吃羊，羊要吃菜，請問農(nóng)夫如何才能使三樣東西平安過河?！舅惴ǚ治觥繉栴}數(shù)字化。用1代表狼，2代表羊，3代表菜。則在河某一邊物體的分布有以下8種情況。1111物體個數(shù)丨0|11111112|111131111111分布情況丨01111111111|2|3|1,2|1,3|2,311111111|1,2,3|111111代碼之和丨0111111111111|2|3|3|4|5|111111116|111111是否相克丨1111111111|相克|相克|11111111|11當(兩物體在一起而且)代碼和為3或5時，必然是相克物體在一起的情況。【參考程序】constwt:ar

44、ray0.3ofstring5=(,WOLF,SHEEP,LEAVE);varleft,right:array1.3ofinteger;procedureprint_left;輸出左岸的物體vari:integer;fori:=1to3dobeginlefti:=i;righti:=0;end;begintotal:=total+1;write(,total,);第幾次渡河fori:=1to3dowrite(wtlefti);write(|,:4);end;procedureprint_right;輸出右岸的物體vari:integer;beginwrite(:4,|);fori:=1to3d

45、oifrighti0thenwrite(wtrighti);writeln;end;procedureprint_back(who:integer);右岸矛盾時，需從右岸捎物體一左岸vari:integer;beginfori:=1to3dobeginifnot(i=who)or(righti=0)thenbegin要捎回左岸的物體不會時剛剛從左岸帶來的物體，也不會是不在右岸的物體what:=righti;righti:=0;print_left;輸出返回過程write(-,wti);print_right;lefti:=what;物體到達左岸end;end;end;begintotal:=0

46、;repeatfori:=1to3do共有3種物體iflefti0then第1種物體在左岸beginwhat:=lefti;lefti:=O;what:放置將要過河的物體編號left_rest:=left1+left2+left3;求左岸剩余的物體編號總和if(left_rest=3)or(left_rest=5)thenlefti:=what假如左岸矛盾，則不能帶第I種過河，嘗試下一物體else否則可帶過河beginprint_left;輸出過河過程write(-,wti);print_right;righti:=what;物體到達右岸ifleft_rest=0thenhalt;左岸物體已悉

47、數(shù)過河right_rest:=right1+right2+right3;求右岸剩余的物體編號總和if(right_rest=3)or(right_rest=5)thenprint_back(i)右岸有矛盾，要捎物體回左岸elsebeginprint_left;右岸有矛盾，空手回左岸write(-,:5);print_right;end;end;end;untilfalse;不斷往返end.【題目】七段數(shù)碼管問題。從一個數(shù)字變化到其相鄰的數(shù)字只需要通過某些段（數(shù)目不限）1或拿走某些段（數(shù)目不限）來實現(xiàn).但不允許既增加段又拿起段.I|例如:3可以變到9,也可以變到1TOC o 1-5 h z6I7

48、|2iI1iIIIIIIII5|I3IT|一I11IIII411Ifori:=1to3dobeginlefti:=i;righti:=0;end;要求:(1)判斷從某一數(shù)字可以變到其它九個數(shù)字中的哪幾個.(2)找出一種排列這十個數(shù)字的方案,便這樣組成的十位數(shù)數(shù)值最小.typekkk=setof0.9;consta:array-1.9ofsetof1.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:a

49、rray-2.9ofsetof0.9;procedurenumber(p:string;s,l:integer;k:kkk);P：生成的數(shù);s:用了幾個數(shù)字;i:前一個是哪個數(shù)字;k:可用的數(shù)字vari:integer;beginfori:=0to9doif(iink)and(iinbl)thenbegin數(shù)字i未用過，且i可由前一個采用的數(shù)字變化而來ifs=10thenbeginwriteln(Min:,p,i);readln;halt;endelsenumber(p+chr(48+i),s+1,i,k-i);end;end;beginfori:=1to9dobi:=;b-2:=0.9;fo

50、ri:=-1to8doforj:=i+1to9doif(ai=aj)or(aj=ai)thenbeginbi:=bi+j;bj:=bj+abs(i);end;b1:=b1+b-1;fori:=0to9dobeginwrite(i,mayturnto:);forj:=0to9doifjinbithenwrite(j,);writeln;fori:=1to8dowrite(ai);writeln;fori:=1to8dowrite(ai);writeln;forj:=1to8dowrite(aj:2);writeln;end;number(,1,-2,0.9);end.題目】把1-8這8個數(shù)放入下

51、圖8個格中,要求相鄰的格（橫,豎,對角線）上填的數(shù)不連續(xù).II11I1111111111I1111111111111I11II【參考程序】constlin:array1.8ofsetof1.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:array1.8ofinteger;total,i:integer;had:setof1.8;functionok(dep,i:integer):boolean;判斷是否能在第dep格放數(shù)字ivarj:integer;beginok:=true;forj:

52、=1to8do相鄰且連續(xù)則不行if(jinlindep)and(abs(i-aj)=1)thenok:=false;ifiinhadthenok:=false;已用過的也不行end;procedureoutput;輸出一種方案varj:integer;begininc(total);write(total,:);end;procedurefind(dep:byte);vari:byte;beginfori:=1to8dobegin每一格可能放1-8這8個數(shù)字中的一個ifok(dep,i)thenbeginadep:=i;把i放入格中had:=had+i;設置已放過標志if(dep=8)then

53、outputelsefind(dep+1);adep:=10;回溯,恢復原狀態(tài)had:=had-i;end;end;end;beginfillchar(a,sizeof(a),10);total:=0;had:=;find(1);writeln(End.);end.【題目】在4x4的棋盤上放置8個棋，要求每一行，每一列上只能放置2個.【參考程序1】算法:8個棋子,填8次.深度為8.注意判斷是否能放棋子時,兩個兩個為一行.vara:array1.8of0.4;line,bz:array1.4of0.2;line數(shù)組:每行已放多少個的計數(shù)器bz數(shù)組:每列已放多少個的計數(shù)器total:integer

54、;procedureoutput;輸出vari:integer;begininc(total);write(total,:);forj:=1to8dowrite(aj:2);writeln;end;functionok(dep,i:integer):boolean;beginok:=true;ifdepmod2=0then假如是某一行的第2個,其位置必定要在第1個之后if(i=adep-1)thenok:=false;if(bzi=2)or(linedepdiv2=2)thenok:=false;某行或某列已放滿2個end;procedurefind(dep:integer);vari:int

55、eger;beginfori:=1to4dobeginifok(dep,i)thenbeginadep:=i;放在dep行i列inc(bzi);某一列記數(shù)器加1inc(linedepdiv2);某一行記數(shù)器加1ifdep=8thenoutputelsefind(dep+1);dec(bzi);回溯dec(linedepdiv2);adep:=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

56、格)共6種放法constfa:array1.6ofarray1.2of1.4=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4);六種可能放法的行坐標end;end;forj:=1to8dowrite(aj:2);writeln;vara:array1.8of0.4;bz:array1.4of0.2;列放了多少個的記數(shù)器total:integer;procedureoutput;vari:integer;begininc(total);write(total,:);fori:=1to8dowrite(ai);writeln;end;functionok(dep,i:inte

57、ger):boolean;beginok:=true;判斷現(xiàn)在的放法中,相應的兩列是否已放夠2個if(bzfai,1=2)or(bzfai,2=2)thenok:=false;end;procedurefind(dep:integer);vari:integer;beginfori:=1to6dobegin共有6種可能放法ifok(dep,i)thenbegina(dep-1)*2+1:=fai,1;次連續(xù)放置2個a(dep-1)*2+2:=fai,2;inc(bzfai,1);相應的兩列,記數(shù)器均加1inc(bzfai,2);ifdep=4thenoutputelsefind(dep+1);

58、dec(bzfai,1);回溯dec(bzfai,2);a(dep-1)*2+1:=0;a(dep-1)*2+2:=0;end;end;end;writeln;end;writeln;forj:=1to8dowrite(aj:2);writeln;begintotal:=0;fillchar(a,sizeof(a),0);fillchar(bz,sizeof(bz),0);find(1);end.【題目】迷宮問題.求迷宮的路徑.(深度優(yōu)先搜索法)【參考程序1】constRoad:array1.8,1.8of0.3=(1,0,0,0,0,0,0,0),(0,1,1,1,1,0,1,0),(0,0

59、,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:array1.4,1.2of-1.1=(1,0),(0,1),(-1,0),(0,-1);四個移動方向WayIn:array1.2ofbyte=(1,1);入口坐標WayOut:array1.2ofbyte=(8,8);出口坐標Vari,j,Total:integer;ProcedureOutput;vari,j:integer;BeginFori:=1to8d

60、obeginforj:=1to8dobeginifRoadi,j=1thenwrite(#219);1:墻ifRoadi,j=2thenwrite();2:曾走過但不通的路ifRoadi,j=3thenwrite(#03);3:沿途走過的暢通的路ifRoadi,j=0thenwrite();0:原本就可行的路end.forj:=1to8dowrite(aj:2);writeln;end;inc(total);統(tǒng)計總數(shù)readln;end;FunctionOk(x,y,i:byte):boolean;判斷坐標(X,Y)在第I個方向上是否可行VarNewX,NewY:shortint;BeginO