內(nèi)容信息學搜索

1、搜索福州一中 陳穎 搜索專題教學設計 1.知識目標 2.能力目標 3.問題設計活動設計 1.專題測試討論 2.學生自我命題測試討論 3.網(wǎng)上問題解決提交,如 /教學設計知識目標1.搜索解決問題的思維方式2.狀態(tài)空間分析:狀態(tài)與狀態(tài)轉移3.基本搜索策略:深度優(yōu)先搜索(DFS)廣度優(yōu)先搜索(BFS)4.DFS與BFS的程序框架5.搜索的瓶頸與策略6.擴展:盲目搜索的各種算法1、審題能力；2、深入的分析問題能力；3、數(shù)學分析與猜想能力；4、細節(jié)處理能力；5、程序設計能力。能力目標問題設計如何通過恰當問題設計基礎達到上述的教學目標.什么是搜索？搜索是對一個問題不斷地尋找可行方案，然后找到最優(yōu)的可行方案

2、。搜索實質(zhì)上是枚舉，但它與枚舉又不完全相同。枚舉 枚舉對問題的所有可能解的狀態(tài)集合進行一次掃描或遍歷。在具體的程序?qū)崿F(xiàn)過程中，可以通過循環(huán)和條件判斷語句來完成。枚舉法常用于解決“是否存在”或“有多少種可能”等類型的問題。例如，求解不定方程的問題就可以采用列舉法。 適用枚舉法求解的問題必須滿足兩個條件： 可預先確定每個狀態(tài)的元素個數(shù)n； 狀態(tài)元素a1，a2，an的可能值為一個連續(xù)的值域。設 ai1狀態(tài)元素ai的最小值；aik狀態(tài)元素ai的最大值(1in)，即a11a1a1k，a21a2a2k， ai1aiaik，an1anankfor a1a11 to a1k do fo a2a21 to a2

3、k do for aiai1 to aik do for anan1 to ank do if 狀態(tài)(a1，ai，an)滿足檢驗條件 then 輸出問題的解； 搜索：一般是通過狀態(tài)轉移不斷地尋找目標狀態(tài)或最優(yōu)狀態(tài)。 狀態(tài)：是對問題在某一時刻的進展情況的數(shù)學描述 狀態(tài)擴展：是問題從一種狀態(tài)轉移到另一種狀態(tài)的操作。問題:八皇后 八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的數(shù)學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。 高斯認為有76種方案。1854年在柏林的象棋雜

4、志上不同的作者發(fā)表了40種不同的解，后來有人解出92種結果。 現(xiàn)在請你輸出這92種解。用*代表皇后，#代表棋盤格。1.人工模擬完成問題(1)搜索解決問題的思維方式:首先選擇搜索對象，接著分析搜索對象的狀態(tài)空間。(2)問題的狀態(tài)空間:搜索的過程實際是在遍歷一個隱式圖,它的結點是所有的狀態(tài),有向邊對應于狀態(tài)轉移,而一個可行解就是一條從起始結點出發(fā)到目標狀態(tài)集中任意一個結點的路徑,這個圖稱為狀態(tài)空間,這樣的搜索稱為狀態(tài)空間搜索,得到的遍歷樹稱為解答樹.狀態(tài) 狀態(tài)轉移 狀態(tài)可行 可行解2.狀態(tài)描述(1)每行皇后放置位置:An(2)可行狀態(tài)判定方法:pd:array1.8 of boolean;pd1:

5、array2.16 of boolean;pd2:array-7.7 of boolean; 1 2 3 4 5 6 7 8123456783.搜索策略DFS程序框架Procedure com(n:byte);beginfor i:=1 to 8 doif(pdi=false)and(pd1n+i=false)and(pd2n-i=false)thenBegin狀態(tài)轉移an:=i;pdi:=true;pd1n+i:=true;pd2n-i:=true;if(n=max)then begin inc(s);print; endelse com(n+1);an:=0;pdi:=false;pd1n

6、+i:=false;pd2n-i:=false;回溯end;end;深度優(yōu)先搜索DFS框架問題1:迷宮(maze) 【問題描述】 給定一個N*M方格的迷宮，迷宮里有T處障礙，障礙處不可通過。給定起點坐標和終點坐標，問每個方格最多經(jīng)過1次，有多少種從起點坐標到終點坐標的方案。在迷宮中移動有上下左右四種方式。保證起點上沒有障礙?！据斎胛募?第一行N、M和T，N為行，M為列，T為障礙總數(shù)。 第二行起點坐標SX,SY，終點坐標FX,FY。 接下來T行，每行為障礙的坐標?！据敵鑫募?給定起點坐標和終點坐標，問每個方格最多經(jīng)過1次，從起點坐標到終點坐標的方案總數(shù)?！緲永斎搿? 2 11 1 2 21

7、 2【樣例輸出】1【數(shù)據(jù)規(guī)?！?=N,Mn)or(nxm)or(ny1) then continue; if (visitnx,ny=false) then begin visiti,j:=true; if not(nx=fx)and(ny=fy) then search(nx,ny) else ans:=ans+1; visiti,j:=false; end; end;end;【問題描述】 N+Q是班長。在校運動會上，N+Q班要進行隊列表演。N+Q要選出2*N名同學編隊，每人都被編上一個號，每一個從1到N的自然數(shù)都被某2名同學佩戴，現(xiàn)在要求將他們排成一列，使兩個編號為1的同學中間恰好夾1名同

