程序設計基礎11_2_遞歸

1、第第1111章章 遞推與遞歸遞推與遞歸第第11章章 遞推與遞歸遞推與遞歸開開 始始1第第1111章章 遞推與遞歸遞推與遞歸主要內(nèi)容主要內(nèi)容遞推遞推遞歸遞歸遞歸與分治遞歸與分治遞歸與回溯遞歸與回溯2第第1111章章 遞推與遞歸遞推與遞歸遞歸的概念遞歸的概念 先看大家都熟悉的一個民間故事：從前有座山，山上先看大家都熟悉的一個民間故事：從前有座山，山上有座廟，廟里有一個老和尚在給小和尚講故事，故事有座廟，廟里有一個老和尚在給小和尚講故事，故事里說，從前有座山，山上有座廟，廟里有一個老和尚里說，從前有座山，山上有座廟，廟里有一個老和尚在給小和尚講故事，故事里說在給小和尚講故事，故事里說。象這樣，一個對

2、。象這樣，一個對象部分地由它自己組成，或者是按它自己定義，我們象部分地由它自己組成，或者是按它自己定義，我們稱之為遞歸。稱之為遞歸。 遞歸的定義：遞歸的定義：在一個函數(shù)的定義中又直接或間接地調(diào)用該函數(shù)本身在一個函數(shù)的定義中又直接或間接地調(diào)用該函數(shù)本身，稱為遞歸。遞歸是一種非常有用的程序設計方法。，稱為遞歸。遞歸是一種非常有用的程序設計方法。3第第1111章章 遞推與遞歸遞推與遞歸遞歸算法的基本思想遞歸算法的基本思想 把規(guī)模大的、較難解決的問題變成規(guī)模較小把規(guī)模大的、較難解決的問題變成規(guī)模較小的、易解決的同一問題。規(guī)模較小的問題又變的、易解決的同一問題。規(guī)模較小的問題又變成規(guī)模更小的問題，并且小

3、到一定程度可以直成規(guī)模更小的問題，并且小到一定程度可以直接得出它的解，從而得到原來問題的解。接得出它的解，從而得到原來問題的解。遞歸算法的特點遞歸算法的特點 用遞歸算法編寫的程序結構清晰，具有很好用遞歸算法編寫的程序結構清晰，具有很好的可讀性；但程序的效率比較低。的可讀性；但程序的效率比較低。4第第1111章章 遞推與遞歸遞推與遞歸遞歸的應用場合遞歸的應用場合當問題具備以下特點之一時，往往采用遞歸算當問題具備以下特點之一時，往往采用遞歸算法來解決：法來解決： 問題本身是遞歸定義的，如問題本身是遞歸定義的，如FibonacciFibonacci數(shù)數(shù)列問題列問題 ； 問題涉及到的數(shù)據(jù)結構是遞歸定義

4、的，如問題涉及到的數(shù)據(jù)結構是遞歸定義的，如樹樹、圖等、圖等 ； 問題的解決方法是遞歸形式的，如問題的解決方法是遞歸形式的，如漢諾塔問漢諾塔問題題 ；5第第1111章章 遞推與遞歸遞推與遞歸例例 輸出Fibonacii數(shù)列的第n項#include int fib(int n)if (n=1) return 1; else return fib(n-1)+fib(n-2); void main( )int n;scanf(%d,&n);printf(%dn ,fib( n ) );6第第1111章章 遞推與遞歸遞推與遞歸 上面是斐波那契數(shù)列的遞歸調(diào)用樹，可以看出同一個fib(i)被調(diào)用多次

5、，因此遞歸算法編寫的程序效率比較低。Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)7第第1111章章 遞推與遞歸遞推與遞歸遞歸設計的要件遞歸設計的要件 (1) (1) 在函數(shù)中必須在函數(shù)中必須有直接或間接調(diào)用自身有直接或間接調(diào)用自身的語的語句；句； (2) (2) 在使用遞歸策略時，必須在使用遞歸策略時，必須有一個明確的遞有一個明確的遞歸結束條件歸結束條件，稱為遞歸出口（或遞歸邊界）。，稱為遞歸出口（或遞歸邊界）。8第第1111章章 遞推與遞歸遞推與遞歸編寫遞歸

6、算法時，首先要對問題的以下三個方面編寫遞歸算法時，首先要對問題的以下三個方面進行分析：進行分析： u決定問題規(guī)模的參數(shù)。決定問題規(guī)模的參數(shù)。 需要用遞歸算法解決的問題，其規(guī)模通常都是比較需要用遞歸算法解決的問題，其規(guī)模通常都是比較大的，在問題中決定規(guī)模大小（或問題復雜程度）的量大的，在問題中決定規(guī)模大小（或問題復雜程度）的量有哪些？把它們找出來。有哪些？把它們找出來。 u問題的邊界條件及邊界值。問題的邊界條件及邊界值。 在什么情況下可以直接得出問題的解？這就是問題在什么情況下可以直接得出問題的解？這就是問題的邊界條件及邊界值。的邊界條件及邊界值。 u解決問題的通式解決問題的通式。 把規(guī)模大的、

7、較難解決的問題變成規(guī)模較小、易解把規(guī)模大的、較難解決的問題變成規(guī)模較小、易解決的同一問題，需要通過哪些步驟或等式來實現(xiàn)？這是決的同一問題，需要通過哪些步驟或等式來實現(xiàn)？這是解決遞歸問題的難點。把這些步驟或等式確定下來。解決遞歸問題的難點。把這些步驟或等式確定下來。 9第第1111章章 遞推與遞歸遞推與遞歸遞歸設計實例遞歸設計實例 例例10.5 10.5 漢諾（漢諾（HanoiHanoi）塔問題）塔問題 （1 1）相傳在古代印度的一個寺廟中，有位僧人整天把）相傳在古代印度的一個寺廟中，有位僧人整天把三根柱子上的金盤倒來倒去，原來他是想把三根柱子上的金盤倒來倒去，原來他是想把6464只一個只一個比

