枚舉與搜索PPT學習教案

1、會計學1枚舉與搜索枚舉與搜索第1頁/共65頁注意：注意：1. 加號與等號各自需要兩根火柴棍加號與等號各自需要兩根火柴棍2. 如果如果AB，則，則A+B=C與與B+A=C視為不同的等式（視為不同的等式（A、B、C=0）3. n根火柴棍必須全部用上根火柴棍必須全部用上第2頁/共65頁第3頁/共65頁第4頁/共65頁第5頁/共65頁第6頁/共65頁第7頁/共65頁第8頁/共65頁第9頁/共65頁現(xiàn)有一個棱長為現(xiàn)有一個棱長為n的立方體，可以分成的立方體，可以分成n3個個1*1*1的的單位立方體。每個單位立方體都有一個整數(shù)值。單位立方體。每個單位立方體都有一個整數(shù)值。n3個單位立方體的數(shù)和不會超過個單位

2、立方體的數(shù)和不會超過longint范圍?，F(xiàn)在要范圍。現(xiàn)在要求在這個立方體找到一個包含完整單位立方體的長求在這個立方體找到一個包含完整單位立方體的長方體，使得該長方體內(nèi)所有單位立方體的數(shù)和最大。方體，使得該長方體內(nèi)所有單位立方體的數(shù)和最大。輸入：輸入： n(1n20)；n個個n*n的數(shù)字矩陣，每個數(shù)的數(shù)字矩陣，每個數(shù)字矩陣代表一層，每個數(shù)字代表一個單位立方體的字矩陣代表一層，每個數(shù)字代表一個單位立方體的整數(shù)值，整數(shù)值，-999單位立方體的整數(shù)值單位立方體的整數(shù)值999999輸出：輸出：長方體的數(shù)和長方體的數(shù)和第10頁/共65頁第11頁/共65頁第12頁/共65頁3 3、提取恰當?shù)男畔?、提取恰當?shù)?/p>

3、信息上述考察實際上求出上述考察實際上求出z z軸坐標為軸坐標為z z2 2的平面中矩形（的平面中矩形（x1，y1，x2，y2）的數(shù)和。我們將這個數(shù)和記為）的數(shù)和。我們將這個數(shù)和記為value(a) value(a) value(A)=value(ABCD)+value(B)-value(BC)- value(A)=value(ABCD)+value(B)-value(BC)-value(BD)value(BD)這就啟發(fā)我們用另一種方法表示立方體的信息：設這就啟發(fā)我們用另一種方法表示立方體的信息：設recxrecx，y y，zz表示表示z z軸坐標為軸坐標為z z的水平面中矩形（的水平面中矩形（

4、1 1，1，x，y）的數(shù)和。）的數(shù)和。 z z軸坐標為軸坐標為z z的水平面中的水平面中左上角為（左上角為（x1，y1）、右下）、右下角為（角為（x2，y2）的矩陣的數(shù)和為）的矩陣的數(shù)和為recxrecx2 2，y y2 2，z+ z+ recxrecx1 1，y y1 1，z-recxz-recx2 2，y y1 1，z-recxz-recx1 1，y y2 2，zz 第13頁/共65頁RecRec數(shù)組可以在輸入數(shù)據(jù)的同時計算數(shù)組可以在輸入數(shù)據(jù)的同時計算fillchar(recfillchar(rec，size(rec)size(rec)，0)0)；recrec數(shù)組初始化數(shù)組初始化 forf

5、or z1 to n do 逐層輸入信息逐層輸入信息 forfor x1 to n do 逐行輸入逐行輸入z平面的信息平面的信息forfor y1 to n do 逐列輸入逐列輸入z平面上平面上x行的信息行的信息beginbegin read(mapx read(mapx，y y，z)z)； 輸入輸入z z平面上（平面上（x,yx,y）中的數(shù)）中的數(shù) if (x=1)and(y=1) if (x=1)and(y=1) 計算計算z z平面上以（平面上以（1 1，1 1）為左上角、（）為左上角、（x,yx,y）為右下角的矩形的數(shù)和）為右下角的矩形的數(shù)和 then rec1 then rec1，1

6、1，zzmap1map1，1 1，zz else if y=1 then recx else if y=1 then recx，y y，zzrecx-1recx-1，n n，z+mapxz+mapx，y y，zz else recx else recx，y y，zrecxzrecx，y-1y-1，z+mapxz+mapx，y y，zz； endend；forfor 這樣，考察過程就可以改為這樣，考察過程就可以改為 sumsum+recxsumsum+recx2 2，y y2 2，z z2 2+recx+recx1 1，y y1 1，z z2 2-recx-recx2 2，y y1 1，z z2

