遞歸與搜索算法

1、遞歸思想和搜索算法數(shù)模組 費鵬1遞歸思想和搜索算法遞歸遞歸的定義遞歸的特點深度優(yōu)先搜索深度搜索定義深搜過程廣度優(yōu)先搜索遞歸定義在調(diào)用一個函數(shù)的過程中又出現(xiàn)直接或間接地調(diào)用該函數(shù)本身，成為函數(shù)的遞歸調(diào)用。例如：int fun(int n)int t;if(n = 1)t = 1;elset = n * fun(n - 1);return t;遞歸2考慮一下剛才那個函數(shù)的運行過程以起始n為5為例有fun(5)調(diào)用fun(4),fun(4)調(diào)用fun(3),直到n = 1為止然后依次向上一層返回值。n=5t=5*fun(4) n=4t=4*fun(3) n=3t=3*fun(2) n=2t=2*fu

2、n(1) n=1t=1 考慮若在return語句前加入printf(“%d”, t)，會有怎么的輸出結(jié)果輸出1輸出2輸出6輸出24輸出1203為什么能用遞歸解決這個問題？階乘問題可以分解為規(guī)模更小的子問題，用同樣的方法可以解子問題可以很容易的得到關(guān)于階乘問題的遞歸公式： 1, n = 0, 1 n! = n * (n - 1)!, n 1考慮一個新問題：現(xiàn)在有n個蘋果和m個盤子，把這些蘋果都放到盤子里，可以有盤子里一個蘋果也不放，有多少種擺放方法。4關(guān)注最后一個條件，即可能存在也可能不存在沒放蘋果的盤子。結(jié)果可為以下兩種情況的和有空盤子的情況，則問題可簡化為n個蘋果放m 1個盤子。沒有空盤子的

3、情況，則問題可簡化為n m個蘋果放m個盤子可以得到遞歸公式，total總數(shù) 1, n = 0 or m = 1total(n, m) total(n, n), n = 8)/搜索到第8層以上時得到一個解for(i = 0;i 8;i +)printf(%d, mapi);printf(n);for(i = 1;i = 8;i +)/對每一個可行子節(jié)點進行深搜for(j = 0;j = l)mapl = i;/記錄棋子的位置DFS(l + 1);mapl = 0;/返回上一層時要清空這層的信息Visited哪去了？24考慮一個新問題：在n*m的棋盤上有一只馬，它能像圖示那樣走現(xiàn)在它想遍歷每一個棋

4、格，它該怎么做？25Bool DFS(int i , int j)step+;routestep=(i,j)/positionvisitedij=true;if(step=n*m)return true;for(int n=1;n=1&x=A&y=n+A-1)if(DFS(x,y)return true;mapij=false;step-;return false;26廣度優(yōu)先搜索遞歸遞歸的定義遞歸的特點深度優(yōu)先搜索深度搜索定義深搜過程廣度優(yōu)先搜索在深度優(yōu)先搜索算法中，是深度越大的結(jié)點越先得到擴展。如果在搜索中把算法改為按結(jié)點的層次進行搜索， 本層的結(jié)點沒有搜索處理完時，不能對下層結(jié)點進行處理

5、，即深度越小的結(jié)點越先得到擴展。也就是說先產(chǎn)生的結(jié)點先得以擴展處理，這種搜索算法稱為廣度優(yōu)先搜索法。27偽代碼Void BFS (int V)/A breadth first search of G is carried out beginning /at vertex v. For any node i , visitedi=1 if i has already been visited. The /graph G and array visited are global; visited is initialized to u=v; Queue q(size)/ q is

6、 a queue of unexplored vertices. visitedv=1;doFor all vertices w adjacent from uIf(visitedw=0)q . add(w);/ w is unexplored.Visitedw=1; If(q.qempty() return;/ No unexplored vertex. while(1);28下面是一棵搜索樹1235467891029圖的廣度優(yōu)先算法在廣度優(yōu)先算法中，我們從定點v開始，標(biāo)記它為已經(jīng)到達（已訪問）。這時，頂點v稱為未考察的點。當(dāng)已經(jīng)訪問過某個頂點的所有相鄰定點后，在算法中這個頂點稱為已經(jīng)考察的

7、頂點。接著訪問v的所有相鄰的未訪問的頂點，這些是新的未考察的頂點，頂點v現(xiàn)在成為已考察的頂點。最新訪問的頂點還未考察，放置在隊列的尾部，隊列的首結(jié)點就是下一個要考察的點。當(dāng)不存在為考察的點時，考察停止。30對圖的廣度優(yōu)先遍歷ADBCFEGHI31上圖的搜索樹ABCEDHFIG32如何實現(xiàn)廣度優(yōu)先搜索？一種數(shù)據(jù)結(jié)構(gòu)可以幫助實現(xiàn)-隊列隊列可以簡化為一種退化了的數(shù)組僅支持總頭部提取元素和從尾部添加元素類比生活中的隊伍先到的人排在隊首，先接受服務(wù)，后到的人排在隊尾，最后接受服務(wù)。33再來一次123546789102345678910134偽代碼Void BFS (int V)/A breadth fi

8、rst search of G is carried out beginning /at vertex v. For any node i , visitedi=1 if i has already been visited. The /graph G and array visited are global; visited is initialized to u=v; Queue q(size)/ q is a queue of unexplored vertices. visitedv=1;doFor all vertices w adjacent from uIf(v

9、isitedw=0)q . add(w);/ w is unexplored.Visitedw=1; If(q.qempty() return;/ No unexplored vertex. while(1);35一個問題：有兩個數(shù)n和m，n總比m小，n每次可以進行自乘2，或者自加1，或者自減1，至少多少次操作后n可以變?yōu)閙比如n = 5， m = 9，兩步即可n = n * 2,n = n 1,n = 9 = m36類似求最短路徑問題依舊是樹狀結(jié)構(gòu)每走一步相當(dāng)于一層，每步有三種走法，相當(dāng)于3個節(jié)點由于深度未知，同時要求最短路徑，所以適合用廣度搜索新產(chǎn)生的節(jié)點進隊列，待擴展的節(jié)點從隊列中取出，

10、走過的節(jié)點不需要重復(fù)遍歷，走到目標(biāo)點m時，搜索結(jié)束37struct Pint x;int d;/結(jié)構(gòu)體P存儲節(jié)點的值和深度int visited100010;/判斷節(jié)點是否遍歷過的數(shù)組struct P queue100010;int BFS(int N, int K)int rear = 0, font = 0, L, d;/rear指向尾，font指向頭queuerear.x = N;queuerear.d = 0;rear +;while(1)L = queuefont.x;/從隊列中獲得節(jié)點d = queuefont.d;頭指針向后移一位是否滿足條件？visitedL = 1;38if(L * 2 = 0 & mapL * 2 != 1)/ 該點進入隊列/visited數(shù)組L;/ /尾指針向后移動/產(chǎn)生自乘2的節(jié)點，入隊if(L + 1 = 0 & mapL + 1 != 1)產(chǎn)生自加1的節(jié)點，入隊if(L - 1 = 0 & mapL - 1 != 1)產(chǎn)生自減1的節(jié)點，入隊39考慮一個新問題：八數(shù)碼問題描述：把下圖的狀態(tài)57381246變成這樣12348765每次只能交換空白格和與它相鄰的格子最少多少步可以完成轉(zhuǎn)換40深搜與廣搜的比較搜索方