8、一個小的盤子從柱子比一個小的盤子從柱子A A上借助柱子上借助柱子B B移到柱子移到柱子C C上去上去。 （2 2）移動過程恪守下述規(guī)則：每次只允許移動一只盤）移動過程恪守下述規(guī)則：每次只允許移動一只盤子，且大盤子不得落在小盤子上面。子，且大盤子不得落在小盤子上面。 （3 3）有人覺得這很簡單，但真的動手才發(fā)現(xiàn)，如以每）有人覺得這很簡單，但真的動手才發(fā)現(xiàn)，如以每秒移動一只盤子，按照上述規(guī)則將秒移動一只盤子，按照上述規(guī)則將6464只盤子從柱子只盤子從柱子A A移到柱子移到柱子C C上，所需時間也是很多年。上，所需時間也是很多年。10第第1111章章 遞推與遞歸遞推與遞歸11第第1111章章 遞推與

9、遞歸遞推與遞歸 漢諾塔的目標是將初始位置的漢諾塔的目標是將初始位置的n n個盤子從初始位置個盤子從初始位置A A借借助于中間位置助于中間位置B B移動到目標位置移動到目標位置C C，可以按照以下三個，可以按照以下三個步驟來執(zhí)行：步驟來執(zhí)行： 第一步：將初始位置第一步：將初始位置A A上面的上面的n-1n-1個盤子借助目標位置個盤子借助目標位置C C，移動到中間位置，移動到中間位置B B暫時存放；暫時存放； 第二步：將初始位置第二步：將初始位置A A最下面的大盤子直接移動到目標最下面的大盤子直接移動到目標位置位置C C； 第三步：將中間位置第三步：將中間位置B B暫存的暫存的n-1n-1個盤子借

10、助初始位置個盤子借助初始位置A A移動到目標位置移動到目標位置C C12第第1111章章 遞推與遞歸遞推與遞歸HanoiHanoi塔問題塔問題#include #include int step=1;int step=1; / / 整型全局變量整型全局變量, , 預置預置1, 1, 步數(shù)步數(shù)void move(int,char,char,char);void move(int,char,char,char);void main()void main() int n; int n; printf( printf(請輸入盤數(shù)請輸入盤數(shù) n=);n=); scanf(%d,&n); scan

11、f(%d,&n); printf( printf(在在3 3根柱子上移根柱子上移%d%d只盤的步驟為只盤的步驟為:n,n);:n,n); move(n,a,b,c); move(n,a,b,c); printf(n); printf(n); 13第第1111章章 遞推與遞歸遞推與遞歸void move(int m,char p,char q,char r)void move(int m,char p,char q,char r) if (m=1)if (m=1) / / 如果如果1 1個盤子，則為直接可解結點個盤子，則為直接可解結點, , printf(n%d move %d# fro

12、m %c to %c,step,m,p,r); printf(n%d move %d# from %c to %c,step,m,p,r); step+; step+; / / 步數(shù)加步數(shù)加1 1 else else move(m-1,p,r,q); move(m-1,p,r,q); / / 遞歸調(diào)用遞歸調(diào)用movemove printf(n%d move %d# from %c to %c,step,m,p,r); printf(n%d move %d# from %c to %c,step,m,p,r); step+; step+;/ / 步數(shù)加步數(shù)加1 1 move(m-1,q,p,r)

13、; move(m-1,q,p,r); / / 遞歸調(diào)用遞歸調(diào)用movemove 14第第1111章章 遞推與遞歸遞推與遞歸HanoiHanoi塔問題的特點塔問題的特點NN個盤子的從個盤子的從A A到到B B的移動可以分成三步：的移動可以分成三步：u N-1N-1個盤子從個盤子從A A到到B B的移動；的移動；u 1 1個盤子從個盤子從A A到到C C的移動的移動u N-1 N-1個盤子從個盤子從B B到到C C的移動；的移動；這三步對應的問題具備以下共性：這三步對應的問題具備以下共性：u 仍然是盤子的移動問題；仍然是盤子的移動問題；u 是規(guī)模更小的盤子的移動問題；是規(guī)模更小的盤子的移動問題；所

14、以，可以遞歸求解這些問題。所以，可以遞歸求解這些問題。 15第第1111章章 遞推與遞歸遞推與遞歸再來看一個問題，再來看一個問題，看看與前者有沒有共同之處？看看與前者有沒有共同之處？16第第1111章章 遞推與遞歸遞推與遞歸例例11.611.6：青蛙過河：青蛙過河一條小溪尺寸不大，青蛙可以從左岸跳到右岸，在左岸有一一條小溪尺寸不大，青蛙可以從左岸跳到右岸，在左岸有一石柱石柱L L，面積只容得下一只青蛙落腳，同樣右岸也有一石柱，面積只容得下一只青蛙落腳，同樣右岸也有一石柱R R，面積，面積也只容得下一只青蛙落腳。有一隊青蛙從尺寸上一個比一個小。規(guī)也只容得下一只青蛙落腳。有一隊青蛙從尺寸上一個比一

15、個小。規(guī)定初始時這隊青蛙定初始時這隊青蛙只能趴在左岸的石頭只能趴在左岸的石頭L L上上，當然是，當然是按號排一個落一按號排一個落一個，小的落在大的上面?zhèn)€，小的落在大的上面。不允許大的在小的上面。在。不允許大的在小的上面。在小溪中有小溪中有S S個石個石柱，有柱，有 y y片荷葉，規(guī)定溪中的柱子上允許一只青蛙落腳片荷葉，規(guī)定溪中的柱子上允許一只青蛙落腳，如有多只，如有多只同樣要求按號排一個落一個，同樣要求按號排一個落一個，大的在下，小的在上大的在下，小的在上。對于。對于荷葉只允荷葉只允許一只青蛙落腳許一只青蛙落腳，不允許多只在其上。對于右岸的石柱，不允許多只在其上。對于右岸的石柱R R，與左岸的

