c語言_遞歸算法

1、1整理ppt計算機(jī)語言與程序設(shè)計計算機(jī)語言與程序設(shè)計諶諶 衛(wèi)衛(wèi) 軍軍Introduction to Computer Programming2整理ppt第第八章八章 遞歸算法遞歸算法基本概念基本概念基于回溯策略的遞歸基于回溯策略的遞歸基于分治策略的遞歸基于分治策略的遞歸 3整理ppt從前有座山，山上有座廟，廟里有一個老和尚從前有座山，山上有座廟，廟里有一個老和尚和一個小和尚，老和尚正在給小和尚講故事。和一個小和尚，老和尚正在給小和尚講故事。講的是什么故事呢？他說，從前講的是什么故事呢？他說，從前4整理pptRecursion- See Recursion. In order to unders

2、tand recursion, one must first understand recursion. 5整理pptC語言允許嵌套地調(diào)用函數(shù)，也就是說，在調(diào)用語言允許嵌套地調(diào)用函數(shù)，也就是說，在調(diào)用一個函數(shù)的過程中，又去調(diào)用另一個函數(shù)。一個函數(shù)的過程中，又去調(diào)用另一個函數(shù)。函數(shù)的嵌套調(diào)用函數(shù)的嵌套調(diào)用void main( ) study_english ( ); void study_english( ) reading( ); listening( ); writing( )void listening( ) 6整理ppt函數(shù)的嵌套調(diào)用有一個特例，即遞歸調(diào)用，也就函數(shù)的嵌套調(diào)用有一個特例，

3、即遞歸調(diào)用，也就是說，在調(diào)用一個函數(shù)的過程中，又出現(xiàn)了直接是說，在調(diào)用一個函數(shù)的過程中，又出現(xiàn)了直接或間接地去調(diào)用該函數(shù)本身。或間接地去調(diào)用該函數(shù)本身。void tell_story( ) int old_monk, young_monk; tell_story ( ); / tell_story 函數(shù)的遞歸調(diào)用函數(shù)的遞歸調(diào)用函數(shù)的遞歸調(diào)用函數(shù)的遞歸調(diào)用? ?7整理pptvoid tell_story( ) static int old_monk, young_monk; old_monk = old_monk + 1; / 年齡大了一歲年齡大了一歲 young_monk = young_mo

4、nk + 1; if(old_monk = 60) / 遞歸形式遞歸形式 tell_story ( ); else printf(對不起，已退休！對不起，已退休！); / 遞歸邊界遞歸邊界8整理ppt在語法上（簡單）在語法上（簡單）J遞歸即為普通的函數(shù)調(diào)用。遞歸即為普通的函數(shù)調(diào)用。在算法上（難）在算法上（難）J如何找到遞歸形式？如何找到遞歸形式？J如何找到遞歸邊界？如何找到遞歸邊界？如何編寫遞歸程序？如何編寫遞歸程序？ 9整理ppt遞歸算法的類型遞歸算法的類型遞歸算法可以分為兩種類型：遞歸算法可以分為兩種類型： 基于分治策略的遞歸算法；基于分治策略的遞歸算法； 基于回溯策略的遞歸算法?；诨厮?/p>

5、策略的遞歸算法。10整理ppt第第八章八章 遞歸算法遞歸算法基本概念基本概念基于回溯策略的遞歸基于回溯策略的遞歸基于分治策略的遞歸基于分治策略的遞歸 11整理ppt分而治之（分而治之（divide-and-conquer）的算法）的算法設(shè)計思想：設(shè)計思想： Divide：把問題劃分為若干個子問題；：把問題劃分為若干個子問題； Conquer：以：以同樣的方式同樣的方式分別去處理各分別去處理各個子問題；個子問題；1. Combine：把各個子問題的處理結(jié)果綜：把各個子問題的處理結(jié)果綜合起來，形成最終的處理結(jié)果。合起來，形成最終的處理結(jié)果。8.2.1 分而治之分而治之12整理ppt瑪特露什卡瑪特露

6、什卡13整理ppt調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用14整理ppt如何編寫基于分治策略的遞歸程序？如何編寫基于分治策略的遞歸程序？J在算法分析上，要建立分治遞歸的思維在算法分析上，要建立分治遞歸的思維方式。方式。J在編程實(shí)現(xiàn)上，要建立在編程實(shí)現(xiàn)上，要建立遞歸信心遞歸信心（To turst the recursion, Jerry Cain, stanford）。）。15整理ppt如何建立分治遞歸的思維方式？如何建立分治遞歸的思維方式？J基本原則：基本原則：目標(biāo)驅(qū)動目標(biāo)驅(qū)動！J計算計算n!：n! = n * (n-1)!，且，且1! = 1。遞歸形式遞歸形式遞歸邊界遞歸邊界16整理