8、學，兩個編號為2的同學中間恰好夾2名同學，兩個編號為N的同學中間恰好夾N名同學，N+Q希望知道這樣的排法能否實現(xiàn)?！据斎胛募枯斎胛募H包括一行，即要處理的N。【輸出文件】輸出文件有兩種情況，如果這樣的排法能實現(xiàn)，則輸出排列順序；如果這樣的排法不能實現(xiàn)，則輸出“No Solution.”。格式如樣例所示。問題2Line 問題簡述 給出一個數(shù)N。然后將1至N這N個數(shù)每個數(shù)字使用兩次來構造序列，使序列中數(shù)字為i的兩項中間恰好有i個數(shù)，求滿足該條件的序列。 【樣例輸入】3【樣例輸出】3 1 2 1 3 2【數(shù)據(jù)規(guī)?！?=N=761.狀態(tài)空間及描述(1)定義lin數(shù)組存放排列。 搜索對象：數(shù)字。 每個

9、數(shù)字搜索的狀態(tài)空間為lin數(shù)組序列的第1位至第2N位;(2)當在序列第i位和序列第i+t+1位上能夠放入數(shù)字，則將第i位和第i+t+1位上放置數(shù)字t，然后遞歸放置t+1。如果不符合放置條件則退回t重新搜索。當t=n時輸出。 請考慮搜索序的選擇，T值從小到大搜索還是從大到小搜索？考查搜索樹的形態(tài)：（1）T值從小到大：第一層即T=1時，有2n-2分支選擇。（2）T值從大到?。旱谝粚蛹碩=n時，有n-1分支選擇。 相比較，（1）的搜索樹形態(tài)要比（2）的搜索樹形態(tài)寬得多。 因些直觀分析倒序搜索能夠更快得到解. 試驗不同的搜索序程序得到解的效率. 結論:對搜索問題的解決,搜索序的選擇將影響得到問題的解的

10、效率.3.程序框架procedure search(layer:longint);Begin /layer值從大到小搜索，當為0時搜索結束if layer=0 then begin ok:=true;exit;end;for l:=1 to (n+n-1-layer) do /搜索能夠放置位置if (linel=0)and(linel+layer+1=0)thenbegin /能放入，存放該數(shù)linel:=layer;linel+layer+1:=layer;search(layer-1); /繼續(xù)放入下一個數(shù)linel:=0;linel+layer+1:=0;end;end;4.無解判斷 最

11、耗時的是無解狀態(tài)，如果能時先將情況排除，程序的效率就快多了。方法1： 打表發(fā)現(xiàn)規(guī)律方法2： 數(shù)學方法分析，被夾住的數(shù)的個數(shù)分別為1,2,n，被夾住的數(shù)的總數(shù)為 (1+n)*n/2。如果這個數(shù)是奇數(shù)，無解。主程序procedure main;begin fillchar(line,sizeof(line),0); ok:=false; if (n+1)*n div 2 and 1=0 then /有解情況的判定。其中，i and 1的結果相當于i mod 2。這里用位運算代替較慢的模運算。 search(n); if ok then begin for j:=1 to n*2-1 write(l

12、inej, ); writeln(linek); end else writeln(No Solution.);end;【問題描述】 在Q迷的千呼萬喚之下，N+Q終于推出了新專輯My Cow Life.其中一首God is a cow更是天籟之音，令Q迷們?yōu)橹畠A倒。可是，讓Q迷們不爽的是，這張專輯是限量發(fā)行的，并且價格.許多Q迷們在音像店前排起了長隊，想要買到一張CD或者磁帶。SGaPb小店的店長SGaPb是個熱心人。他看到這么多Q迷想要買專輯，就設計了一個小游戲抽獎。規(guī)則是這樣的：每位Q迷可以抽到一張獎券。獎券上寫有1到M這M個自然數(shù)。Q迷可以在這M個數(shù)中任意選取N個不同的數(shù)打圈。每個Q迷只

13、能買一張獎券，不同的獎券上的選擇不同。每次抽獎將抽出兩個自然數(shù)X和Y。如果某人拿到的獎券上，所選N個自然數(shù)的倒數(shù)和，恰好等于X/Y，則他將免費獲得一張CDMy Cow Life。 現(xiàn)在,已知抽獎結果X和Y。作為N+Q的fans，你的任務是:求出必須準備多少CD，才能保證支付所有獲獎者。且對于同一種選數(shù), SGaPb只用支付一盤CD。問題3問題簡述 求在M個數(shù)中取N個數(shù)，它們的倒數(shù)和為X/Y的組數(shù)。 【輸入文件】輸入有且僅有一行，就是用空格分開的四個整數(shù)N，M，X，Y。【輸出文件】輸出有且僅有一行，即所需準備的CD數(shù)量?！緲永斎搿? 4 3 4【樣例輸出】1【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)，1=N

14、=M=15對于60%的數(shù)據(jù)，1=N=M=20對于100%的數(shù)據(jù)，1=N=M=25，X=25,Y=25算法分析1、搜索對象：N個數(shù)2、搜索狀態(tài)：第1個數(shù)為1M,第2個數(shù)為2M,第i個數(shù)為上一個數(shù)T+1M.3、滿足條件：從M個數(shù)中搜索選擇N個數(shù)，當它們的倒數(shù)和與X/Y相等，組數(shù)累加器SUM加1。4、參數(shù)設置：（1）當前數(shù)；（2）搜索到了幾個數(shù)；（3）累加的倒數(shù)和初步框架：Procedure DFS(T,Total:Longint;Sum:TIndex);T代表數(shù)，TOTAL代表SUM中加入了多少數(shù)，SUM代表倒數(shù)和 Begin If Total=N Then /選出了n個數(shù) Begin /當?shù)箶?shù)和