16、，與左岸的石柱石柱L L一樣一樣 ，允許多個青蛙按號排一個落一個，小的在上，大的在，允許多個青蛙按號排一個落一個，小的在上，大的在下。當青蛙從左岸的下。當青蛙從左岸的L L上跳走后就不允許再跳回來；同樣，從左岸上跳走后就不允許再跳回來；同樣，從左岸L L上跳至右岸上跳至右岸R R，或從溪中荷葉或溪中石柱跳至右岸，或從溪中荷葉或溪中石柱跳至右岸R R上的青蛙也不允上的青蛙也不允許再離開。許再離開。問在已知溪中有問在已知溪中有S S根石柱和根石柱和y y片荷葉的情況下，最多能跳片荷葉的情況下，最多能跳過多少只青蛙過多少只青蛙？17第第1111章章 遞推與遞歸遞推與遞歸解題思路：解題思路：1、定義函

17、數(shù)： Jump(S,y) 最多可跳過河的青蛙數(shù) 其中：S為河中柱子數(shù)，y為荷葉數(shù)2、先看簡單情況，河中無柱子：S=0，即Jump(0,y)。 18第第1111章章 遞推與遞歸遞推與遞歸解題思路：解題思路：當y=1時，河中有一片荷葉，起始時L上有兩只青蛙，1#在2#上面。 第一步：1# 跳到荷葉上； 第二步：2# 從L直接跳至R上； 第三步：1# 再從荷葉跳至R上。 因此：Jump(0,1)=2；左岸L右岸R荷葉19第第1111章章 遞推與遞歸遞推與遞歸當y=2時河中有兩片荷葉時，起始時：1#，2#，3# 3只青蛙落在L上， 第一步：1# 從L跳至葉 1上， 第二步：2# 從L跳至葉 2上， 第

18、三步：3# 從L直接跳至R上， 第四步：2# 從葉2跳至R上， 第五步：1# 從葉1跳至R上說明：河中有兩片荷葉時，可以過3只青蛙：Jump(0,2)=3；左岸左岸L右岸右岸R荷葉荷葉2荷葉荷葉120第第1111章章 遞推與遞歸遞推與遞歸那么，請思考：那么，請思考： Jump(0,3)=? Jump(0,4)=? Jump(0,y)=?采用歸納法：采用歸納法：Jump(0,y)=y+1在河中沒有石柱的情況下，過河的青蛙數(shù)僅取決于荷葉數(shù)，數(shù)目是荷葉數(shù)+1。21第第1111章章 遞推與遞歸遞推與遞歸1# 青蛙從 L Y；2# 青蛙從 L S；1# 青蛙從 Y S；3# 青蛙從 L Y；4# 青蛙從

19、 L R； 3# 青蛙從 Y R；左岸左岸L右岸右岸R荷葉荷葉Y石柱石柱S1# 青蛙從 S Y；2# 青蛙從 S R；1# 青蛙從 Y R；可以看出，Jump(1,1)=2*Jump(0,1)=2*2=43、再看Jump(S, y): 先看一個最簡單情況：S=1、y=1時，22第第1111章章 遞推與遞歸遞推與遞歸參照漢諾塔問題，可將借助參照漢諾塔問題，可將借助一個荷葉一個荷葉、一個石柱的青蛙跳一個石柱的青蛙跳躍躍問題分成問題分成五個步驟五個步驟： 第一步：借助荷葉將左岸上面的若干青蛙（這里是第一步：借助荷葉將左岸上面的若干青蛙（這里是1#1#與與2#2#兩只）跳到石柱上暫存；兩只）跳到石柱上

20、暫存； 第二部：左岸的下一只青蛙（這里是第二部：左岸的下一只青蛙（這里是3#3#）跳到荷葉上）跳到荷葉上； 第三步：左岸的再下一只青蛙（這里是第三步：左岸的再下一只青蛙（這里是4#4#）完成到右）完成到右岸的直接跳躍；岸的直接跳躍； 第四步：荷葉暫存的青蛙完成到右岸的跳躍；第四步：荷葉暫存的青蛙完成到右岸的跳躍； 第五步：石柱上暫存的青蛙借助荷葉完成到右岸的跳第五步：石柱上暫存的青蛙借助荷葉完成到右岸的跳躍；躍；23第第1111章章 遞推與遞歸遞推與遞歸 第一、五兩步實際上完成的就是青蛙借助一個荷葉跳第一、五兩步實際上完成的就是青蛙借助一個荷葉跳躍的過程，并且這兩步的對象是同一批青蛙，所以個躍

21、的過程，并且這兩步的對象是同一批青蛙，所以個數(shù)是數(shù)是Jump(0,1)Jump(0,1)。 第二、三、四步實際上完成的也是青蛙借助一個荷葉第二、三、四步實際上完成的也是青蛙借助一個荷葉跳躍的過程，所以個數(shù)也是跳躍的過程，所以個數(shù)也是Jump(0,1)Jump(0,1)。 所以，所以，Jump(1,1)Jump(1,1)與與Jump(0,1)Jump(0,1)是相關的，即：是相關的，即： Jump(1,1)=2Jump(1,1)=2* *Jump(0,1)Jump(0,1)；24第第1111章章 遞推與遞歸遞推與遞歸 按照這樣的思路，借助按照這樣的思路，借助s s個石柱、個石柱、y y個荷葉個荷