7、ppt調(diào)用調(diào)用調(diào)用調(diào)用fact(3)fact(2)fact(1)17整理pptvoid main( ) int n; printf(請輸入一個整數(shù)：請輸入一個整數(shù)：); scanf(%d, &n); printf(%d! = %d n, n, fact(n);int fact(int n) if(n = 1) return(1); else return(n * fact(n-1);請輸入一個整數(shù)：請輸入一個整數(shù)：33! = 618整理ppt Bfact(2)fact(2)=2*fact(1)=2*fact(1)=2*1=2*1=2=2返回返回 DAfact(3)fact(3)=3*f

8、act(2)=3*fact(2)=3*2=3*2=6=6E E返回返回 Cfact(1)=1調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用和返回的遞歸示意圖調(diào)用和返回的遞歸示意圖19整理ppt如何建立遞歸信心？如何建立遞歸信心？J函數(shù)的遞歸調(diào)用到底是如何進(jìn)行的呢？函數(shù)的遞歸調(diào)用到底是如何進(jìn)行的呢？在遞歸調(diào)用時，執(zhí)行的是不是相同的代在遞歸調(diào)用時，執(zhí)行的是不是相同的代碼？訪問的是不是相同的數(shù)據(jù)？如果是碼？訪問的是不是相同的數(shù)據(jù)？如果是的話，那么大家會不會相互干擾、相互的話，那么大家會不會相互干擾、相互妨礙？妨礙？20整理pptmain的棧幀的棧幀m3void main( ) int m; printf(請輸入一個整數(shù)：請輸

9、入一個整數(shù)：); scanf(%d, &m); printf(%d! = %dn, m, fact(m);int fact(int n) if(n = 1) return(1); else return(n * fact(n-1);3nfact的棧幀的棧幀2nfact的棧幀的棧幀1nfact的棧幀的棧幀21整理ppt8.2.2 尋找最大值尋找最大值問題描述：問題描述：給定一個整型數(shù)組給定一個整型數(shù)組a，找出其中的最大，找出其中的最大值。值。如何設(shè)計相應(yīng)的如何設(shè)計相應(yīng)的遞歸算法遞歸算法？22整理ppt如何來設(shè)計相應(yīng)的遞歸算法？如何來設(shè)計相應(yīng)的遞歸算法？目標(biāo)：目標(biāo)：maxa0, a1, a

10、n-1可分解為：可分解為：maxa0, maxa1, an-1另外已知另外已知maxx x這就是遞歸算法的這就是遞歸算法的遞歸形式遞歸形式和和遞歸邊界遞歸邊界，據(jù)，據(jù)此可以編寫出相應(yīng)的遞歸函數(shù)。此可以編寫出相應(yīng)的遞歸函數(shù)。23整理pptint Max(int a, int first, int n) int max; if(first = n-1) return afirst; max = Max(a, first+1, n); if(max R) return(-1); mid = (L + R)/2; if(x = bmid) return mid; else if(x bmid) ret

11、urn bsearch(b, x, L, mid-1); else return bsearch(b, x, mid+1, R);34整理ppt8.2.4 漢諾漢諾(Hanoi)(Hanoi)塔問題塔問題相傳在古印度相傳在古印度Bramah廟中，有位僧人整天把三根柱子廟中，有位僧人整天把三根柱子上的金盤倒來倒去，原來他是想把上的金盤倒來倒去，原來他是想把64個一個比一個小的個一個比一個小的金盤從一根柱子上移到另一根柱子上去。移動過程中遵金盤從一根柱子上移到另一根柱子上去。移動過程中遵守以下規(guī)則：每次只允許移動一只盤，且大盤不得落在守以下規(guī)則：每次只允許移動一只盤，且大盤不得落在小盤上（簡單嗎？

12、若每秒移動一只盤子，需小盤上（簡單嗎？若每秒移動一只盤子，需5800億年億年）ABC35整理ppt怎樣編寫這種程序？思路上還是先從最簡單的情況分怎樣編寫這種程序？思路上還是先從最簡單的情況分析起，搬一搬看，慢慢理出思路。析起，搬一搬看，慢慢理出思路。1、在、在A柱上只有一只盤子，假定盤號為柱上只有一只盤子，假定盤號為1， 這時只需將該盤直接從這時只需將該盤直接從A搬至搬至C，記為，記為 move from A to CABC136整理ppt2、在、在A柱上有二只盤子，柱上有二只盤子，1為小盤為小盤2為大盤。為大盤。分三步進(jìn)行：分三步進(jìn)行：ABC21move from A to B;move f

13、rom A to C;move form B to C;37整理ppt3、在、在A柱上有柱上有3只盤子，從小到大分別為只盤子，從小到大分別為1號，號，2號，號，3號。號。怎么移？怎么移？ABC213分七步！分七步！38整理ppt 分三步進(jìn)行：分三步進(jìn)行： move 2 discs from A to B using C； move from A to C； move 2 discs from B to C using A ；ABC21339整理ppt4、在、在A柱上有柱上有 n 個盤子個盤子, 從小到大分別為從小到大分別為1號、號、2號、號、3 號、號、n號。號。 第第 1 步：將步：將1號、

14、號、2號、號、n-1號盤作為一個整體，號盤作為一個整體， 在在C的幫助下，從的幫助下，從A移至移至B； 第第 2 步：將步：將n號盤從號盤從A移至移至C； 第第 3 步：再將步：再將1號、號、2號、號、n-1號盤作為一個整號盤作為一個整 體，在體，在A的幫助下，從的幫助下，從B移至移至C； 這三步記為：這三步記為： move n-1 discs from A to B using C； move 1 discs from A to C； move n-1 discs from B to C using A ；遞歸形式！遞歸形式！40整理ppt定義函數(shù)定義函數(shù)move(int n, char L

15、, char M, char R);表示表示move n discs from L to R using M；如果如果 n = 1，即表示，即表示move from L to R；移動的是誰？移動的是誰？41整理ppt#include void move(int n, char L, char M, char R);void main( ) int n; printf(請輸入一個整數(shù)：請輸入一個整數(shù)：); scanf(%d, &n); move(n, A, B, C);42整理ppt/ L: Left post, M: Middle post, R: Right postvoid mo

16、ve(int n, char L, char M, char R) if(n = 1) printf(move #1 from %c to %cn, L, R); else move(n-1, L, R, M); printf(move #%d from %c to %cn, n, L, R); move(n-1, M, L, R); 43整理ppt請輸入一個整數(shù)：請輸入一個整數(shù)：3move #1 from A to Cmove #2 from A to Bmove #1 from C to Bmove #3 from A to Cmove #1 from B to Amove #2 from

17、 B to Cmove #1 from A to C一次運(yùn)行結(jié)果一次運(yùn)行結(jié)果44整理ppt8.2.5 青蛙過河青蛙過河 一條小溪尺寸不大，青蛙可以從左岸跳到右岸，在左岸有一一條小溪尺寸不大，青蛙可以從左岸跳到右岸，在左岸有一石柱石柱L，面積只容得下一只青蛙落腳，同樣右岸也有一石柱，面積只容得下一只青蛙落腳，同樣右岸也有一石柱R，面積也只容得下一只青蛙落腳。有一隊青蛙從尺寸上一個比一個面積也只容得下一只青蛙落腳。有一隊青蛙從尺寸上一個比一個小。我們將青蛙從小到大，用小。我們將青蛙從小到大，用1，2，n編號。規(guī)定初始時這編號。規(guī)定初始時這隊青蛙只能趴在左岸的石頭隊青蛙只能趴在左岸的石頭L上，按編號

18、一個落一個，小的落在上，按編號一個落一個，小的落在大的上面。不允許大的在小的上面。在小溪中有大的上面。不允許大的在小的上面。在小溪中有S根石柱，有根石柱，有y片片荷葉，規(guī)定溪中的柱子上允許一只青蛙落腳，如有多只同樣要求荷葉，規(guī)定溪中的柱子上允許一只青蛙落腳，如有多只同樣要求按編號一個落一個，大的在下，小的在上，而且必須編號相鄰。按編號一個落一個，大的在下，小的在上，而且必須編號相鄰。對于荷葉只允許一只青蛙落腳，不允許多只在其上。對于右岸的對于荷葉只允許一只青蛙落腳，不允許多只在其上。對于右岸的石柱石柱R，與左岸的石柱，與左岸的石柱L一樣允許多個青蛙落腳，但須一個落一一樣允許多個青蛙落腳，但須一

19、個落一個，小的在上，大的在下，且編號相鄰。當(dāng)青蛙從左岸的個，小的在上，大的在下，且編號相鄰。當(dāng)青蛙從左岸的L上跳上跳走后就不允許再跳回來；同樣，從左岸走后就不允許再跳回來；同樣，從左岸L上跳至右岸上跳至右岸R，或從溪，或從溪中荷葉或溪中石柱跳至右岸中荷葉或溪中石柱跳至右岸R上的青蛙也不允許再離開。問在已上的青蛙也不允許再離開。問在已知溪中有知溪中有S根石柱和根石柱和y片荷葉的情況下，最多能跳過多少只青蛙？片荷葉的情況下，最多能跳過多少只青蛙？45整理ppt這題看起來較難，但是如果我們認(rèn)真分析，理這題看起來較難，但是如果我們認(rèn)真分析，理出思路，就可化難為易。出思路，就可化難為易。思路：思路：1、

20、簡化問題，探索規(guī)律。先從個別再到一般，要善、簡化問題，探索規(guī)律。先從個別再到一般，要善于對多個因素作分解，孤立出一個一個因素來分于對多個因素作分解，孤立出一個一個因素來分析，化難為易。析，化難為易。2. 定義函數(shù)定義函數(shù) Jump ( S ,y ) 最多可跳過河的青蛙數(shù)最多可跳過河的青蛙數(shù) 其中：其中：S 河中柱子數(shù)河中柱子數(shù) y 荷葉數(shù)荷葉數(shù)46整理ppt 2 說明：河中有一片荷葉，可以過兩只青蛙，起始時說明：河中有一片荷葉，可以過兩只青蛙，起始時 L 上有兩上有兩只青蛙，只青蛙，1# 在在 2# 上面。上面。 第一步：第一步：1# 跳到荷葉上；跳到荷葉上； 第二步：第二步：2# 從從 L

21、直接跳至直接跳至 R 上；上； 第三步：第三步：1# 再從荷葉跳至再從荷葉跳至 R 上。上。 如下圖：如下圖：2#2#1#1#2 21 13 3L L左岸左岸R R右岸右岸3. 先看簡單情況，河中無柱子：先看簡單情況，河中無柱子：S = 0 ，Jump ( 0 , y ) 當(dāng)當(dāng) y = 1 時，時，Jump ( 0 , 1 ) = ；47整理ppt3 說明：河中有兩片荷葉時，可以過說明：河中有兩片荷葉時，可以過 3 只青蛙。起始時：只青蛙。起始時： 1#，2#，3# 3只青蛙落在只青蛙落在 L 上，上， 第一步：第一步：1# 從從 L 跳至葉跳至葉 1上，上， 第二步：第二步：2# 從從 L

22、跳至葉跳至葉 2上，上， 第三步：第三步：3# 從從 L 直接跳至直接跳至 R 上，上， 第四步：第四步：2# 從葉從葉 2 跳至跳至 R 上，上， 第五步：第五步：1# 從葉從葉 1 跳至跳至 R 上，上，葉1葉13 31 15 5L LR R葉2葉22 24 4采用歸納法：采用歸納法：Jump ( 0 , y ) = 當(dāng)當(dāng) y = 2 時，時， Jump ( 0 , 2 ) = ； y+1； 意思是：在河中沒有石柱的情況意思是：在河中沒有石柱的情況下，過河的青蛙數(shù)僅取決于荷葉下，過河的青蛙數(shù)僅取決于荷葉數(shù)，數(shù)目是荷葉數(shù)數(shù)，數(shù)目是荷葉數(shù)+1。48整理ppt再看再看Jump( S, y )Ju

23、mp( S, y )先看一個最簡單情況：先看一個最簡單情況： S = 1，y = 1 。從圖上看出需要從圖上看出需要 步，跳過步，跳過 只青蛙。只青蛙。S SY Y5 54 46 6L LR R1 12 23 37 78 89 91#2#4#3#3#1#2#1#1# 9 4 9 4 1# 1# 青蛙從青蛙從 L L Y Y；2# 2# 青蛙從青蛙從 L L S S；1# 1# 青蛙從青蛙從 Y Y S S；3# 3# 青蛙從青蛙從 L L Y Y；4# 4# 青蛙從青蛙從 L L R R；3# 3# 青蛙從青蛙從 Y Y R R；1# 1# 青蛙從青蛙從 S S Y Y；2# 2# 青蛙從青蛙

24、從 S S R R；1# 1# 青蛙從青蛙從 Y Y R R；49整理ppt對于對于S = 1，y = 1的情形，從另外一個角度來分析的情形，從另外一個角度來分析若沒有石柱若沒有石柱S S，最多可過，最多可過 y+1y+1 = = 2 2 只青蛙。只青蛙。有了石柱有了石柱S后，最多可過后，最多可過 2*2 = 4 只青蛙。只青蛙。步驟步驟1 1：1#1#和和2# 2# 從從 L L S S；步驟步驟2 2：3#3#和和4# 4# 從從 L L R R；步驟步驟3 3：1#1#和和2# 2# 從從 S S R R；YSLR: 1#, 2#: 3#, 4#: 1#, 2#YYY50整理ppt對于對

25、于S = 1，y 1的情形的情形若沒有石柱若沒有石柱S S，最多可過，最多可過 y+1y+1 只青蛙。只青蛙。有了石柱有了石柱S后，最多可過后，最多可過 2*(y+1) 只青蛙。只青蛙。步驟步驟1 1：前前y+1y+1只只 從從 L L S S；步驟步驟2 2：后后y+1y+1只只 從從 L L R R；步驟步驟3 3：前前y+1y+1只只 從從 S S R R；YSLR: 前前y+1只只: 后后y+1只只: 前前y+1只只YYY51整理ppt對于對于S = 2，y 1的情形的情形若只有石柱若只有石柱S1，最多可過，最多可過 2 2* *(y+1)(y+1) 只青蛙。只青蛙。有了石柱有了石柱S

26、2后，最多可過后，最多可過 只青蛙。只青蛙。YS1LR4*(y+1)S2步驟步驟1 1：前前2*(y+1)只只 從從 L L S2 S2；步驟步驟2 2：后后2*(y+1)只只 從從 L L R R；步驟步驟3 3：前前2*(y+1)只只 從從 S2 S2 R R；Y,S1Y,S1Y,S152整理ppt采用歸納法，可得出如下的遞歸形式：采用歸納法，可得出如下的遞歸形式：Jump(S, y) = 2 * Jump(S-1, y)；意思是：先讓一半的青蛙利用意思是：先讓一半的青蛙利用y片荷葉和片荷葉和S-1根石柱，落在河中剩下的那根石柱上；根石柱，落在河中剩下的那根石柱上；然后讓另一半的青蛙利用然

27、后讓另一半的青蛙利用y片荷葉和片荷葉和S-1根根石柱，落在右岸的石柱，落在右岸的R上面；最后再讓先前上面；最后再讓先前的一半青蛙，利用的一半青蛙，利用y片荷葉和片荷葉和S-1根石柱，根石柱，落在右岸的落在右岸的R上面。上面。遞歸邊界：遞歸邊界：Jump(0, y) = y + 153整理pptvoid main( ) int S, y; printf(請輸入石柱和荷葉的數(shù)目：請輸入石柱和荷葉的數(shù)目：); scanf(%d %d, &S, &y); printf(最多有最多有 %d 只青蛙過河只青蛙過河n, Jump(S, y);int Jump(int S, int y) if

28、(S = 0) return( y + 1 ); return( 2 * Jump(S-1, y);54整理ppt8.2.6 快速排序快速排序快速排序的基本思路：快速排序的基本思路：1 1、在數(shù)組、在數(shù)組a a中，有一段待排序的數(shù)據(jù)，下標(biāo)從中，有一段待排序的數(shù)據(jù)，下標(biāo)從l l到到r r。2 2、取、取alal放在變量放在變量valuevalue中，通過由右、左兩邊對中，通過由右、左兩邊對valuevalue的取值的比較，為的取值的比較，為valuevalue選擇應(yīng)該排定的位選擇應(yīng)該排定的位置。這時要將比置。這時要將比valuevalue大的數(shù)放右邊，比它小的數(shù)大的數(shù)放右邊，比它小的數(shù)放左邊。當(dāng)

29、放左邊。當(dāng)valuevalue到達(dá)最終位置后（如下標(biāo)到達(dá)最終位置后（如下標(biāo)m m），），由它劃分了左右兩個集合由它劃分了左右兩個集合l.m-1l.m-1、m+1.rm+1.r。然后轉(zhuǎn)第然后轉(zhuǎn)第1 1步，再用步，再用相同的思路相同的思路分別去處理左集合分別去處理左集合和右集合。和右集合。55整理ppt令令 qsort(l, r)表示將數(shù)組元素從下標(biāo)為表示將數(shù)組元素從下標(biāo)為 l 到到下標(biāo)為下標(biāo)為 r 的共的共 r-l+1 個元素進(jìn)行從小到大的個元素進(jìn)行從小到大的快速排序?？焖倥判?。目標(biāo)：目標(biāo)：1、讓、讓 value = al2、將、將 value 放在放在 am中，中，l m r3、使、使 al,

30、 al+1, , am-1 = am4、使、使 am am+1, am+2, , ar56整理ppt例子：數(shù)組例子：數(shù)組a當(dāng)中有當(dāng)中有7個元素等待排序。個元素等待排序。5261734lr首先，讓首先，讓value = al = a0 = 5value5a0123456下標(biāo)下標(biāo)57整理ppt5261734l第二步，從第二步，從r=6開始，將開始，將ar與與value進(jìn)行比較。進(jìn)行比較。若若ar value，則，則 r-，繼續(xù)比較。否則，繼續(xù)比較。否則，al = ar，l +。value5ra0123456下標(biāo)下標(biāo)4l58整理ppt4261734第三步，從第三步，從l=1開始，將開始，將al與與v

31、alue進(jìn)行比較。進(jìn)行比較。若若al value，則，則 l+，繼續(xù)比較。否則，繼續(xù)比較。否則，ar = al，r -。value5ra0123456下標(biāo)下標(biāo)ll6r59整理ppt4261736又回到第二步，從又回到第二步，從r=5開始，將開始，將ar與與value進(jìn)行進(jìn)行比較。若比較。若ar value，則，則 r-，繼續(xù)比較。否則，繼續(xù)比較。否則al = ar，l +。 value5a0123456下標(biāo)下標(biāo)lr3l60整理ppt4231736又回到第三步，從又回到第三步，從l=3開始，將開始，將al與與value進(jìn)行進(jìn)行比較。若比較。若al value，則，則 l+，繼續(xù)比較。否則，繼續(xù)比

32、較。否則，ar = al，r -。 value5a0123456下標(biāo)下標(biāo)rll7r61整理ppt4231776現(xiàn)在現(xiàn)在 l r，已經(jīng)找到了，已經(jīng)找到了value的正確位置，把的正確位置，把value中的值放回到數(shù)組當(dāng)中。中的值放回到數(shù)組當(dāng)中。value5a0123456下標(biāo)下標(biāo)lr562整理ppt4231576下面的任務(wù)：用剛才介紹的方法，對下面的任務(wù)：用剛才介紹的方法，對 5 左、右左、右兩側(cè)的兩段數(shù)據(jù)，分別進(jìn)行排序。兩側(cè)的兩段數(shù)據(jù)，分別進(jìn)行排序。a0123456下標(biāo)下標(biāo)1324a0123456下標(biāo)下標(biāo)lr67a0123456下標(biāo)下標(biāo)lr63整理ppt1234567最后的結(jié)果：最后的結(jié)果：a

33、0123456下標(biāo)下標(biāo)具體實(shí)現(xiàn)：幾重循環(huán)語句？具體實(shí)現(xiàn)：幾重循環(huán)語句？參考程序：略參考程序：略64整理ppt第第八章八章 遞歸算法遞歸算法基本概念基本概念基于回溯策略的遞歸基于回溯策略的遞歸基于分治策略的遞歸基于分治策略的遞歸 65整理ppt 在程序設(shè)計當(dāng)中，有相當(dāng)一類求一組解、或求在程序設(shè)計當(dāng)中，有相當(dāng)一類求一組解、或求全部解或求最優(yōu)解的問題，不是根據(jù)某種確定的全部解或求最優(yōu)解的問題，不是根據(jù)某種確定的計算法則，而是利用試探和回溯（計算法則，而是利用試探和回溯（Backtracking）的搜索技術(shù)求解。回溯法也是設(shè)計遞歸算法的一種的搜索技術(shù)求解?；厮莘ㄒ彩窃O(shè)計遞歸算法的一種重要方法，它的求解

34、過程實(shí)質(zhì)上是一個先序遍歷一重要方法，它的求解過程實(shí)質(zhì)上是一個先序遍歷一棵棵“狀態(tài)樹狀態(tài)樹”的過程，只不過這棵樹不是預(yù)先建立的，的過程，只不過這棵樹不是預(yù)先建立的，而是隱含在遍歷的過程當(dāng)中。而是隱含在遍歷的過程當(dāng)中。66整理ppt8.3.1 分書問題分書問題有五本書，它們的編號分別為有五本書，它們的編號分別為1，2，3，4，5，現(xiàn)準(zhǔn)備分給，現(xiàn)準(zhǔn)備分給 A, B, C, D, E五個人，每個五個人，每個人的閱讀興趣用一個二維數(shù)組來加以描述：人的閱讀興趣用一個二維數(shù)組來加以描述：10 ijijlike ij 喜歡 書不喜歡 書希望編寫一個程序，輸出所有的分書方案，希望編寫一個程序，輸出所有的分書方案

35、，讓人人皆大歡喜。讓人人皆大歡喜。67整理ppt假定這假定這5個人對這個人對這5本書的閱讀興趣如下表：本書的閱讀興趣如下表： 1 2 3 4 5ABCDE0011011001011010001001001人人書書68整理ppt解題思路：解題思路：1、定義一個整型的二維數(shù)組，將上表中的閱讀喜好、定義一個整型的二維數(shù)組，將上表中的閱讀喜好用初始化的方法賦給這個二維數(shù)組。用初始化的方法賦給這個二維數(shù)組?？啥x：可定義：int Like66 = 0, 0, 0,0,1,1,0, 0, 1,1,0,0,1, 0, 0,1,1,0,1, 0, 0,0,0,1,0, 0, 0,1,0,0,1;69整理ppt

36、2、定義一個整型一維數(shù)組、定義一個整型一維數(shù)組BookFlag6用來記錄書用來記錄書是否已被選用。用后五個下標(biāo)作為五本書的標(biāo)號，是否已被選用。用后五個下標(biāo)作為五本書的標(biāo)號，被選用的元素值為被選用的元素值為1, 未被選用的值為未被選用的值為0, 初始化皆為初始化皆為0.int BookFlag6 = 0;70整理ppt3、定義一個整型一維數(shù)組、定義一個整型一維數(shù)組BookTaken6用來記錄用來記錄每一個人選用了哪一本書。用數(shù)組元素的下標(biāo)來作每一個人選用了哪一本書。用數(shù)組元素的下標(biāo)來作為人的標(biāo)號，用數(shù)組元素的值來表示書號。如果某為人的標(biāo)號，用數(shù)組元素的值來表示書號。如果某個人還沒有選好書，則相應(yīng)

37、的元素值為個人還沒有選好書，則相應(yīng)的元素值為0。初始化。初始化時，所有的元素值均為時，所有的元素值均為0。int BookTaken6 = 0;4、循環(huán)變量、循環(huán)變量 i 表示人，表示人，j 表示書，表示書，i, j 1, 2, 3, 4, 571整理ppt一種方法：一種方法：枚舉法枚舉法。把所有可能出現(xiàn)的分書方案都枚舉出來，把所有可能出現(xiàn)的分書方案都枚舉出來，然后逐一判斷它們是否滿足條件，即是否然后逐一判斷它們是否滿足條件，即是否使得每個人都能夠得到他所喜歡的書。使得每個人都能夠得到他所喜歡的書。缺點(diǎn)：計算量太大。缺點(diǎn)：計算量太大。72整理ppti=1 j=1 j=2i=2j=3 j=5i=

38、3j=1i=3j=2 j=4i=4j=2 j=4i=4j=5i=5j=4 j=5 j=5 j=2i=5j=4 j=2 j=1 j=4i=4j=5 j=1i=5j=4 j=1i=3j=5i=2j=4如何抽取出如何抽取出遞歸形式？遞歸形式？73整理pptvoid person( int i );int Like66 = 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1;int BookFlag6 = 0;int BookTaken6 = 0;void main( )

39、 person( 1 );74整理pptvoid person(int i)/ 嘗試給第嘗試給第i個人分書個人分書 int j, k; for(j = 1; j = 5; j+)/ 嘗試把每本書分給第嘗試把每本書分給第i個人個人 if(BookFlagj != 0) | (Likeij = 0) continue; / 失敗失敗 BookTakeni = j; / 把第把第j本書分給第本書分給第i個人個人 BookFlagj = 1; if(i = 5)/ 已找到一種分書方案已找到一種分書方案 for(k = 1; k i, 表明這一步不可能走表明這一步不可能走 j 級臺階級臺階, 函函 數(shù)數(shù)

40、返回返回；否則，轉(zhuǎn)第三步；否則，轉(zhuǎn)第三步；第三步：這一步走第三步：這一步走 j 級臺階，即級臺階，即 paces = j; 如果如果 i - j = 0，說明已經(jīng)到達(dá)地面了，也就是，說明已經(jīng)到達(dá)地面了，也就是 已經(jīng)找到一種方案了，把它顯示出來；否則已經(jīng)找到一種方案了，把它顯示出來；否則 的話，接著走下一步，的話，接著走下一步，TryStep(i-j, s+1)；第四步：第四步： j = j +1，如果，如果 j 3，轉(zhuǎn)第二步；否則函數(shù)，轉(zhuǎn)第二步；否則函數(shù) 結(jié)束。結(jié)束。能否用分治策略？能否用分治策略？80整理ppt8.3.3 八皇后問題八皇后問題在在8 88 8的棋盤上，放置的棋盤上，放置8 8

41、個個皇后皇后（棋子），使兩兩之（棋子），使兩兩之間互不攻擊。所謂互不攻擊是說任何兩個皇后都要間互不攻擊。所謂互不攻擊是說任何兩個皇后都要滿足：滿足：（1 1）不在棋盤的同一行；）不在棋盤的同一行；（2 2）不在棋盤的同一列；）不在棋盤的同一列；（3 3）不在棋盤的同一對角線上。）不在棋盤的同一對角線上。因此可以推論出，棋盤共有因此可以推論出，棋盤共有8 8行，故至多有行，故至多有8 8個皇后，個皇后，即每一行有且僅有一個皇后。這即每一行有且僅有一個皇后。這8 8個皇后中的每一個個皇后中的每一個應(yīng)該擺放在哪一列上是解該題的任務(wù)。應(yīng)該擺放在哪一列上是解該題的任務(wù)。81整理ppt82整理ppt數(shù)據(jù)的

42、定義（數(shù)據(jù)的定義（1）：）： i 第第i i行（個）皇后，行（個）皇后，1 1 i i 8 8； j 第第j列，列， 1 1 j j 8 8； Queeni 第第i i行皇后所在的列；行皇后所在的列； ColumnjColumnj 第第j j列是否列是否安全安全，0, 10, 1；83整理ppt 1 2 3 4 5 6 7 81234567884整理ppt數(shù)據(jù)的定義（數(shù)據(jù)的定義（2）：）： Down-7.7 記錄每一條從上到下的對記錄每一條從上到下的對 角線，是否安全，角線，是否安全，0,10,1 Up2.16 Up2.16記錄每一條從下到上的對角記錄每一條從下到上的對角 角線，是否安全，角線

43、，是否安全，0,10,185整理ppt利用以上的數(shù)據(jù)定義：利用以上的數(shù)據(jù)定義： 當(dāng)我們需要在棋盤的當(dāng)我們需要在棋盤的( i, j ) 位置擺放一個皇位置擺放一個皇后的時候，可以通過后的時候，可以通過Column數(shù)組、數(shù)組、Down數(shù)組和數(shù)組和Up數(shù)組的相應(yīng)元素，來判斷該位置數(shù)組的相應(yīng)元素，來判斷該位置是否安全；是否安全； 當(dāng)我們已經(jīng)在棋盤的當(dāng)我們已經(jīng)在棋盤的( i, j ) 位置擺放了一個位置擺放了一個皇后以后，就應(yīng)該去修改皇后以后，就應(yīng)該去修改Column數(shù)組、數(shù)組、Down數(shù)組和數(shù)組和Up數(shù)組的相應(yīng)元素，把相應(yīng)的數(shù)組的相應(yīng)元素，把相應(yīng)的列和對角線設(shè)置為不安全。列和對角線設(shè)置為不安全。86整

44、理pptvoid TryQueen( int i );int Queen9 = 0 ;int Column9 = 0 ;int Down15 = 0 ;int Up15 = 0 ;void main( ) TryQueen( 1 );87整理pptvoid TryQueen(int i)/ 擺放第擺放第 i 行的皇后行的皇后 int j, k; for(j = 1; j = 8; j+)/ 嘗試把該皇后放在每一列嘗試把該皇后放在每一列 if(Columnj | Downi-j+7 | Upi+j-2) continue; / 失敗失敗 Queeni = j; / 把該皇后放在第把該皇后放在第j

45、列上列上 Columnj = 1; Downi-j+7 = 1; Upi+j-2 = 1; if(i = 8)/ 已找到一種解決方案已找到一種解決方案 for(k = 1; k = 8; k+) printf(%d , Queenk); printf(n); else TryQueen(i + 1); / 擺放第擺放第i+1行的皇后行的皇后 Queeni = 0;/ 回溯，把該皇后從第回溯，把該皇后從第j列拿起列拿起 Columnj = 0; Downi-j+7 = 0; Upi+j-2 = 0; 88整理ppt共共92組解，部分答案如下：組解，部分答案如下：方案方案1：1 5 8 6 3 7

46、 2 4方案方案2：1 6 8 3 7 4 2 5方案方案3：1 7 4 6 8 2 5 3方案方案4：1 7 5 8 2 4 6 3方案方案5：2 4 6 8 3 1 7 5方案方案6：2 5 7 1 3 8 6 4方案方案7：2 5 7 4 1 8 6 3方案方案8：2 6 1 7 4 8 3 5方案方案9：2 6 8 3 1 4 7 5方案方案10：2 7 3 6 8 5 1 489整理pptn假設(shè)在假設(shè)在棋盤上事先已經(jīng)擺放了一個國王棋盤上事先已經(jīng)擺放了一個國王，位，位置為置為，即即第第X X行第行第Y Y列列，在擺放八個皇在擺放八個皇后時，要求皇后間不能互相攻擊且不能被國后時，要求皇后

47、間不能互相攻擊且不能被國王攻擊。王攻擊。國王的攻擊范圍如下圖所示：國王的攻擊范圍如下圖所示：思考題：對題目做如下的修改思考題：對題目做如下的修改90整理pptn先輸入某一個皇后所在的位置先輸入某一個皇后所在的位置，即第，即第X X行第行第Y Y列，列，在此情形下，如何擺放其余的在此情形下，如何擺放其余的7 7個個皇后，要求找到所有解決方案。皇后，要求找到所有解決方案。91整理ppt8.3.4 過河過河問題問題問題描述：問題描述：M條狼和條狼和N條狗（條狗（NM）渡船過河，從河西）渡船過河，從河西到河?xùn)|。在每次航行中，該船最多能容納到河?xùn)|。在每次航行中，該船最多能容納2只動物，只動物，且最少需搭

48、載且最少需搭載1只動物。安全限制：無論在河?xùn)|、只動物。安全限制：無論在河?xùn)|、河西還是船上，狗的數(shù)量不能小于狼的數(shù)量。河西還是船上，狗的數(shù)量不能小于狼的數(shù)量。請問：能否找到一種方案，使所有動物都能順利過請問：能否找到一種方案，使所有動物都能順利過河。如果能，移動的步驟是什么？河。如果能，移動的步驟是什么？92整理ppt如何描述系統(tǒng)的當(dāng)前狀態(tài)？如何描述系統(tǒng)的當(dāng)前狀態(tài)？ 位置：河西岸、河?xùn)|岸、河；位置：河西岸、河?xùn)|岸、河； 對象：船、狼、狗。對象：船、狼、狗。問題分析問題分析93整理ppt三元組三元組（W、 D、 B）WolfDogBoat例如：例如：(2, 2, W)94整理ppt若若M2、N2(

49、2, 2, W)(0, 2, E)(1, 2, W)(0, 0, E)(2, 0, W)(1, 0, E)95整理ppt 問題實(shí)質(zhì)：在一個有向圖中尋找一條問題實(shí)質(zhì)：在一個有向圖中尋找一條路徑路徑； 狀態(tài)轉(zhuǎn)換：如何從一個結(jié)點(diǎn)狀態(tài)轉(zhuǎn)換：如何從一個結(jié)點(diǎn)跳轉(zhuǎn)跳轉(zhuǎn)到另一個到另一個結(jié)點(diǎn)；結(jié)點(diǎn)； 狀態(tài)樹？狀態(tài)樹？問題分析問題分析96整理ppt 如何避免訪問如何避免訪問重復(fù)的重復(fù)的結(jié)點(diǎn)？結(jié)點(diǎn)？ 如何用如何用簡練的簡練的語句實(shí)現(xiàn)狀態(tài)的轉(zhuǎn)換？語句實(shí)現(xiàn)狀態(tài)的轉(zhuǎn)換？ 如何將如何將5種情形種情形歸納歸納為同一種形式？為同一種形式？技術(shù)難點(diǎn)技術(shù)難點(diǎn)97整理ppt#include #define MAX_M 20#defi

50、ne MAX_N 20int M, N;struct Status int W, D, B;steps1000;int s = 0, num = 0;int flagsMAX_MMAX_N2 = 0;void CrossRiver(int W, int D, int B);int IsValid(int w, int d, int b);98整理pptvoid main( ) scanf(%d %d, &M, &N); flagsMN0 = 1; steps0.W = M; steps0.D = N; steps0.B = 0; s = 1; CrossRiver(M, N,

51、0);void CrossRiver(int W, int D, int B) int i, j, f; int w, d, b;99整理ppt if(B = 0) f = -1; else f = 1; for(j = 1; j = 5; j+) switch(j) case 1: w = W + f*1; d = D; break; case 2: w = W + f*2; d = D; break; case 3: d = D + f*1; w = W; break; case 4: d = D + f*2; w = W; break; case 5: w = W + f*1; d =

52、D + f*1; break; b = 1 - B;100整理ppt if(IsValid(w, d, b) flagswdb = 1; stepss.W = w; stepss.D = d; stepss.B = b; s+; if(w = 0 & d = 0 & b = 1) num +; printf(Solutions %d: n, num); for(i = 0; i s; i+) printf(%d %d %dn, stepsi.W, stepsi.D, stepsi.B); else CrossRiver(w, d, b); flagswdb = 0; s-; 1

53、01整理pptint IsValid(int w, int d, int b) if(w M) return 0; if(d N) return 0; if(flagswdb = 1) return 0; if(d 0 & w d) return 0; if(N-d 0) & (M-w N-d) return 0; return 1;102整理ppt2 2Solutions 1:2 2 00 2 11 2 01 0 12 0 00 0 1Solutions 2:2 2 00 2 11 2 01 0 11 1 00 0 1Solutions 3:2 2 01 1 11 2 01

54、0 12 0 00 0 1Solutions 4:2 2 01 1 11 2 01 0 11 1 00 0 1103整理ppt8.3.5 排列排列問題問題n個對象的一個排列，就是把這個對象的一個排列，就是把這 n 個不同的個不同的對象放在同一行上的一種安排。例如，對于對象放在同一行上的一種安排。例如，對于三個對象三個對象 a, ,b, ,c，總共有，總共有6個排列：個排列：a b ca c bb a cb c ac a bc b an 個對象的排列個數(shù)就是個對象的排列個數(shù)就是 n!。104整理ppt如何生成排列？如何生成排列？基于分治策略的遞歸算法：基于分治策略的遞歸算法： 假設(shè)這假設(shè)這 n

55、個對象為個對象為 1, 2, 3, , n； 對于前對于前n-1個元素的每一個排列個元素的每一個排列 a1 a2 an-1，1 ai n-1，通過在所有可能的位置上插入通過在所有可能的位置上插入數(shù)字?jǐn)?shù)字 n，來形成，來形成 n 個所求的排列，即：個所求的排列，即：n a1 a2 an-1a1 n a2 an-1a1 a2 n an-1 a1 a2 an-1 n105整理ppt例如：生成例如：生成1,2,3的所有排列的所有排列permutation(3) permutation(2) permutation(1)permutation(1)：1permutation(2)：2 1，1 2perm

56、utation(3)：3 2 1，2 3 1，2 1 3， 3 1 2，1 3 2，1 2 3106整理ppt基于回溯策略的遞歸算法：基于回溯策略的遞歸算法： 基本思路：每一個排列的長度為基本思路：每一個排列的長度為 N，對這，對這N個不同的位置，按照順序逐一地枚舉所有個不同的位置，按照順序逐一地枚舉所有可能出現(xiàn)的數(shù)字?？赡艹霈F(xiàn)的數(shù)字。 定義一維數(shù)組定義一維數(shù)組NumFlagN+1用來記錄用來記錄1-N之之間的每一個數(shù)字是否已被使用，間的每一個數(shù)字是否已被使用，1表示已使表示已使用，用，0表示尚未被使用，初始化皆為表示尚未被使用，初始化皆為0；107整理ppt 定義一維數(shù)組定義一維數(shù)組NumTakenN+1，用來記錄每，用來記錄每一個位置上使用的是