15、與x/y的誤差小于一定值，找到一個解。If Abs(Sum-Final)=Seed Then Inc(Ans);Exit;/退出當前層遞歸 End; For I:=T+1 to M do出 /繼續(xù)選下一個數(shù) DFS(I,Total+1,Sum+SI); End;2、剪枝處理（1）搜索的起始值要比上一層搜索的起始值要大，這樣既可以減少運行的時間，又可以避免重復解； （2）可行性剪枝 在每一次搜索前，如果當前搜索到數(shù)的倒數(shù)和+接下去要搜索的所有數(shù)倒數(shù)和小于X/Y，那就沒有可能得出 一個解。我們可以中止它； 如果當前枚舉值的倒數(shù)加上+上一層的和大于X/Y，也可以掐掉。結論： 可行性剪枝是常用的一種剪

16、枝手法 REMARK1、實數(shù)處理中的誤差處理；2、常數(shù)項優(yōu)化，如：每處數(shù)倒數(shù)事先預處理好，避免在搜索過程中重復運算程序框架Procedure DFS(T,Total:Longint;Sum:TIndex);T代表數(shù)，TOTAL代表SUM中加入了多少數(shù)，SUM代表倒數(shù)和BeginIf Total=N Then /選出了n個數(shù)且倒數(shù)和與x/y的誤差小于一定值，找到一個解。BeginIf Abs(Sum-Final)M)or(TotalN)or(Sum+ST*(N-Total)Final+Seed)判斷當前和加上剩余能加的N-Total個數(shù)的最小倒數(shù)和比終值還大剪枝 Then Exit; For I

17、:=T+1 to M doDFS(I,Total+1,Sum+SI);End;問題4 AP數(shù)【問題描述】 正整數(shù)n是無窮的，但其中有些數(shù)有神奇的性質(zhì)，我們給他個名字AP數(shù)。 對于一個數(shù)字i他是AP數(shù)的充要條件是所有比他小的數(shù)的因數(shù)個數(shù)都沒有i的因數(shù)個數(shù)多。比如6的因數(shù)是1 2 3 6 共計有4個因數(shù)。他就是一個AP數(shù)（1-5的因數(shù)個數(shù)不是2就是3）。我們題目的任務就是找到一個最大的，且不超過n的AP數(shù)?！据斎胛募棵總€測試點可能擁有多組數(shù)據(jù)。請用seekeof來確認是否已讀完對于每一行有一個n，如題目所描述【輸出文件】對于每一行輸出最大的且不超過n的AP數(shù)【樣例輸入】1000【樣例輸出】840

18、【數(shù)據(jù)規(guī)?！縩2，則存在質(zhì)數(shù)p，滿足ppn，且p不是A的質(zhì)因子。這時我們可將pn換成p，A變小了，但所含有的約數(shù)個數(shù)卻沒變。這與A是AP矛盾。 性質(zhì)二：令A= p1x1*p2x2*pnxn（p1，p2pn均為質(zhì)數(shù)）。若A是AP數(shù)，那么x1x2xn。 同樣的，我們用反證法來證明，若xixj（i6*109，故我們只用考慮從2到29內(nèi)的質(zhì)數(shù)即可。這樣，確定了搜索對象，枚舉2到29中質(zhì)數(shù)上的因子就可以得到最大的反質(zhì)數(shù)了?！舅惴ㄔO計】1、搜索對象：2,3,5,7,11,13,17,19,23,29十個質(zhì)數(shù)；2、搜索狀態(tài)：每個質(zhì)數(shù)取多少個，最多為20個，根據(jù)性質(zhì)2， 質(zhì)數(shù)指數(shù)x1x2xn，因些，每個質(zhì)數(shù)的