22、葉的青蛙跳躍過程也可以類似的歸的青蛙跳躍過程也可以類似的歸納出來，這個實現(xiàn)步驟可以分成納出來，這個實現(xiàn)步驟可以分成七個步驟七個步驟：第一步第一步：借助所有荷葉以及其余石柱將左岸上面的若干青蛙跳到第一個：借助所有荷葉以及其余石柱將左岸上面的若干青蛙跳到第一個石柱上暫存；石柱上暫存；第二步第二步：左岸的余下的青蛙借助其它可用的石柱以及所有荷葉跳到其它：左岸的余下的青蛙借助其它可用的石柱以及所有荷葉跳到其它石柱上；石柱上；第三步第三步：左岸的再余下的青蛙跳到所有荷葉上：左岸的再余下的青蛙跳到所有荷葉上第四步：左岸的再下一只青蛙完成到右岸的直接跳躍第四步：左岸的再下一只青蛙完成到右岸的直接跳躍；第五步

23、第五步：荷葉暫存的青蛙完成到右岸的跳躍；：荷葉暫存的青蛙完成到右岸的跳躍；第六步第六步：除了第一個外其余石柱上暫存的青蛙完成到右岸的跳躍；：除了第一個外其余石柱上暫存的青蛙完成到右岸的跳躍；第七步第七步：第一個石柱上暫存的青蛙借助其余石柱以及所有荷葉完成到右：第一個石柱上暫存的青蛙借助其余石柱以及所有荷葉完成到右岸的跳躍岸的跳躍 25第第1111章章 遞推與遞歸遞推與遞歸 類似的，如果以上的石柱在跳躍過程中可以看成右岸或左岸的話，類似的，如果以上的石柱在跳躍過程中可以看成右岸或左岸的話，這里的七個步驟也可以簡化成兩個階段：這里的七個步驟也可以簡化成兩個階段：第一、七兩步第一、七兩步實際上是青蛙

24、借助實際上是青蛙借助s-1s-1個石柱以及個石柱以及y y個荷葉，完成從個荷葉，完成從左岸到第一個石柱，再到右岸的跳躍的過程，而這兩步的對象是左岸到第一個石柱，再到右岸的跳躍的過程，而這兩步的對象是同一批青蛙，所以個數(shù)是同一批青蛙，所以個數(shù)是Jump(s-1,y)Jump(s-1,y)。第二步到第六步第二步到第六步完成的是左岸的青蛙借助剩余的完成的是左岸的青蛙借助剩余的n-1n-1個石柱以及所個石柱以及所有有y y個荷葉跳躍到右岸的過程，所以個數(shù)也是個荷葉跳躍到右岸的過程，所以個數(shù)也是Jump(s-1,y)Jump(s-1,y)。 所以，所以，Jump(S, y)Jump(S, y)與與Jum

25、p(s-1,y)Jump(s-1,y)是相關的，即：是相關的，即： Jump(s,y)=2Jump(s,y)=2* *Jump(s-1,y)Jump(s-1,y)；當石柱數(shù)目為當石柱數(shù)目為0 0是不需要遞歸的，此時跳躍的青蛙數(shù)目為荷葉數(shù)目是不需要遞歸的，此時跳躍的青蛙數(shù)目為荷葉數(shù)目+1+1，即，即遞歸的結束條件遞歸的結束條件為：為： Jump(0,y)=y+1;Jump(0,y)=y+1;26第第1111章章 遞推與遞歸遞推與遞歸#include #include int Jump(int, int);int Jump(int, int);/ /聲明有被調(diào)用函數(shù)聲明有被調(diào)用函數(shù)void mai

26、n()void main() int s,y,sum;int s,y,sum;/ /整型變量整型變量,s,s為河中石柱數(shù)為河中石柱數(shù),y,y為荷葉數(shù)為荷葉數(shù)printf(printf(請輸入石柱數(shù)請輸入石柱數(shù)s= );s= );/ /提示信息提示信息scanf(%d,&s);scanf(%d,&s);printf(printf(請輸入荷葉數(shù)請輸入荷葉數(shù)y= );y= );/ /提示信息提示信息scanf(%d,&y);scanf(%d,&y);sum=Jump(s,y);sum=Jump(s,y);/Jump(s,y)/Jump(s,y)為被調(diào)用函數(shù)為被調(diào)用函數(shù)

27、printf(“Jump(%d,%d)=%dn,s,y,sum); printf(“Jump(%d,%d)=%dn,s,y,sum); 27第第1111章章 遞推與遞歸遞推與遞歸int Jump(int r,int z)int Jump(int r,int z)/ /整型自定義函數(shù)整型自定義函數(shù),r,z,r,z為形參為形參 int k;int k;if (r=0)if (r=0)/ /如果如果r r為為0,0,則不再遞歸則不再遞歸, , k=z+1;k=z+1; elseelse/ /如果不為如果不為0,0,則遞歸調(diào)用則遞歸調(diào)用Jump(r-1,z)Jump(r-1,z) k=2 k=2* *

