資源描述：
《廣度優(yōu)先搜索和深度優(yōu)先搜索訓(xùn)練題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、【題目1】N皇后問題(八皇后問題的擴展)【題目2】排球隊員站位問題【題目3】把自然數(shù)Ｎ分解為若干個自然數(shù)之和?！绢}目4】把自然數(shù)Ｎ分解為若干個自然數(shù)之積?！绢}目5】馬的遍歷問題?！绢}目6】加法分式分解【題目7】地圖著色問題【題目8】在n*n的正方形中放置長為2,寬為1的長條塊,【題目9】找迷宮的最短路徑。（廣度優(yōu)先搜索算法）【題目10】火車調(diào)度問題【題目11】農(nóng)夫過河【題目12】七段數(shù)碼管問題。【題目13】把1-8這8個數(shù)放入下圖8個格中,要求相鄰的格(橫,豎,對角線)上填的數(shù)不連續(xù).【題目14】在4×4的棋盤上放置8個棋,要求每一行,每一列上只能放置2個.【題目1
2、5】迷宮問題.求迷宮的路徑.(深度優(yōu)先搜索法)【題目16】一筆畫問題【題目17】城市遍歷問題.【題目18】棋子移動問題【題目19】求集合元素問題（1,2x+1,3X+1類)??【題目】N皇后問題(含八皇后問題的擴展，規(guī)則同八皇后)：在N*N的棋盤上，放置N個皇后，要求每一橫行每一列，每一對角線上均只能放置一個皇后，問可能的方案及方案數(shù)。constmax=8;vari,j:integer;a:array[1..max]of0..max;??{放皇后數(shù)組}b:array[2..2*max]ofboolean;??????{/對角線標(biāo)志數(shù)組}c:array[-(max-1
3、)..max-1]ofboolean;{對角線標(biāo)志數(shù)組}col:array[1..max]ofboolean;{列標(biāo)志數(shù)組}total:integer;????{統(tǒng)計總數(shù)}?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;?{/對角線已放標(biāo)志}???????c[dep-i]:=false;?{對角線已放標(biāo)志}???????col[i]:=false;???{列已放標(biāo)志}???????ifdep=maxthenoutput??????????????elsetry(dep+1);{遞歸下一層}???????a[dep]:=0;??????{取走皇后,回溯}???????b[i+dep]:=true;??{恢復(fù)標(biāo)志數(shù)組}???????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.?【測試數(shù)據(jù)】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?