19、搜索狀態(tài)為：1-i個（i為上一個質(zhì)數(shù)的個數(shù)）；3、搜索參數(shù)：k,now,m,lim 分別表示第k個質(zhì)數(shù)，產(chǎn)生的乘積，約數(shù)的個數(shù)，下一個質(zhì)數(shù)搜索范圍；4、判斷條件：（1）質(zhì)數(shù)乘積小于N；（2）約數(shù)的個數(shù)最多；（3）相同約數(shù)的個數(shù)中的最小乘積為AP數(shù)。 procedure dfs(k,now,m:longint;lim:longint);k第幾個質(zhì)數(shù),now質(zhì)數(shù)乘積,m約數(shù)個數(shù)，lim質(zhì)數(shù)指數(shù)搜索范圍Vari:longint; p:int64;beginif (mmax) and (now=n) thenbegin /記下當前最大約數(shù)個數(shù)max:=m;ans:=maxint;end;if (m=m

20、ax) and (nowans) and (now10 then exit;p:=now;for i:=1 to lim do/搜索質(zhì)數(shù)指數(shù)beginif p*primekn then break;p:=p*primek;/求乘積dfs(k+1,p,m*(I+1),i);/遞歸end;end; 本題分析特點：充分挖掘數(shù)據(jù)的特征性質(zhì)，縮小了搜索范圍，挖掘利用問題自身的性質(zhì)進行剪枝，達到了優(yōu)化的目的。 搜索問題著眼點1）簡化問題：突出問題的核心，用數(shù)學描述問題的狀態(tài)空間狀態(tài)、狀態(tài)轉移；2）問題的條件分析：顯式條件、隱式條件、問題轉化；3）搜索策略：搜索對象、搜索順序、結點擴展順序；4）剪技：可行性

21、剪技、最優(yōu)性剪技、充分抓住問題給予的條件剪技；5）常數(shù)項優(yōu)化：數(shù)據(jù)結構選擇與利用，預處理，判重算法的選擇，6）其他：細節(jié)處理、程序設計能力課堂練習：零和問題(zerosum.pas/c/cpp)【問題描述】請考慮一個由1到N（N=3, 4, 5 . 9）的數(shù)字組成的遞增數(shù)列：1 2 3 . N。現(xiàn)在請在數(shù)列中插入“+”表示加，或者“-”表示減，抑或是“ ”表示空白，來將每一對數(shù)字組合在一起（請不在第一個數(shù)字前插入符號）。計算該表達式的結果并注意你是否得到了和為零。請你寫一個程序找出所有產(chǎn)生和為零的長度為N的數(shù)列。【輸入文件】單獨的一行表示整數(shù)N (3 = N (n-1)*10+n) or (S

22、um后兩位組成的數(shù) 或和0 then Last:=Last*10+(s+1) else Last:=Last*10-(s+1);/加空格，本層數(shù)為上一層和s+1合并 Sum:=Sum-LastT+Last;/求和 Signs:= ;/選加空格的操作 Search(s+1); Sum:=SumT; Last:=LastT;/遞歸返回時，獲取斷點的和與參與運算的最后一個數(shù) Sum:=Sum+(s+1);/選加+號的操作 Last:=s+1; Signs:=+; Search(s+1); Sum:=SumT; Last:=LastT;/遞歸返回時，獲取斷點的和與參與運算的最后一個數(shù) Sum:=Sum

23、-(s+1);/選加-號的操作 Last:=-s-1; Signs:=-; Search(s+1); Sum:=SumT; Last:=LastT;/遞歸返回時，獲取斷點的和與參與運算的最后一個數(shù)End;Begin Assign(input,zerosum.in); Reset(input); Assign(output,zerosum.out); Rewrite(output); Readln(n); Sum:=1; Last:=1; Search(1); Close(input); Close(output);End.廣度優(yōu)先搜索例：重排九宮問題游戲 在一個3乘3的九宮中有1-8的8個數(shù)及

24、一個空格隨機擺放在其中的格子里。如下面左圖所示?，F(xiàn)在要求實現(xiàn)這樣的問題：將該九宮調(diào)整為如下圖右圖所示的形式。調(diào)整規(guī)則是：每次只能將與空格（上，下或左，右）相鄰的一個數(shù)字平移到空格中。試編程實現(xiàn)。 28314765123847651、深度優(yōu)先搜索 深度優(yōu)先搜索就是在搜索樹的每一層始終先只擴展一個子節(jié)點，不斷地向縱深前進直到不能再前進（到達葉子節(jié)點或受到深度限制）時，才從當前節(jié)點返回到上一級節(jié)點，沿另一方向又繼續(xù)前進。這種方法的搜索樹是從樹根開始一枝一枝逐漸形成的。 深度優(yōu)先搜索亦稱為縱向搜索。由于一個有解的問題樹可能含有無窮分枝，深度優(yōu)先搜索如果誤入無窮分枝（即深度無限），則不可能找到目標節(jié)點。

25、所以，深度優(yōu)先搜索策略是不完備的。另外，應用此策略得到的解不一定是最佳解（最短路徑）。 深度優(yōu)先搜索的路徑示意圖： 2.廣度優(yōu)先搜索 在深度優(yōu)先搜索算法中，是深度越大的結點越先得到擴展。如果在搜索中把算法改為按結點的層次進行搜索，本層的結點沒有搜索處理完時，不能對下層結點進行處理，即深度越小的結點越先得到擴展，也就是說先產(chǎn)生的結點先得以擴展處理，這種搜索算法稱為廣度優(yōu)先搜索法。 廣度優(yōu)先搜索路徑示意圖： 廣度優(yōu)先搜索算法框架如下：Program bfs;初始化；建立隊列data;設隊列首指針head:=0;隊列尾指針tail：=1；Repeat head 增1，取出head所指節(jié)點進行擴展；

26、For i:=1 to r do begin If 子節(jié)點符合條件且與原有節(jié)點沒有重復 then begin tail 增1 ，并把新節(jié)點存入數(shù)據(jù)庫隊尾； if 新節(jié)點即目標 then 輸出并退出； endif endforuntil head = tail;隊列為空；廣度優(yōu)先搜索特征 使用廣度優(yōu)先搜索法時，離根節(jié)點最近的節(jié)點先擴展，所以廣度優(yōu)先搜索法比較適合求步數(shù)最少解的問題。 問題一迷宮(maze)【問題描述】 給定一個N*M方格的迷宮，迷宮里有T處障礙，障礙處不可通過。給定起點坐標和終點坐標，問每個方格最多經(jīng)過1次。在迷宮中移動有上下左右四種方式。保證起點上沒有障礙。問從起點到終點的最短

27、路徑長度以及輸出一條長度最短的路徑經(jīng)過的點的坐標。 如果不存在起點到終點的路徑則就輸出-1【輸入文件】第一行N、M和T，N為行，M為列，T為障礙總數(shù)。第二行起點坐標SX,SY，終點坐標FX,FY。接下來T行，每行為障礙的坐標?！据敵鑫募咳绻嬖诮獯饎t：第一行 輸出最短路徑的長度K（起點終點也算在步數(shù)內(nèi)）以下K行，每行包含兩個整數(shù)I,J，意為經(jīng)過第I行第J列的點,否則輸出-1【樣例輸入】2 2 11 1 2 21 2【樣例輸出】31 12 12 2深度優(yōu)先搜索程序框架Procedure dfs(x,y,step:Longint);Vari:Longint;Beginif (x=ex)and(y

28、=ey)and(len0)and(x+dxi0)and(y+dyi0)and(x+dxi0)and(y+dyi=m)and(fx+dxi,y+dyi=0) then Begin當前是節(jié)點入隊stacktail.pre:=head;記下前趨節(jié)點stacktail.path:=i;stacktail.x:=x+dxi;入隊stacktail.y:=y+dyi;fx+dxi,y+dyi:=1;入隊節(jié)點標志 if (x+dxi=ex)and(y+dyi=ey) then目標位置 Begin輸出路徑j:=head;從當前點走向入口while (stackj.xsx)or(stackj.ysy) do B

29、egin 求每點的路徑方向 inc(len); pathlen:=stackj.path; j:=stackj.pre; End; writeln(sx, ,sy);/輸出路徑 x:=sx; y:=sy; for j:=len downto 1 doBeginx:=x+dxpathj;y:=y+dypathj;writeln(x, ,y);End; writeln(ex, ,ey);exit; End; inc(tail);隊尾指針加1 End; inc(head);隊頭指針加工1until headtail;分析深度優(yōu)先與廣度優(yōu)先在解決此問題中的效率區(qū)別1.深度優(yōu)先搜索此問題的搜索擴展情況;

30、2.廣深度優(yōu)先搜索此問題的搜索擴展情況;3.效率分析練習：細胞（gene)Description 一個矩形陣列由數(shù)字09組成，數(shù)字19代表細胞，細胞的定義：對于一個細胞數(shù)字的連通塊算是一個細胞，數(shù)字是四連通的，即每個格子與它上下左右四個格子連通。求給定矩形陣列的細胞個數(shù)。Sample input4 10 10345605002045600671 Sample output4Program gene;constdx:array1.4of longint=(-1, 0, 1, 0);dy:array1.4of longint=(0, -1, 0, 1);varmap:array1.50, 1.80

31、of boolean;h:array1.4001, 1.2of longint;n,m,i,j,num:longint;s:string;procedure doing(p,q:longint);vari,head,tail,x,y:longint;begininc(num);mapp,q:=false;head:=1; tail:=1; h1,1:=p; h1,2:=q;repeat for i:=1 to 4 dobegin x:=hhead,1+dxi; y:=hhead,2+dyi; if (x0)and(x0)and(ytail;end;beginassign(input,gene.

32、in);reset(input);assign(output,gene.out);rewrite(output);readln(n,m);for i:=1 to n dobeginreadln(s);for j:=1 to m do mapi,j:=(sj0);end;for i:=1 to n dofor j:=1 to m doif mapi,j then doing(i,j);writeln(num);close(input);close(output);end.Description 古老的顯示屏是由NM個象素（Pixel）點組成的。一個象素點的位置是根據(jù)所在行數(shù)和列數(shù)決定的。例如P(

33、2,1)表示第2行第1列的象素點。那時候，屏幕只能顯示黑與白兩種顏色，人們用二進制0和1來表示。0表示黑色，1表示白色。當計算機發(fā)出一個指令：P(x,y)=1，則屏幕上的第x行第y列的陰極射線管就開始工作，使該象素點顯示白色，若P(x,y)=0，則對應位置的陰極射線管不工作，象素點保持黑色。在某一單位時刻，計算機以NM二維01矩陣的方式發(fā)出顯示整個屏幕圖像的命令。例如，屏幕是由34的 對應屏幕顯示應為：象素點組成，在某單位時刻，計算機發(fā)出如下命令：000100110110假設放大后，一個格子表示一個象素點問題二 由于未知的原因，顯示黑色的象素點總是受顯示白色的象素點的影響可能是陰極射線管工作的

34、作用。并且，距離越近，影響越大。這里的距離定義如下：設有象素點P1(x1,y1)和象素點P2(x2,y2)，則它們之間的距離D(P1,P2)：D(P1,P2)=|x1-x2|+|y1-y2| 在某一時刻，計算機發(fā)出顯示命令后，科學家們期望知道，每個象素點和其最近的顯示白色的象素點之間的最短距離是多少科學家們保證屏幕上至少有一個顯示白色的象素點。 上面的例子中，象素P(1,1)與最近的白色象素點之間的距離為3，而象素P(3,2)本身顯示白色，所以最短距離為0。Input Format第一行有兩個數(shù)字，N和M (1=N,M=182)，表示屏幕的規(guī)格。以下N行，每行M個數(shù)字，0或1。為計算機發(fā)出的顯

35、示命令。Output Format 輸出文件有N行，每行M個數(shù)字，中間用1個空格分開。第i行第j列的數(shù)字表示距象素點P(i,j)最近的白色象素點的最短距離。SampleInput3 4000100110110Output3 2 1 02 1 0 01 0 0 1Limit對于30%的數(shù)據(jù)：N*M=10000；對于100%的數(shù)據(jù)：N*M=1822。題目簡述 輸入一個N*M的01矩陣map，并定義disi,j=|x-i|+|y-j|,0in,0jm(x,y分別為離mapi,j最近且值為1的點的橫坐標和縱坐標)。要求輸出所有的disi,j. 數(shù)據(jù)規(guī)模對于30%的數(shù)據(jù)：N*M=10000；對于100%

36、的數(shù)據(jù)：N*M=1822?！据斎霕永? 4000100110110【輸出樣例】3 2 1 02 1 0 01 0 0 1分析:1.由于是求最短問題,選擇BFS2.考慮數(shù)據(jù)規(guī)模,搜索對象的選擇值得分析算法思路: 思路一： 搜索對象選擇為0的點，都將其向4個方向擴展，直到找到一個為1的點，則根據(jù)廣搜的最優(yōu)性，該點必為mapx,y。這種算法的的時間復雜度為O(mn)2 。選擇每個為0的點需要NM時間,每點擴展需要NM時間 思路二： 搜索對象選擇為1的點。（1）首先將所有“1”的點入隊，并將其的距離記為0。 （2）逐一從隊列中取出點，若設其為P，對點P向上下左右4個方向擴展，遇到為0的節(jié)點，將其值賦

37、為其父節(jié)點的值加1。并入隊。（3）重復以上操作，直至隊空。由于廣搜的最優(yōu)性，搜索樹的第N層的所有節(jié)點的值都是N-1，因此被擴展的節(jié)點的值必為所求的disi,j。該算法的復雜度為O(MN)。每點只擴展一次 000100110110030201100201101001101001預處理 在讀入之前進行一次預處理，邊界賦為0，讀入的時侯，若值為0，將mapi,j值賦為-1 ，若值為1，就將mapi,j設為0，并加入隊列。即先擴展所有值為1的點. 依次取出隊首元素向4個方向進行擴展，遇到值為-1的格子就將其賦為父節(jié)點的值加1，并加入隊尾。由于是逐層擴展,根據(jù)廣搜索的特點,擴展點的值必為距離值為1點的最

38、小值. 最后輸出mapi,j。 主程序 begintop:=1;tail:=1;for i:=1 to n dofor j:=1 to m domapi,j:=-1;for i:=1 to n do/值為0點map設-1, beginfor j:=1 to m do beginread(dat);if dat=1 then/值為1點map設為0 begin/值為1點入隊mapi,j:=0;linextail:=i;lineytail:=j;inc(tail); end; end; if in then readln; end;for i:=1 to n do/加一圈邊界map設為0，省去邊界判

39、斷 beginmapi,0:=0;mapi,m+1:=0; end;for i:=1 to m do beginmap0,i:=0;mapn+1,i:=0; end;search;/廣度搜索for i:=1 to n do/輸出 beginfor j:=1 to m dowrite(mapi,j, );writeln; end; end.搜索procedure search;begin while topws（山峰），或者wsws（山谷）。 你的任務是，對于給定的地圖，求出山峰和山谷的數(shù)量，如果所有格子都有相同的高度，那么整個地圖即是山峰，又是山谷。Input Format輸入文件grz.in

40、第一行包含一個正整數(shù)n，表示地圖的大小（1=n=1000）。接下來一個n*n的矩陣，表示地圖上每個格子的高度。(0=w=1000000000)Output Format輸出文件grz.out應包含兩個數(shù)，分別表示山峰和山谷的數(shù)量。Sample Input 1 58 8 8 7 77 7 8 8 77 7 7 7 77 8 8 7 87 8 8 8 8Sample Output 22 1Sample Input 2 55 7 8 3 15 5 7 6 66 6 6 2 85 7 2 5 87 1 0 1 7Sample Output 23 3算法選擇：廣度搜索 對于每個未訪問過的點用BFS找出高

41、度相同的連通塊，記下周邊比它大和比它小的點的個數(shù)，判斷它是山谷、山峰還是山坡（周邊上的點有小有大）。 55 7 8 3 15 5 7 6 66 6 6 2 85 7 2 5 87 1 0 1 7 如圖：對（1，1）節(jié)點，高周圍8個方向擴展，遇（1，2）高，打上高的櫝志，遇（2，2）相同入隊，遇（2，1）相同入隊，擴展（2，2）點，其周邊都高，打上高的櫝志，擴展（2，1）點，其周邊都高，打上高的櫝志，該連通塊擴展完畢，由于只有高的標志，則山谷計數(shù)器加1。 同理，尋找未訪問過點的連通塊。readln(n); for i:=1 to n do for j:=1 to n do begin read(

42、Heighti,j); if Heighti,jHeight1,1 then b:=True;/判斷所有格子是否都有相同的高度 end; if b then begin fillchar(Mark,sizeof(Mark),True); for i:=1 to n do for j:=1 to n do if Marki,j then/找到一個可未被標志的結點 begin Head:=1;/從該結點開始擴展 LineXHead:=i; LineYHead:=j; BFS; end; writeln(Peak, ,Valley); endprocedure BFS; var x,y,i,High

43、er,Lower:longint; begin Higher:=0; Lower:=0; Tail:=1; while Head0) and (x+OffsetXi0) and (y+OffsetYi=n) thenif Heightx+OffsetXi,y+OffsetYiHeightx,y then inc(Lower)/計數(shù)低于周邊點 else if Markx+OffsetXi,y+OffsetYi then/擴展相同點 begin inc(Tail);/隊尾指針加1 LineXTail:=x+OffsetXi;/入隊 LineYTail:=y+OffsetYi; end; end;

44、inc(Head);/隊頭指針加1 end; if (Higher0) and (Lower=0) then inc(Peak)/判斷山峰 else if (Higher=0) and (Lower0) then inc(Valley)/判斷山谷 end;問題4、超級馬（sup） Description 在一個無限的棋盤上有一個超級馬，它可以完成各種動作。每一種動作都是通過兩個整數(shù)來確定第一個數(shù)說明列的數(shù)（正數(shù)向右，負數(shù)向左），第二個數(shù)說明行的數(shù)（正數(shù)向上，負數(shù)向下），移動馬來完成這個動作。 編寫一個程序,從文本文件SUP.IN輸入說明各種超級馬的數(shù)據(jù)庫。 對每一個超級馬進行確認，是否通過自己

45、的行動可以到達盤面上的每一個區(qū)。 將結果存儲到文本文件SUP.OUT。Input Format 在文本文件SUP.IN 的第一行中存在一個整數(shù)k，它代表數(shù)據(jù)庫的數(shù)1k100。在這個數(shù)字后出現(xiàn)K 數(shù)據(jù)庫。它們的每一個第一行中會出現(xiàn)整數(shù)N，它是馬能夠完成的各種動作的數(shù)，1n100。接下來數(shù)據(jù)庫的每一個行中包含兩個整數(shù)P 和Q，它們由單個空格分開，說明動作，-100p,q100。Output Format 文本文件SUP.OUT 應由K 行組成，當?shù)趇 個數(shù)據(jù)庫的超級馬可以到達棋盤面的每一個區(qū)，第i 行應包含一個詞TAK，而另一個詞NIE 則恰恰相反。Sample Input 231 00 1-2