28、Jump(r-1,z);Jump(r-1,z); return(k);return(k); 28第第1111章章 遞推與遞歸遞推與遞歸【例例11.711.7】 快速排序快速排序 選擇排序、冒泡排序的排序思路比較簡單，但是排序效選擇排序、冒泡排序的排序思路比較簡單，但是排序效率較低，不能滿足需求（比如在率較低，不能滿足需求（比如在OJOJ或比賽題目中）或比賽題目中） 有沒有一些效率更高的排序方法呢？有沒有一些效率更高的排序方法呢？ 快速排序快速排序是利用是利用分治遞歸分治遞歸技術實現(xiàn)的一種高效的方法。技術實現(xiàn)的一種高效的方法。 何為何為分治遞歸分治遞歸? ? 分治法分治法簡而言之就是簡而言之就是

29、“分而治之分而治之”，亦即把一個復雜的，亦即把一個復雜的問題分成兩個或更多的子問題，再把子問題分成更小的問題分成兩個或更多的子問題，再把子問題分成更小的子問題子問題直到最后分解成的子問題可以直接求解，原直到最后分解成的子問題可以直接求解，原問題的解即子問題的解的合并。問題的解即子問題的解的合并。29第第1111章章 遞推與遞歸遞推與遞歸將要求解的較大規(guī)模的問題分割成將要求解的較大規(guī)模的問題分割成k k個更小規(guī)模的子問題。個更小規(guī)模的子問題。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 對這對這k k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再個子問題分別求解。如果子問題的

30、規(guī)模仍然不夠小，則再劃分為劃分為k k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。，很容易求出其解為止。30第第1111章章 遞推與遞歸遞推與遞歸對這對這k k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為劃分為k k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。，很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)

31、T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。底向上逐步求出原來問題的解。31第第1111章章 遞推與遞歸遞推與遞歸將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(

32、n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)32第第1111章章 遞推與遞歸遞推與遞歸將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的設計思想是，將一個難以直

33、接解決的分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。便各個擊破，分而治之。凡治眾如治寡，分數(shù)是也。凡治眾如治寡，分數(shù)是也。-孫子兵法孫子兵法33第第1111章章 遞推與遞歸遞推與遞歸 由分治法產(chǎn)生的子問題往往是原問題的較小由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。在模式，這就為使用遞歸技術提供了方便。在這種情況下，反復使用分治手段，可以使子這種情況下，反復使用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題

34、縮小到很容易直接求解。這，最終使子問題縮小到很容易直接求解。這一過程很容易導致遞歸過程的產(chǎn)生。一過程很容易導致遞歸過程的產(chǎn)生。 分治與遞歸像一對孿生兄弟，經(jīng)常出現(xiàn)在程分治與遞歸像一對孿生兄弟，經(jīng)常出現(xiàn)在程序設計中。序設計中。 34第第1111章章 遞推與遞歸遞推與遞歸 快速排序是基于分治遞歸的思想來實現(xiàn)的?？焖倥判蚴腔诜种芜f歸的思想來實現(xiàn)的。 設要排序的數(shù)組是設要排序的數(shù)組是a0an-1a0an-1，首先任意，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)

35、都放到它后面，這個過程稱，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速排序。為一趟快速排序。 35第第1111章章 遞推與遞歸遞推與遞歸一趟快速排序的算法是：一趟快速排序的算法是： 1 1）設置兩個變量）設置兩個變量i i、j j，排序開始的時候：，排序開始的時候：i=0i=0，j=n-1j=n-1； 2 2）以第一個數(shù)組元素作為關鍵數(shù)據(jù)，賦值給）以第一個數(shù)組元素作為關鍵數(shù)據(jù)，賦值給keykey，即，即 key=a0key=a0； 3 3）從）從j j開始向前搜索，即由后開始向前搜索（開始向前搜索，即由后開始向前搜索（j=j-1j=j-1），找到第一個），找到第一個小于小于keykey的值

36、的值ajaj，將其值賦給，將其值賦給aiai； 4 4）從）從i i開始向后搜索，即由前開始向后搜索（開始向后搜索，即由前開始向后搜索（i=i+1i=i+1），找到第一），找到第一個大于個大于keykey的的aiai，將其值賦給，將其值賦給ajaj； 5 5）重復第）重復第3 3、4 4步，直到步，直到 i=ji=j，此時將，此時將keykey暫存的值賦給暫存的值賦給aiai（或（或ajaj）；）；36第第1111章章 遞推與遞歸遞推與遞歸50458036156072922578ija0a1a2a3a4a5a6a7a8a9key=50 過程過程A: A: 先從后面的元素（先從后面的元素（j j

37、所指）與所指）與keykey進行比較，如進行比較，如果果aj=keyaj=key，j j往前移動（往前移動（j-j-），繼續(xù)比較下一個），繼續(xù)比較下一個ajaj，直到遇到小于，直到遇到小于keykey的元素停止。的元素停止。 將此時的小于將此時的小于keykey的的ajaj賦值給前面的元素賦值給前面的元素aiai，即：，即：ai=ajai=aj，同時，同時i i后移（后移（i+i+），指向下一個元素。），指向下一個元素。782537第第1111章章 遞推與遞歸遞推與遞歸50458036156072922578ija0a1a2a3a4a5a6a7a8a9key=50 過程過程B B： 再從前面的

38、元素（再從前面的元素（i i所指）與所指）與keykey進行比較，進行比較，如果如果ai=keyai=key，i i往后移動（往后移動（i+i+），繼續(xù)比較下一），繼續(xù)比較下一個個aiai，直到遇到小于，直到遇到小于keykey的元素停止。的元素停止。 將此時的大于將此時的大于keykey的的aiai賦值給前面的元素賦值給前面的元素ajaj，即：，即：aj=aiaj=ai，同時，同時j j前移（前移（j-j-），指向下一個元素。），指向下一個元素。 7825458038第第1111章章 遞推與遞歸遞推與遞歸50458036156072922578ija0a1a2a3a4a5a6a7a8a9ke