7、 2-recx-recx1 1，y y2 2，z z2 2 ； if sumbest then bestif sumbest then bestsumsum；時間復雜度降為時間復雜度降為O O（n n6 6）。）。第14頁/共65頁如果長方體如果長方體a的數(shù)和是負數(shù)，則長方體的數(shù)和是負數(shù)，則長方體a的計算的計算結果廢棄，考察長方體結果廢棄，考察長方體b-a。因為長方體。因為長方體b的數(shù)的數(shù)和和=長方體長方體b-a的數(shù)和的數(shù)和+長方體長方體a的數(shù)和，由于長的數(shù)和，由于長方體方體a的數(shù)和為負，長方體的數(shù)和為負，長方體b-a的數(shù)和一定大于的數(shù)和一定大于等于長方體等于長方體b的數(shù)和。由此可見，在累計長

8、方體的數(shù)和。由此可見，在累計長方體數(shù)和的時候，只要由上而下地枚舉長方體下底數(shù)和的時候，只要由上而下地枚舉長方體下底面的面的z軸坐標即可。設軸坐標即可。設total(z)以以z軸坐標為軸坐標為z的平面為下底面的長的平面為下底面的長方體的最大數(shù)和方體的最大數(shù)和0, 1, 1, 1, 1,)1(, 0max(00)(21121122zzyxreczyxreczyxreczyxrecztotalzztotal第15頁/共65頁第16頁/共65頁第17頁/共65頁第18頁/共65頁第19頁/共65頁第20頁/共65頁第21頁/共65頁第22頁/共65頁第23頁/共65頁Procedure Try( i:

9、 integer)；var j:integer;begin if i=n+1 then print； for j:=1 to n do if aj and bi+j and ci-j then begin ai:=j; aj:=false; bi+j:=false; ci-j:=false; Try (i+1) aj:=true; bi+j:= true; ci-j:= true; end;end;第24頁/共65頁搜索的方向第25頁/共65頁第26頁/共65頁第27頁/共65頁第28頁/共65頁第29頁/共65頁第30頁/共65頁第31頁/共65頁第32頁/共65頁第33頁/共65頁第34頁

10、/共65頁2 2、粗略利用信息、粗略利用信息 若已經(jīng)確定了前若已經(jīng)確定了前k k個數(shù)，并且下一個關系符號是小于號，這時所個數(shù)，并且下一個關系符號是小于號，這時所能產(chǎn)生的序關系數(shù)就是剩下的能產(chǎn)生的序關系數(shù)就是剩下的n-kn-k個數(shù)所能產(chǎn)生的序關系數(shù)。個數(shù)所能產(chǎn)生的序關系數(shù)。設設i i個數(shù)共有個數(shù)共有FiFi種不同的序關系，那么，由上面的討論可知，在種不同的序關系，那么，由上面的討論可知，在算法算法1 1中，調(diào)用一次中，調(diào)用一次Count(Step+1Count(Step+1，1 1，Can-i)Can-i)之后，之后，TotalTotal的增的增量應該是量應該是Fn-StepFn-Step。這個

11、值可以在第一次調(diào)用。這個值可以在第一次調(diào)用Count(Step+1Count(Step+1，1 1，Can-i)Can-i)時求出。而一旦知道了時求出。而一旦知道了Fn-StepFn-Step的值，就可以用的值，就可以用TotalTotalTotal+Fn-Step Total+Fn-Step 代替調(diào)用代替調(diào)用Count(Step+1Count(Step+1，1 1，Can-i)Can-i) 第35頁/共65頁procedure Count(Stepprocedure Count(Step，F(xiàn)irstFirst，Can)Can)； StepStep，F(xiàn)irstFirst，CanCan的含義同算

12、法的含義同算法11 begin begin if Step=n then begin 若確定了最后一個關系符號，若確定了最后一個關系符號，則輸出統(tǒng)計結果則輸出統(tǒng)計結果 for i for iFirst to n do if i in Can then Inc(Total)First to n do if i in Can then Inc(Total)；Exit Exit 回溯回溯 end end；thenthen for iFirst to n do for iFirst to n do 枚舉當前的大寫字母枚舉當前的大寫字母 if i in Can if i in Can 序號為序號為i i

13、的大寫字母可以使用的大寫字母可以使用 then beginthen begin Count(Step+1 Count(Step+1，i+1i+1，Can-i)Can-i)； 添等于號添等于號 if Fn-Step=-1 if Fn-Step=-1 then begin then begin 第一次調(diào)用第一次調(diào)用 Fn-Step Fn-Step TotalTotal；Count(Step+1Count(Step+1，1 1，Can-i)Can-i)； 添小于號添小于號 Fn-Step Fn-Step Total-Fn-Step Fn-Step=TotalTotal-Fn-Step Fn-Step

14、=Total的增量的增量 end thenend thenelse TotalTotal+Fn-Step Fn-Step已經(jīng)求出已經(jīng)求出 endthen end；count該算法實質(zhì)上就是自頂向下記憶化方式的搜索，它的時間復雜度為該算法實質(zhì)上就是自頂向下記憶化方式的搜索，它的時間復雜度為W(2W(2n n) )。 第36頁/共65頁3 3、充分利用信息、充分利用信息在搜索的過程中，如果確定在第在搜索的過程中，如果確定在第k個大寫字母之后添加第一個小于號，則個大寫字母之后添加第一個小于號，則可得到下面兩條信息：可得到下面兩條信息：第一條信息：前第一條信息：前k個大寫字母都是用等號連接的。前半部分

15、將產(chǎn)生的序關個大寫字母都是用等號連接的。前半部分將產(chǎn)生的序關系數(shù)，就是系數(shù)，就是n個物體中取個物體中取k個的組合數(shù)個的組合數(shù)第二條信息：在此基礎上繼續(xù)搜索，將產(chǎn)生第二條信息：在此基礎上繼續(xù)搜索，將產(chǎn)生Fn-k個序關系表達式。個序關系表達式。這樣，我們可以得到這樣，我們可以得到Fn 的遞推關系式：的遞推關系式：采用上述公式計算采用上述公式計算Fn的算法記為算法的算法記為算法3，它的時間復雜度是，它的時間復雜度是W(n2)。knC101FknFCnFnkkn，其中第37頁/共65頁varvar Total Total ：CompComp； 答案答案 F F ：array0.maxn of Comp

16、array0.maxn of Comp；FiFi為為i i個數(shù)的序關系表達式個數(shù)個數(shù)的序關系表達式個數(shù) i i，j j ：IntegerInteger； x x ：CompComp； beginbegin FillChar(F FillChar(F，Sizeof(F)Sizeof(F)，0)0)；FF初始化初始化 F0 1 F0 1； for i1 to n do beginfor i1 to n do begin遞推遞推F F數(shù)組數(shù)組 Fi 0 Fi 0；x1x1； for j1 to i do begin for j1 to i do begin 計算計算FiFi xx xx* *(i-j

17、+1)/j(i-j+1)/j；Fi Fi+xFi Fi+x* *Fi-jFi-j Endfor Endfor end end；forfor writeln(Fn) writeln(Fn)； 輸出結果輸出結果 end end；mainmain第38頁/共65頁第39頁/共65頁一個反例第40頁/共65頁第41頁/共65頁第42頁/共65頁第43頁/共65頁第44頁/共65頁DXCBCNXXBACNXXDDCNXAC332211* BADC+ CBDA DCCC 枚舉每位是否進位，復雜度是枚舉每位是否進位，復雜度是O(2n), (因為首位不可能進位因為首位不可能進位，無須枚舉，無須枚舉)。然后，用

18、高斯消元法來解方程，復雜度是。然后，用高斯消元法來解方程，復雜度是O(n3) ?？倧碗s度是?？倧碗s度是O(2n*n3) 。第45頁/共65頁第46頁/共65頁第47頁/共65頁第48頁/共65頁第49頁/共65頁第50頁/共65頁第51頁/共65頁第52頁/共65頁第53頁/共65頁第54頁/共65頁第55頁/共65頁第56頁/共65頁Amazing Robots: IOI2003已知條件： 迷宮 i（i=1,2） （每個不會大于20*20） 守衛(wèi) Gi（0=Gi=10） （守衛(wèi)循環(huán)移動進行執(zhí)勤） （守衛(wèi)巡邏的方格數(shù)（2.4）求： 兩個機器人都離開迷宮所用的最少指令數(shù)目 和離開制指令序列（10000 步以內(nèi)）。第57頁/共65頁每一步可以發(fā)出的命令可以是N, E, S, W中的一種，有4種選擇。對每一步具體發(fā)出哪個命令，直接搜索。假設最后結果是T。（也就是最少出宮時間）時間復雜度是O(4T)這種方法時間復雜度太高，絕對不可行!第58頁/共65頁5*4和4*4的迷宮第一個機器人的位置是(2,2)第二個機器人的位置是(3,2)當前時間是0。狀態(tài)(2,2),(3,2),0)狀態(tài)表示：狀態(tài)表示： （第一個機器人