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

《广度优先搜索和深度优先搜索训练题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、5】迷宫问题.求迷宫的路径.(深度优先搜索法)【题目16】一笔画问题【题目17】城市遍历问题.【题目18】棋子移动问题【题目19】求集合元素问题（1,2x+1,3X+1类)  【题目】N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。constmax=8;vari,j:integer;a:array[1..max]of0..max;  {放皇后数组}b:array[2..2*max]ofboolean;      {/对角线标志数组}c:array[-(max-1

3、)..max-1]ofboolean;{对角线标志数组}col:array[1..max]ofboolean;{列标志数组}total:integer;    {统计总数} procedureoutput;{输出}vari:integer;begin    write('No.':4,'[',total+1:2,']');    fori:=1tomaxdowrite(a[i]:3);write('    ');    if(total+1)mod2=0then writeln; inc(total);end; function ok(i,dep:integer)

4、:boolean; {判断第dep行第i列可放否}begin      ok:=false;      if(b[i+dep]=true)and(c[dep-i]=true){and(a[dep]=0)}and              (col[i]=true)then  ok:=trueend; proceduretry(dep:integer);vari,j:integer;begin    fori:=1tomaxdo   {每一行均有max种放法}      if ok(i,dep)thenbegin       a[dep]:=i;       b[i+

5、dep]:=false; {/对角线已放标志}       c[dep-i]:=false; {对角线已放标志}       col[i]:=false;   {列已放标志}       ifdep=maxthenoutput              elsetry(dep+1);{递归下一层}       a[dep]:=0;      {取走皇后,回溯}       b[i+dep]:=true;  {恢复标志数组}       c[dep-i]:=true;       col[i]:=true;      end;end; begin    fori:=

6、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. 【测试数据】n=8八皇后问题 No.[1] 1 5    8 6 3 7 2 4     No.[2] 1 6 8    3 7 4 2 5 No.[3] 1 7    4 6 8 2 5 3     No.[4] 1 7 5    8 2 4

7、 6 3 No.[5] 2 4    6 8 3 1 7 5     No.[6] 2 5 7    1 3 8 6 4 No.[7] 2 5    7 4 1 8 6 3     No.[8] 2 6 1    7 4 8 3 5 No.[9] 2 6    8 3 1 4 7 5     No.[10] 2 7 3    6 8 5 1 4 No.[11] 2 7    5 8 1 4 6 3     No.[12] 2 8 6    1 3 5 7 4 No.[13] 3 1    7 5 8 2 4 6     No.[14] 3 5 2    8 1