39、y=50再次重復上述過程再次重復上述過程A A與過程與過程B B兩個步驟，直到下標兩個步驟，直到下標i i與下標與下標j j指向同指向同一元素（即一元素（即i=ji=j）為止。）為止。當下標當下標i i與與j j相等時，相等時，i( i(或或j) j)所指的位置就是初始選作比較的元素所指的位置就是初始選作比較的元素keykey應該存放的位置，把應該存放的位置，把keykey放入該位置，放入該位置， 7825458092jjj726015ii365039第第1111章章 遞推與遞歸遞推與遞歸 這就是一趟快速排序的過程。通過這一過程，以這就是一趟快速排序的過程。通過這一過程，以5050作作為劃分的

40、樞軸元素，把一個無序的序列做了重新的元為劃分的樞軸元素，把一個無序的序列做了重新的元素調(diào)整，變成了：素調(diào)整，變成了： 其中在其中在5050之前存放的元素都小于等于之前存放的元素都小于等于5050，在，在5050之后之后的存放元素都大于等于的存放元素都大于等于5050。 疑問：這個序列還不是一個完全有序的序列，疑問：這個序列還不是一個完全有序的序列，而我們的目標是所有元素的排序呀？而我們的目標是所有元素的排序呀？2525，4545，1515，36,36,50,50, 6060，7272，9292，8080，787840第第1111章章 遞推與遞歸遞推與遞歸2525，4545，1515，36,36

41、,6060，7272，9292，8080，787850,50, 這還不是一個有序的序列這還不是一個有序的序列 但，如果把但，如果把5050之前的之前的4 4個元素的排好序，以及元素個元素的排好序，以及元素5050之后的之后的5 5個元素的排好序，就可得到所有個元素的排好序，就可得到所有1010個個元素的有序序列了。元素的有序序列了。 這兩個序列如何排序？這兩個序列如何排序？ 這兩個區(qū)間的排序問題與原問題相比較是性質(zhì)相同這兩個區(qū)間的排序問題與原問題相比較是性質(zhì)相同，但規(guī)模更小的問題，所以可以用分治遞歸的策略，但規(guī)模更小的問題，所以可以用分治遞歸的策略來完成。來完成。41第第1111章章 遞推與遞

42、歸遞推與遞歸 當然，遞歸不能無限進行下去，當劃分的區(qū)間只包當然，遞歸不能無限進行下去，當劃分的區(qū)間只包含一個元素時，該區(qū)間自身一定是一個有序的區(qū)間含一個元素時，該區(qū)間自身一定是一個有序的區(qū)間，就不用再做遞歸了，這就是遞歸終止的條件。，就不用再做遞歸了，這就是遞歸終止的條件。 排序的遞歸函數(shù)要以待排序序列的邊界作為參數(shù)，排序的遞歸函數(shù)要以待排序序列的邊界作為參數(shù)，以便每次遞歸調(diào)用時完成不同區(qū)間的排序。假設以以便每次遞歸調(diào)用時完成不同區(qū)間的排序。假設以參數(shù)參數(shù)l l與參數(shù)與參數(shù)r r分別作為區(qū)間的左右邊界，那么當分別作為區(qū)間的左右邊界，那么當l=rl=r時表示區(qū)間只有一個元素，本身有序，所以不時表

43、示區(qū)間只有一個元素，本身有序，所以不需要遞歸，否則要進行遞歸。需要遞歸，否則要進行遞歸。 42第第1111章章 遞推與遞歸遞推與遞歸程序思路如下：程序思路如下： 當左邊界當左邊界l l右邊界右邊界r r時時 1 1、執(zhí)行一趟快速排序過程，以、執(zhí)行一趟快速排序過程，以i i為界形成兩個子序列為界形成兩個子序列，i i前的所有元素皆小于等于前的所有元素皆小于等于aiai，i i之后的所有元素皆之后的所有元素皆大于等于大于等于aiai； 2 2、對、對i i之前的區(qū)間做遞歸調(diào)用，左邊界不變，右邊界之前的區(qū)間做遞歸調(diào)用，左邊界不變，右邊界為為i-1i-1； 3 3、對、對i i之后的區(qū)間做遞歸調(diào)用，左

44、邊界為之后的區(qū)間做遞歸調(diào)用，左邊界為i+1i+1，右邊界，右邊界不變。不變。 43第第1111章章 遞推與遞歸遞推與遞歸#include #include void qsort(int a,int l,int r) void qsort(int a,int l,int r) int x=al,i=l,j=r;/int x=al,i=l,j=r;/以第一個數(shù)為一趟快速排序的樞軸元素以第一個數(shù)為一趟快速排序的樞軸元素if (l=r) return;/if (l=r) return;/遞歸終止遞歸終止while(ij)while(ij) while(i=x) j-; while(i=x) j-; a

