遞歸與回溯法PPT學習教案

1、會計學1遞歸與回溯法遞歸與回溯法第1頁/共34頁第2頁/共34頁遞歸算法遞歸算法在可計算性理論中占有重要地位，它在可計算性理論中占有重要地位，它是算法設計的有力工具，對于拓展編程思路非常有是算法設計的有力工具，對于拓展編程思路非常有用。就遞歸算法而言并不涉及高深數(shù)學知識，只不用。就遞歸算法而言并不涉及高深數(shù)學知識，只不過初學者要建立起遞歸概念不十分容易。過初學者要建立起遞歸概念不十分容易。我們先從一個最簡單的例子導入。我們先從一個最簡單的例子導入。遞歸及其實現(xiàn)遞歸及其實現(xiàn)用遞歸算法求用遞歸算法求 n!定義：函數(shù)定義：函數(shù) fact( n ) = n!fact( n-1 ) = ( n-1 )!

2、則有則有fact( n ) = n fact( n-1 )已知已知fact( 1 ) = 1第3頁/共34頁第4頁/共34頁第5頁/共34頁第6頁/共34頁第7頁/共34頁這相當于從菜心這相當于從菜心“推到推到”外層。外層。 遞歸遞歸算法的算法的出發(fā)點不放在初始條件上，放在求解的目標上，出發(fā)點不放在初始條件上，放在求解的目標上，從所求的未知項出發(fā)逐次調用本身的求解過程，從所求的未知項出發(fā)逐次調用本身的求解過程，直到遞歸的邊界（即初始條件）。就本例而言，直到遞歸的邊界（即初始條件）。就本例而言，讀者會認為遞歸算法可能是多余的，費力而不討讀者會認為遞歸算法可能是多余的，費力而不討好。好。但許多實際

3、問題不可能或不容易找到顯而易但許多實際問題不可能或不容易找到顯而易見的遞推關系，這時遞歸算法就表現(xiàn)出了明顯的見的遞推關系，這時遞歸算法就表現(xiàn)出了明顯的優(yōu)越性。優(yōu)越性。下面我們將會看到，遞歸算法比較符合下面我們將會看到，遞歸算法比較符合人的思維方式，邏輯性強，可將問題描述得簡單人的思維方式，邏輯性強，可將問題描述得簡單扼要，具有良好的可讀性，易于理解扼要，具有良好的可讀性，易于理解. 許多看來許多看來相當復雜，或難以下手的問題，如果能夠使用遞相當復雜，或難以下手的問題，如果能夠使用遞歸算法就會使問題變得易于處理。歸算法就會使問題變得易于處理。第8頁/共34頁第9頁/共34頁第10頁/共34頁回溯

4、法也是搜索算法中的一種控制策略，但與枚舉法不同的是，它是從初始狀態(tài)出發(fā)，運用題目給出的條件、規(guī)則，按照深度優(yōu)秀搜索的順序擴展所有可能情況，從中找出滿足題意要求的解答。回溯法是求解特殊型計數(shù)題或較復雜的枚舉題中使用頻率最高的一種算法?；厮莘ㄒ彩撬阉魉惴ㄖ械囊环N控制策略，但與枚舉法不同的是，它是從初始狀態(tài)出發(fā)，運用題目給出的條件、規(guī)則，按照深度優(yōu)秀搜索的順序擴展所有可能情況，從中找出滿足題意要求的解答?；厮莘ㄊ乔蠼馓厥庑陀嫈?shù)題或較復雜的枚舉題中使用頻率最高的一種算法。 procedure run（當前狀態(tài)）； var i：integer；begin if 當前狀態(tài)為邊界 then begin if

5、 當前狀態(tài)為最佳目標狀態(tài) then 記下最優(yōu)結果； exit；回溯 end； for i算符最小值 to 算符最大值 do begin 算符i作用于當前狀態(tài)，擴展出一個子狀態(tài)； if (子狀態(tài)滿足約束條件)and(子狀態(tài)滿足最優(yōu)性要求)then run(子狀態(tài)) end；end；第11頁/共34頁在應用回溯法求所有路徑的算法框架解題時，應考慮如下幾個重要因素：在應用回溯法求所有路徑的算法框架解題時，應考慮如下幾個重要因素：定義狀態(tài)：定義狀態(tài)：即如何描述問題求解過程中每一步的狀況。為了精簡程序，即如何描述問題求解過程中每一步的狀況。為了精簡程序，增加可讀性，我們一般將參與子結點擴展運算的變量組合

6、成當前狀態(tài)列入增加可讀性，我們一般將參與子結點擴展運算的變量組合成當前狀態(tài)列入值參，以便回溯時能恢復遞歸前的狀態(tài)，重新計算下一條路徑；值參，以便回溯時能恢復遞歸前的狀態(tài)，重新計算下一條路徑；邊界條件：邊界條件：即在什么情況下程序不再遞歸下去。如果是求滿足某個特定即在什么情況下程序不再遞歸下去。如果是求滿足某個特定條件的一條最佳路徑，則當前狀態(tài)到達邊界時并非一定意味著此時就是最條件的一條最佳路徑，則當前狀態(tài)到達邊界時并非一定意味著此時就是最佳目標狀態(tài)。因此還須增加判別最優(yōu)目標狀態(tài)的條件；佳目標狀態(tài)。因此還須增加判別最優(yōu)目標狀態(tài)的條件；搜索范圍：搜索范圍：在當前狀態(tài)不滿足邊界條件的情況下，應如何設

7、計算符值的在當前狀態(tài)不滿足邊界條件的情況下，應如何設計算符值的范圍。換句話說，如何設定范圍。換句話說，如何設定for語句中循環(huán)變量的初值和終值。語句中循環(huán)變量的初值和終值。約束條件和最優(yōu)性要求：約束條件和最優(yōu)性要求：當前擴展出一個子結點后應滿足什么條件方可當前擴展出一個子結點后應滿足什么條件方可繼續(xù)遞歸下去；如果是求滿足某個特定條件的一條最佳路徑，那么在擴展繼續(xù)遞歸下去；如果是求滿足某個特定條件的一條最佳路徑，那么在擴展出某個子狀態(tài)后是否繼續(xù)遞歸搜索下去，不僅取決于子狀態(tài)是否滿足約束出某個子狀態(tài)后是否繼續(xù)遞歸搜索下去，不僅取決于子狀態(tài)是否滿足約束條件，而且還取決于子狀態(tài)是否滿足最優(yōu)性要求。條件

8、，而且還取決于子狀態(tài)是否滿足最優(yōu)性要求。參與遞歸運算的參數(shù)：參與遞歸運算的參數(shù)：將參與遞歸運算的參數(shù)設為遞歸子程序的值參或將參與遞歸運算的參數(shù)設為遞歸子程序的值參或局部變量。若這些參數(shù)的存儲量大（例如數(shù)組）且初始值需由主程序傳入，局部變量。若這些參數(shù)的存儲量大（例如數(shù)組）且初始值需由主程序傳入，為避免內存溢出，則必須將其設為全局變量，且回溯前需恢復其遞歸前的為避免內存溢出，則必須將其設為全局變量，且回溯前需恢復其遞歸前的值。值。 第12頁/共34頁 八皇后的兩組解八皇后的兩組解第13頁/共34頁第14頁/共34頁第15頁/共34頁第16頁/共34頁第17頁/共34頁第18頁/共34頁第19頁/共34頁搜索的方向