46、-153 4-3 -62 -25 6-1 4Sample OutputTAKNIE分析： 棋盤無限大，顯然讓馬走遍棋盤來進行搜索判斷是不可能的。 換一種思路，要能到達棋盤上的每一個位置，就表示超級馬可以做到只從一格移動到相鄰的位置，即位移一格。于是，問題變?yōu)榕袛嗤ㄟ^一系列的動作，超級馬能否向上下左右4個方向位移一格。 規(guī)律1：如果馬可以通過給定的幾種走法的組合，做到以下4種“基本走法”，馬就可以走遍棋盤：(1,0),(-1,0),(0,1),(0,-1)。 規(guī)律2：因為一次移動，坐標改變量不超過100，所以馬可以僅通過在-100,100的區(qū)間內(nèi)移動，得到以上的“基本走法”。 規(guī)律3：如果所有走

47、法的橫坐標的gcd（最大公約數(shù)(greatest common divisor）大于1，或縱坐標的gcd大于1，則肯定不能得到基本走法，輸出NIE 算法流程為：1.分別計算所有走法的橫、縱坐標的gcd，判斷是否大于1，若大于1，則無解；2.從（0，0）點開始在-100,100坐標內(nèi)BFS各種走法；3.判斷從（0，0）點能否走到其上下左右四個點，能走到則有解，不能走到則無解。 procedure main; var i,nowx,nowy:longint; begin linex1:=0; liney1:=0;/（0，0）點入隊 head:=1; tail:=1; while head=tail

48、 do begin for i:=1 to n do/擴展隊頭結點 begin nowx:=linexhead+xi;/求每種走法到達點 nowy:=lineyhead+yi; if con (nowx,nowy) then/是否可行 begin/可行點入隊 inc(tail); linextail:=nowx; lineytail:=nowy; fnowx,nowy:=true; end; end; inc(head);/隊頭指針加1，繼續(xù)擴展 end; end;function con (a,b:longint):boolean; begin /判斷當前點是否在坐標范圍內(nèi)的可走點 cont

49、inue:=true; if (a100) then continue:=false; if (b100) then continue:=false; if continue then if fa,b then continue:=false; end; procedure outp;/判斷從（0，0）點能否走到相鄰四個點 begin if (f0,-1) and (f0,1) and (f1,0) and (f-1,0) then writeln(TAK) else writeln(NIE);End;搜索問題訓練1、生日蛋糕（cake）（NOI題）【問題描述】 7月17日是Mr.W的生日，A

50、CM-THU為此要制作一個體積為N的M層生日蛋糕，每層都是一個圓柱體。設從下往上數(shù)第i(1=i=M)層蛋糕是半徑為Ri, 高度為Hi的圓柱。當iRi+1且HiHi+1，Ri、Hi均為整數(shù)。 由于要在蛋糕上抹奶油，為盡可能節(jié)約經(jīng)費，我們希望蛋糕外表面（最下一層的下底面除外）的面積Q最小。 令Q= S 請編程對給出的N和M，找出蛋糕的制作方案（適當?shù)腞i和Hi的值），使S最小。【輸入格式】輸入最多10組數(shù)據(jù)，每組數(shù)據(jù)包含兩個整數(shù)N和M。輸入以一個0結尾?！据敵龈袷健繉τ诿拷M數(shù)據(jù)，輸出一個整數(shù)S?！据斎霕永?00 21000 30【輸出樣例】68316【數(shù)據(jù)范圍】N100001, MANS構建I層