45、i=aj;ai=aj;while(ij & ai=x) i+; while(ij & ai=x) i+; aj=ai; aj=ai; ai=x; ai=x; qsort(a,l,i-1); /qsort(a,l,i-1); /左半?yún)^(qū)間遞歸調(diào)用左半?yún)^(qū)間遞歸調(diào)用qsort(a,i+1,r); /qsort(a,i+1,r); /右半?yún)^(qū)間遞歸調(diào)用右半?yún)^(qū)間遞歸調(diào)用 44第第1111章章 遞推與遞歸遞推與遞歸int main()int main() int i,n,a10001; int i,n,a10001; scanf(%d,&n);scanf(%d,&n);for(

46、i=0;in;i+)for(i=0;in;i+)scanf(%d,&ai);scanf(%d,&ai);qsort(a,0,n-1); qsort(a,0,n-1); for(i=0;in;i+)for(i=0;in;i+)printf(%d,ai);printf(%d,ai); 45第第1111章章 遞推與遞歸遞推與遞歸 排序與查找是最常用的數(shù)據(jù)操作排序與查找是最常用的數(shù)據(jù)操作 利用分治遞歸的方法可以有效提高排序的效利用分治遞歸的方法可以有效提高排序的效率：率： -快速排序快速排序 利用同樣的方法，也可以提高查找的效率：利用同樣的方法，也可以提高查找的效率： -找第找第k k

47、小的數(shù)小的數(shù) -二分查找（折半查找）二分查找（折半查找）46第第1111章章 遞推與遞歸遞推與遞歸例：找第例：找第k k小的數(shù)小的數(shù) 輸入輸入n n個數(shù)，找出其中第個數(shù)，找出其中第k(0kn)k(0kn)小的數(shù)小的數(shù) 方法：方法： 先對數(shù)組做排序，再找第先對數(shù)組做排序，再找第k k個位置的元素；個位置的元素； 排好前排好前k k個元素的順序，找到第個元素的順序，找到第k k小的元素；小的元素； -思路簡單，但時間開銷大思路簡單，但時間開銷大 怎么辦？怎么辦？ 利用類似快速排序的思想利用類似快速排序的思想-分治遞歸分治遞歸 47第第1111章章 遞推與遞歸遞推與遞歸快速排序的啟示快速排序的啟示

48、一趟快速排序的結果，以一趟快速排序的結果，以3030為軸心，分成兩個序列，為軸心，分成兩個序列，3030之前的元素均不大于之前的元素均不大于3030，3030之后的元素均不小于之后的元素均不小于30.30. 如果需要整個序列排序，只需對兩個子序列分別做遞歸如果需要整個序列排序，只需對兩個子序列分別做遞歸調(diào)用即可。調(diào)用即可。 現(xiàn)在的目標是找到其中第現(xiàn)在的目標是找到其中第k k小的元素小的元素, ,有何關系？有何關系？30 12 62 25 80 38 50 42 70 16key=30lowhigh16low12low62highhighhighhighhighhigh704250388025l

49、ow3048第第1111章章 遞推與遞歸遞推與遞歸快速排序的啟示快速排序的啟示 比如比如k=4k=4，即要找第，即要找第4 4小的元素，有什么發(fā)現(xiàn)？小的元素，有什么發(fā)現(xiàn)？ low=4(high=4)low=4(high=4) 如何來判定？如何來判定？ low=klow=k high=k high=k30 12 62 25 80 38 50 42 70 16key=3016 1262high704250388025low3049第第1111章章 遞推與遞歸遞推與遞歸快速排序的啟示快速排序的啟示 如果如果k=2k=2，該怎么辦？，該怎么辦？p 在在lowlow位置之前的序列做查找位置之前的序列做查

50、找p 是一個性質(zhì)相同但規(guī)模更小的問題，可遞歸求解是一個性質(zhì)相同但規(guī)模更小的問題，可遞歸求解 如何表示？如何表示？ 如果函數(shù)原型為如果函數(shù)原型為 find(a,s,t,k) find(a,s,t,k) 則，遞歸調(diào)用形式為：則，遞歸調(diào)用形式為：find(a,s,low-1,k)find(a,s,low-1,k)30 12 62 25 80 38 50 42 70 1616 1262high704250388025low3050第第1111章章 遞推與遞歸遞推與遞歸快速排序的啟示快速排序的啟示 如果如果k=7k=7，又該怎么辦？，又該怎么辦？p 在在lowlow位置之后的序列做查找位置之后的序列做查

51、找p 仍是一個性質(zhì)相同但規(guī)模更小的問題，可遞歸求解仍是一個性質(zhì)相同但規(guī)模更小的問題，可遞歸求解 如果函數(shù)原型為如果函數(shù)原型為 find(a,s,t,k) find(a,s,t,k)，k=2k=2時的遞歸調(diào)用形時的遞歸調(diào)用形式為：式為：find(a,s,low-1,k)find(a,s,low-1,k)， K=7K=7時可否寫為：時可否寫為： find(a, low+1,t,k)find(a, low+1,t,k)，為什么？，為什么？ 問題有何變化問題有何變化-find(a, low+1,t,k-low)-find(a, low+1,t,k-low)30 12 62 25 80 38 50 42

52、 70 1616 1262high704250388025low3051第第1111章章 遞推與遞歸遞推與遞歸#include #include int find(int a,int s,int t,int k) int find(int a,int s,int t,int k) int x=as,low=s,high=t;/int x=as,low=s,high=t;/以第一個數(shù)為樞軸元素以第一個數(shù)為樞軸元素while(lowhigh)while(lowhigh) while(low=x) high-; while(low=x) high-; alow=ahigh;alow=ahigh;wh

53、ile(lowhigh& alow=x) low+; while(lowhigh& alowk) find(a,s,low-1,k); / else if(lowk) find(a,s,low-1,k); /左半?yún)^(qū)間遞歸調(diào)用左半?yún)^(qū)間遞歸調(diào)用 else find(a,low+1,t,k-low); /else find(a,low+1,t,k-low); /右半?yún)^(qū)間遞歸調(diào)用右半?yún)^(qū)間遞歸調(diào)用 52第第1111章章 遞推與遞歸遞推與遞歸 二分查找采用跳躍式方式查找，先以有序數(shù)列二分查找采用跳躍式方式查找，先以有序數(shù)列的中點位置為比較對象，如果要找的元素值小的中點位置為比較對象，如果要

