广度优先搜索和深度优先搜索训练题

1、【题目1】N皇后问题（八皇后问题的扩展）题目2】排球队员站位问题【题目3】把自然数N分解为若干个自然数之和。【题目4】把自然数N分解为若干个自然数之积。题目5】马的遍历问题。题目6】加法分式分解题目7】地图着色问题【题目8】在n*n的正方形中放置长为2,宽为1的长条块，题目9】找迷宫的最短路径。（广度优先搜索算法）题目10】火车调度问题题目11】农夫过河题目12】七段数码管问题。题目13】把1-8这8个数放入下图8个格中,要求相邻的格（横,竖,对角线）上填的数不连续.【题目14】在4x4的棋盘上放置8个棋，要求每一行，每一列上只能放置2个.题目15】迷宫问题.求迷宫的路径.（深度优先搜索法）题

2、目16】一笔画问题题目17】城市遍历问题.题目18】棋子移动问题【题目19】求集合元素问题（1,2x+1,3X+1类）【题目】N皇后问题（含八皇后问题的扩展，规则同八皇后）：在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。constmax=8;vari,j:integer;a:array1.maxof0.max;放皇后数组b:array2.2*maxofboolean;/对角线标志数组c:array-（max-1）.max-1ofboolean;对角线标志数组col:array1.maxofboolean;列标志数组total:inte

3、ger;统计总数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;恢复标志数组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.【测试数据】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方案数丨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编程求每个队员的站位情况。【算法分析】本题可用一般的穷举法得出答案。也可用回溯法。以下为回溯解法。【参考程序】typesset=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)未安排妥,则继续排下去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.【题目】把自然数N分解为若干个自然数之和。参考答案】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:待分解的数,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.【题目】把自然数N分解为若干个自然数之积。【参考程序】varpath: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)处出发，把棋盘的每一格都走一次，且只走一次。找出所有路径。end;end;【参考程序】深度优先搜索法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;统计总数a:array1.n,1.mofbyte;记录走法数组procedureou

17、tput;输出,并统计总数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);从新坐标出发,递归下一层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为要分解的分数的分母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区域相邻数组,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数组放已填的颜色total:integer;functionok(dep,i:byte):boolean;判断选用色i是否可用vark:byte;条件:相邻的区域颜色不能相同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);参数dep:当前正在填的层数vari:byte;beginfori:=1to4dobegin每个区域都可能是1-4种颜色ifok(dep,i)thenbegincolordep:=i;ifdep=12theno

26、utputelsefind(dep+1);colordep:=0;恢复初始状态,以便下一次搜索end;end;end;begintotal:=0;总数初始化fillchar(color,sizeof(color),0);find(1);writeln(total:=,total);end.【参考程序2】constlin数组:代表区域相邻情况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个区域，故a数组下标为1-12total:integer;functionok(dep,i:integer):boolean;判断第dep块区域是否可填第i种色varj:integer;j为什么设成局部变量?beginok:=true;forj:=1to12doif(jinlindep)and(aj=i)thenok:=false;end;procedureoutput;输出过程varj:integer;j为什么设成局

28、部变量?begininc(total);方案总数加1write(total:4);输出一种方案forj:=1to12dowrite(coloraj:2);writeln;end;procedurefind(dep:byte);vari:byte;i为什么设成局部变量?beginfori:=1to4do每一区域均可从4种颜色中选一beginifok(dep,i)thenbegin可填该色adep:=i;第dep块区域填第i种颜色if(dep=12)thenoutput填完12个区域elsefind(dep+1);未填完adep:=0;取消第dep块区域已填的颜色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;方案总数加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;记录已放的长条数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;记录已放的长条数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),);记录放置情况的字符数组,初始值为空格result:=O;k:=0;k记录已放的块数，如果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;题目】找迷宫的最短路径。（广度优先搜索算法）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);迷宫数组fangxiang:array1.4,1.2of-1.1=(1,0),(0,1),(-1,0),(0,-1);方向增量数组typenode=recordlastx:integer;上一位置坐标lasty:integer;nowx:integer;当前位置坐标nowy:integer;pre:byte;本结点由哪一步扩展而来dep:byte;本结点是走到第几步产生的end;varlujing:array1.25ofnode;记录走法数组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记录新的结点数据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:步数,have:入口处有多少辆车;rest:车站中有多少车;exit_weizhi:从车站开出后，排在出口处的位置;stack:车站中车辆情况数组;exitout:出口处车辆情况数组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)经过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】用穷举二进制数串的方法完成.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二进制数串中,0表示出栈,1表示入栈i:=i+1;数串中第I位ifai=1thenbegin第I位为1,则表示车要入栈inc(k);栈中车数inc(tl);入栈记录,T1为栈指针,S为栈数组st1:=k;endelse第I位为0,车要出栈ift11)and(at1)dobeginat:=0;dec(t);at:=at+1;end;untila1=2;readln;end.N:4678TOTAL:141324291430【题目】农夫过河。一个农夫带着一只狼，一只羊和一些菜过河。河边只有一条一船，由于船太小，只能装下农夫和他的一样东西

43、。在无人看管的情况下，狼要吃羊，羊要吃菜，请问农夫如何才能使三样东西平安过河。【算法分析】将问题数字化。用1代表狼，2代表羊，3代表菜。则在河某一边物体的分布有以下8种情况。1111物体个数丨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、数过河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.【题目】七段数码管问题。从一个数字变化到其相邻的数字只需要通过某些段（数目不限）1或拿走某些段（数目不限）来实现.但不允许既增加段又拿起段.I|例如:3可以变到9,也可以变到1TOC o 1-5 h z6I7

48、|2iI1iIIIIIIII5|I3IT|一I11IIII411Ifori:=1to3dobeginlefti:=i;righti:=0;end;要求:(1)判断从某一数字可以变到其它九个数字中的哪几个.(2)找出一种排列这十个数字的方案,便这样组成的十位数数值最小.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：生成的数;s:用了几个数字;i:前一个是哪个数字;k:可用的数字vari:integer;beginfori:=0to9doif(iink)and(iinbl)thenbegin数字i未用过，且i可由前一个采用的数字变化而来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个数放入下

51、图8个格中,要求相邻的格（横,竖,对角线）上填的数不连续.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格放数字ivarj:integer;beginok:=true;forj:

52、=1to8do相邻且连续则不行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个数字中的一个ifok(dep,i)thenbeginadep:=i;把i放入格中had:=had+i;设置已放过标志if(dep=8)then

53、outputelsefind(dep+1);adep:=10;回溯,恢复原状态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数组:每行已放多少个的计数器bz数组:每列已放多少个的计数器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);某一列记数器加1inc(linedepdiv2);某一行记数器加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;列放了多少个的记数器total:integer;procedureoutput;vari:integer;begininc(total);write(total,:);fori:=1to8dowrite(ai);writeln;end;functionok(dep,i:inte

57、ger):boolean;beginok:=true;判断现在的放法中,相应的两列是否已放够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;次连续放置2个a(dep-1)*2+2:=fai,2;inc(bzfai,1);相应的两列,记数器均加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.【题目】迷宫问题.求迷宫的路径.(深度优先搜索法)【参考程序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);迷宫数组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);统计总数readln;end;FunctionOk(x,y,i:byte):boolean;判断坐标(X,Y)在第I个方向上是否可行VarNewX,NewY:shortint;BeginO