51、最小體積：構建I層最小側面積： 本題最強的條件是：體積限制，即要充分用好left的值，能夠讓其影響最優(yōu)性剪枝條件呢？數(shù)學變換：left= 當前蛋糕的表面積為 觀察 和 ，縮放得到不等式則 即：于是 即If s+2*left/rians then 剪枝 procedure main; var i,j,k:longint; begin read(m); ans:=maxlongint; for i:=m to n div m do /最底層高度范圍（最高層最小1，最底層最小為m） for j:=m to trunc(sqrt(n div i) do/最底層半徑范圍 begin hm:=i; rm:

52、=j; dfs(m-1,n-i*j*j,j*j+i*2*j);/參數(shù)：下一層，剩余體積，當前表面積 end; if ans=maxlongint then writeln(0) else writeln(ans); end; procedure ready; var i,j,k:longint; begin minv0:=0; mins0:=0; for i:=1 to 10 do begin minsi:=minsi-1+i*2*i;/從頂層到底層的最小表面積 minvi:=minvi-1+i*i*i;/從頂層到底層的最小體積 end; end; procedure dfs(now,left

53、,s:longint); var i,j,k:longint; begin if leftans then exit;/當前面積+前層以上最小面積大于最優(yōu)答案剪枝，最優(yōu)性剪枝 if hnow+1*rnow+1*rnow+1*now=ans then exit;/根據(jù)問題性質(zhì)剪枝 if (now=0) then/搜索結束 begin if left=0 then/剩余面積為0，求最小面積 if stotal then/填完后，保存最優(yōu)值 Begin If nowans then ans:=now; Flag:=true; End else Begin For i:=9 downto 1 do/每

54、格可填數(shù)為91 If (not can1wt,1,i)and(not can2wt,2,i)and(not can3(wt,1-1) div 3+1,(wt,2-1)div 3+1,i) then/可行性判斷 Begin Can1wt,1,i:=true;/可行填入數(shù) Can2wt,2,i:=true; Can3(wt,1-1) div 3+1,(wt,2-1)div 3+1,i:=true; Now:=now+i*pointwt,1,wt,2; Main(t+1); Now:=now-i*pointwt,1,wt,2;/回溯退出標志 Can1wt,1,i:=false; Can2wt,2,i

55、:=false; Can3(wt,1-1) div 3+1,(wt,2-1)div 3+1,i:=false; End; End; End;進一步分析： 搜索序：對于一顆搜索樹，將其中分支少的節(jié)點盡量靠近根，必然可以在不改變搜索樹深度的條件下使搜索樹變窄。 對于本題，在相同的格局下，每個未填格子可填的數(shù)字個數(shù)可以求出，每次讓當前可填數(shù)最少的點先填數(shù)，速度就會得到大幅提高。 最優(yōu)性剪枝：當發(fā)現(xiàn)剩下的格子無論填多大時都比當前結果小，就直接回溯。 procedure Init;Begin for i:=1 to 9 do for j:=1 to 9 dobegin read(Gi,j);/讀入數(shù)據(jù)先

56、作輸入數(shù)據(jù)不可行判斷 if (Gi,j0) and not (FlagXi,Gi,j and FlagYj,Gi,j and FlagG(i-1) div 3*3+(j-1) div 3+1,Gi,j) then begin writeln(-1); close(input); close(output); halt; end; FlagXi,Gi,j:=False;/同行標志標志數(shù)組初值為true FlagYj,Gi,j:=False;/同列標志 FlagG(i-1) div 3*3+(j-1) div 3+1,Gi,j:=False;/同一九宮標志 end;end;procedure Ma

57、in;begin Ans:=-1;x:=0; Min:=Maxlongint;v:=0; for i:=1 to 9 dofor j:=1 to 9 doif Gi,j=0 thenbegininc(v,Pointi,j);/v為未填入點的耙分和inc(Total);/求搜索點個數(shù)s:=0;for k:=1 to 9 do / 求可填數(shù)字個數(shù)if FlagXi,k and FlagYj,k and FlagG(i-1) div 3*3+(j-1) div 3+1,k then inc(s); if sMin then /找填數(shù)個數(shù)最少的點beginMin:=s;a:=i;b:=j;end;en

58、delse inc(x,Gi,j*Pointi,j);/求已填上數(shù)點的分值和DFS(1,a,b,x,v);/從填數(shù)個數(shù)最少的點開始搜索end;procedure DFS(const t,x,y,k,v:longint);vari,i1,j1,k1,a,b,s,Min:longint;beginfor i:=9 downto 1 do /搜索可填的數(shù)if FlagXx,i and FlagYy,i and FlagG(x-1) div 3*3+(y-1) div 3+1,i thenbeginif k+i*Pointx,y+v*9Ans then continue;/最優(yōu)性剪枝，無論填什么都不大

59、Gx,y:=i;/填入該點FlagXx,i:=False;FlagYy,i:=False;FlagG(x-1) div 3*3+(y-1) div 3+1,i:=False;if tTotal then/未搜索完beginMin:=Maxlongint;/繼續(xù)找填入個數(shù)最少點進行搜索for i1:=1 to 9 do for j1:=1 to 9 do if Gi1,j1=0 thenbegin s:=0; for k1:=1 to 9 do if FlagXi1,k1 and FlagYj1,k1 and FlagG(i1-1) div 3*3+(j1-1) div 3+1,k1 then

60、inc(s); if sAns then Ans:=k+i*Pointx,y;Gx,y:=0;/回溯FlagXx,i:=True;FlagYy,i:=True;FlagG(x-1) div 3*3+(y-1) div 3+1,i:=True;end;end;3、海盜船（corsair）【問題描述】 有一個很有趣的游戲叫做海盜船。這是一個在9*8的棋盤上進行的游戲，棋盤上的每個格子可能是下面4種狀態(tài)之一： “.”：表示當前格子為空； “S”：表示你的船所在的位置； “E”：表示敵船所在的位置； “#”：表示一座小島。 每次你可以將你的船朝周圍的8個方向之一移動，但不能停留。在你移動完之后，所有的