54、找的元素值小于該中點元素，則將待查序列縮小為左半部分于該中點元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區(qū)，否則為右半部分。通過一次比較，將查找區(qū)間縮小一半，所以稱這種查找方法為二分查找間縮小一半，所以稱這種查找方法為二分查找或折半查找?；蛘郯氩檎摇?二分查找的數(shù)據(jù)序列必須是有序的序列。二分查找的數(shù)據(jù)序列必須是有序的序列。 53第第1111章章 遞推與遞歸遞推與遞歸二分查找的具體查找步驟二分查找的具體查找步驟A A、取得有序序列中間位置的元素，與待查找的數(shù)據(jù)進行比較，、取得有序序列中間位置的元素，與待查找的數(shù)據(jù)進行比較，如果兩者相等表示找到，查找結束；如果兩者相等表示

55、找到，查找結束；B B、如果兩者不相等，則存在兩種可能：、如果兩者不相等，則存在兩種可能： （1 1）中間元素大于待查找的數(shù)據(jù)元素，說明如果該元素存在，只可）中間元素大于待查找的數(shù)據(jù)元素，說明如果該元素存在，只可能在中間元素之前的半個區(qū)間，到前半?yún)^(qū)間做遞歸查找；能在中間元素之前的半個區(qū)間，到前半?yún)^(qū)間做遞歸查找； （2 2）中間元素小于待查找的數(shù)據(jù)元素，說明如果該元素存在，只可）中間元素小于待查找的數(shù)據(jù)元素，說明如果該元素存在，只可能在中間元素之后的半個區(qū)間，到后半?yún)^(qū)間做遞歸查找；能在中間元素之后的半個區(qū)間，到后半?yún)^(qū)間做遞歸查找；重復以上重復以上A A、B B過程，直到找到滿足條件的記錄（查找成

56、功），或過程，直到找到滿足條件的記錄（查找成功），或直到區(qū)間不存在（查找不成功）為止。直到區(qū)間不存在（查找不成功）為止。54第第1111章章 遞推與遞歸遞推與遞歸 經(jīng)一次查找找到的情況；經(jīng)一次查找找到的情況； 經(jīng)多次查找找到的情況；經(jīng)多次查找找到的情況； 找不到的情況找不到的情況55第第1111章章 遞推與遞歸遞推與遞歸1 1、查找一次就找到的情況（查找的元素為、查找一次就找到的情況（查找的元素為4545）：）：10 15 26 36 45 60 72 80 85 96lowhighkey=45low 指示查找區(qū)間的下界;high 指示查找區(qū)間的上界;mid = (low+high)/2。mi

57、d4556第第1111章章 遞推與遞歸遞推與遞歸2 2、查找多次后找到的情況（以查找元素、查找多次后找到的情況（以查找元素2626為例）：為例）：10 15 2636 45 60 72 80 85 96lowhighkey=26low 指示查找區(qū)間的下界;high 指示查找區(qū)間的上界;mid = (low+high)/2。mid45mid15low26mid57第第1111章章 遞推與遞歸遞推與遞歸3 3、查找失敗的情況（以查找元素、查找失敗的情況（以查找元素3030為例）：為例）：10 15 2636 45 60 72 80 85 96lowhighkey=30low 指示查找區(qū)間的下界;h

58、igh 指示查找區(qū)間的上界;mid = (low+high)/2。mid45mid15low26midlow36high58第第1111章章 遞推與遞歸遞推與遞歸int Binsearch(int a,int s,int t,int key) int Binsearch(int a,int s,int t,int key) int low=s,high=t,mid; /int low=s,high=t,mid; /置當前查找區(qū)間上、下界的初值置當前查找區(qū)間上、下界的初值if (s=t)if (skey) if(amidkey) return Binsearch(a,low,mid-1,key)

59、;/ return Binsearch(a,low,mid-1,key);/左半?yún)^(qū)間遞歸查找左半?yún)^(qū)間遞歸查找elseelse return Binsearch(a,mid+1,high,key); / return Binsearch(a,mid+1,high,key); /在右半?yún)^(qū)間遞歸查找在右半?yún)^(qū)間遞歸查找 return -1; /return -1; /當當lowhighlowhigh時表示查找區(qū)間為空，查找失敗時表示查找區(qū)間為空，查找失敗 /BinSeareh /BinSeareh59第第1111章章 遞推與遞歸遞推與遞歸用遞歸實現(xiàn)回溯算法用遞歸實現(xiàn)回溯算法 回溯法也叫試探法，每次試著

60、往前走，回溯法也叫試探法，每次試著往前走，一直走到不通，然后撤回，重新試探一直走到不通，然后撤回，重新試探60第第1111章章 遞推與遞歸遞推與遞歸用遞歸實現(xiàn)回溯算法用遞歸實現(xiàn)回溯算法的幾個重要因素的幾個重要因素(1) 狀態(tài): 作為遞歸的值參。(2) 邊界條件: 作為遞歸的結束條件。(3) 遞歸范圍: 作為for循環(huán)的初值和終值。(4) 約束條件: 滿足解的條件。(5) 最優(yōu)性要求：滿足最優(yōu)解的條件。61第第1111章章 遞推與遞歸遞推與遞歸 【例【例11.911.9】 八皇后問題八皇后問題 八皇后問題，是一個古老而著名的問題，是回八皇后問題，是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀著名的溯算法的典型例題。該問題是十九世紀著名的數(shù)學家高斯數(shù)學家高斯18501850年提出：在年提出：在8 88 8格的國際象格