數(shù)據(jù)結(jié)構(gòu)課件：05、第六章 遞歸[新][薦]

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 1 頁(yè)頁(yè)第六章第六章 遞遞 歸歸第一節(jié)第一節(jié) 遞歸的定義遞歸的定義第二節(jié)第二節(jié) 基本遞歸過程基本遞歸過程第三節(jié)第三節(jié) 遞歸過程實(shí)現(xiàn)與堆棧遞歸過程實(shí)現(xiàn)與堆棧第四節(jié)第四節(jié) 遞歸法求解問題遞歸法求解問題第五節(jié)第五節(jié) 遞歸的效率遞歸的效率數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 2 頁(yè)頁(yè)線性表線性表數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 3 頁(yè)頁(yè)棧和遞歸在程序設(shè)計(jì)中的應(yīng)用是非常棧和遞歸在程序設(shè)計(jì)中的應(yīng)用是非常廣泛的，如對(duì)于迷宮的求解、表達(dá)式的廣泛的，如對(duì)于迷宮的求解、表達(dá)式的求解等都可以用棧來解決。典型的求解等都可以用棧來解決。典型的hanoihanoi塔問題，樹

2、和圖的遍歷等都可以用遞歸塔問題，樹和圖的遍歷等都可以用遞歸來解決。遞歸算法的設(shè)計(jì)實(shí)際上就是對(duì)來解決。遞歸算法的設(shè)計(jì)實(shí)際上就是對(duì)問題的抽象的過程，如果抽象到每個(gè)小問題的抽象的過程，如果抽象到每個(gè)小問題都有相同特征時(shí)，那就形成了遞歸，問題都有相同特征時(shí)，那就形成了遞歸，遞歸算法簡(jiǎn)明易懂。遞歸算法簡(jiǎn)明易懂。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 4 頁(yè)頁(yè) 遞歸不僅是數(shù)學(xué)中的一個(gè)重要概念，遞歸不僅是數(shù)學(xué)中的一個(gè)重要概念，也是計(jì)算技術(shù)中重要的概念之一。也是計(jì)算技術(shù)中重要的概念之一。20世世紀(jì)紀(jì)30年代，正是可計(jì)算的遞歸函數(shù)理論年代，正是可計(jì)算的遞歸函數(shù)理論與圖靈機(jī)演算和與圖靈機(jī)演算和POST規(guī)范系統(tǒng)等理

3、論規(guī)范系統(tǒng)等理論一起為計(jì)算理論的建立奠定了基礎(chǔ)。一起為計(jì)算理論的建立奠定了基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 5 頁(yè)頁(yè)從方法論意義上說，遞歸方法是一種從從方法論意義上說，遞歸方法是一種從簡(jiǎn)單到復(fù)雜、從低級(jí)到高級(jí)的可連續(xù)操作的解簡(jiǎn)單到復(fù)雜、從低級(jí)到高級(jí)的可連續(xù)操作的解決問題的方法。決問題的方法。 在人們的思維過程中，普遍存在著遞歸在人們的思維過程中，普遍存在著遞歸現(xiàn)象和遞歸機(jī)制。現(xiàn)象和遞歸機(jī)制。 對(duì)于某些問題，只能用遞歸方法來處理；對(duì)于某些問題，只能用遞歸方法來處理；對(duì)于某些問題，用遞歸方法處理比其他方法更對(duì)于某些問題，用遞歸方法處理比其他方法更有效。有效。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程

4、精品課程第第 6 頁(yè)頁(yè)6.1 什么是遞歸什么是遞歸 xn=x*x*x*x （n個(gè)個(gè)x連乘連乘） xn+1=xn * x S(n)=1+2+3+(n-1)+n S(n+1)=S(n)+(n+1)優(yōu)點(diǎn)：優(yōu)點(diǎn)：直觀、有效直觀、有效 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 7 頁(yè)頁(yè)定義：定義：如果一個(gè)對(duì)象部分地如果一個(gè)對(duì)象部分地包含包含它自己，它自己，或者利用自己定義自己的方式來定或者利用自己定義自己的方式來定義或描述，則稱義或描述，則稱這個(gè)對(duì)象這個(gè)對(duì)象是遞歸的；是遞歸的；如果一個(gè)過程如果一個(gè)過程直接或間接直接或間接地調(diào)用自地調(diào)用自己，則稱這個(gè)己，則稱這個(gè)過程是過程是一個(gè)遞歸過程。一個(gè)遞歸過程。組成：

5、組成：遞歸調(diào)用、遞歸終止條件遞歸調(diào)用、遞歸終止條件數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 8 頁(yè)頁(yè)以下三種情況適于用遞歸求解問題：以下三種情況適于用遞歸求解問題：1.問題的定義是遞歸的問題的定義是遞歸的2.問題所涉及的數(shù)據(jù)結(jié)構(gòu)是遞歸的；問題所涉及的數(shù)據(jù)結(jié)構(gòu)是遞歸的；3.問題的解法滿足遞歸的性質(zhì)。問題的解法滿足遞歸的性質(zhì)。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 9 頁(yè)頁(yè)1、問題的定義是遞歸的、問題的定義是遞歸的階乘函數(shù)、冪函數(shù)階乘函數(shù)、冪函數(shù)和和斐波那契數(shù)列。斐波那契數(shù)列。例例階乘函數(shù)的定義階乘函數(shù)的定義 0n ! 10n 1!nnn數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 10 頁(yè)頁(yè)求解階乘函數(shù)

6、的遞歸過程求解階乘函數(shù)的遞歸過程long Factorial(long n)if (n=0) return 1; /遞歸終止條件遞歸終止條件else return n * Factorial(n-1); /遞歸調(diào)用過程遞歸調(diào)用過程數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 11 頁(yè)頁(yè)求解求解 4! 的過程的過程數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 12 頁(yè)頁(yè)計(jì)算斐波那契數(shù)列的函數(shù)計(jì)算斐波那契數(shù)列的函數(shù)Fib(n)的定義的定義1),2() 1(0,1,)(nnFibnFibnnnFib求解斐波那契數(shù)列的遞歸算法求解斐波那契數(shù)列的遞歸算法long Fib ( long n ) if ( n = 1

7、) return n; else return Fib (n- -1) + Fib (n- -2);數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 13 頁(yè)頁(yè)遞歸求解的過程：遞歸求解的過程： 對(duì)于一個(gè)比較復(fù)雜的問題，如果能夠?qū)τ谝粋€(gè)比較復(fù)雜的問題，如果能夠把它把它分解分解為若干個(gè)為若干個(gè)相對(duì)簡(jiǎn)單相對(duì)簡(jiǎn)單的、而且的、而且解法解法相同相同或或類似類似的子問題，那么當(dāng)這些子問題的子問題，那么當(dāng)這些子問題獲得解決時(shí)，原問題就獲得解決分治獲得解決時(shí)，原問題就獲得解決分治策略。策略。 子問題無需分解就可以直接解決時(shí)，子問題無需分解就可以直接解決時(shí)，停止分解，直接求解該子問題停止分解，直接求解該子問題遞歸結(jié)遞歸結(jié)束

8、條件。束條件。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 14 頁(yè)頁(yè)2、問題所涉及的數(shù)據(jù)結(jié)構(gòu)是遞歸的例單鏈表 head=NULL7245head36數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 15 頁(yè)頁(yè)在頭指針為在頭指針為p的單鏈表中搜索的單鏈表中搜索data值為值為item的結(jié)點(diǎn)的結(jié)點(diǎn)template void Search（Node *p，T item）if（p = = NULL）cerr data = = item）Dealwith（p）；）；/ 通過通過Dealwith函數(shù)對(duì)函數(shù)對(duì)該節(jié)點(diǎn)進(jìn)行一定的處理該節(jié)點(diǎn)進(jìn)行一定的處理elseSearch（p-next，item）；）；數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品

9、課程精品課程第第 16 頁(yè)頁(yè)搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值template void Find (Node *f ) if ( f next = NULL ) cout f data endl; else Find ( f next );數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 17 頁(yè)頁(yè)二叉樹：二叉樹是數(shù)據(jù)元素的有窮二叉樹：二叉樹是數(shù)據(jù)元素的有窮集合，它或者為空集（空二叉集合，它或者為空集（空二叉 樹），或者由一個(gè)根元素和其下的兩樹），或者由一個(gè)根元素和其下的兩棵互不相交的二叉樹（左子樹和右子棵互不相交的二叉樹（左子樹和右子樹）構(gòu)成。樹）構(gòu)成。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)

10、 精品課程精品課程第第 18 頁(yè)頁(yè)3、問題的解法滿足遞歸的性質(zhì)例如，漢諾塔例如，漢諾塔(Tower of Hanoi)問題問題 問題的提出：?jiǎn)栴}的提出：在在19世紀(jì)末，布拉瑪神廟世紀(jì)末，布拉瑪神廟(Temple of Bramah)里的傳教士玩著一種游戲，里的傳教士玩著一種游戲，據(jù)說他們的游戲裝置是由一塊銅板上有三根金剛據(jù)說他們的游戲裝置是由一塊銅板上有三根金剛石針，針上放有石針，針上放有64個(gè)直徑大小不等的金盤組成的。個(gè)直徑大小不等的金盤組成的。游戲的目標(biāo)是把左面針上的金盤移動(dòng)到右面的針游戲的目標(biāo)是把左面針上的金盤移動(dòng)到右面的針上，移動(dòng)過程中一次只能移動(dòng)一個(gè)盤子，不允許上，移動(dòng)過程中一次只能

11、移動(dòng)一個(gè)盤子，不允許大盤放在小盤上面，只能借助于中間的針。他們大盤放在小盤上面，只能借助于中間的針。他們認(rèn)為這種游戲的結(jié)束就意味著世界末日的到來。認(rèn)為這種游戲的結(jié)束就意味著世界末日的到來。歐洲人把這種游戲叫做漢諾塔歐洲人把這種游戲叫做漢諾塔(Tower of Hanoi)游戲。游戲。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 19 頁(yè)頁(yè)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 20 頁(yè)頁(yè)對(duì)于對(duì)于n階漢諾塔進(jìn)行一下分析：階漢諾塔進(jìn)行一下分析：1.把把n個(gè)盤子從上到下編號(hào)個(gè)盤子從上到下編號(hào)1n,要把要把n個(gè)盤子從個(gè)盤子從a塔移動(dòng)到塔移動(dòng)到c塔塔,首先借用首先借用b塔作為存放盤子的臨時(shí)塔作為存放盤子的臨時(shí)

12、塔，把上面的塔，把上面的n-1個(gè)盤子移動(dòng)到個(gè)盤子移動(dòng)到b;2.把第把第n個(gè)盤子移動(dòng)到個(gè)盤子移動(dòng)到c3.那么如何把第那么如何把第n-1個(gè)盤子移動(dòng)到個(gè)盤子移動(dòng)到c？ 可以把可以把a(bǔ)作為臨時(shí)塔，把第作為臨時(shí)塔，把第n-1盤子上面的盤子上面的n-2個(gè)盤子從個(gè)盤子從b移動(dòng)到移動(dòng)到a，把第，把第n-2個(gè)盤子移動(dòng)到個(gè)盤子移動(dòng)到c。這。這樣樣n-2個(gè)盤子又回到了個(gè)盤子又回到了a上了。上了。4.以此類推，下面以此類推，下面n-2個(gè)盤子的移動(dòng)仿佛是在重復(fù)個(gè)盤子的移動(dòng)仿佛是在重復(fù)第第1、2步操作，這個(gè)問題變成了典型的遞歸問題。步操作，這個(gè)問題變成了典型的遞歸問題。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 21 頁(yè)頁(yè)v

13、oid Hanoi (int n, String A, String B, String C ) / if ( n = 1 ) cout move A to C endl; else Hanoi ( n-1, A, C, B ); cout move A to C endl; Hanoi ( n-1, B, A, C ); 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 22 頁(yè)頁(yè)6.2基本遞歸過程基本遞歸過程 遞歸過程在實(shí)現(xiàn)時(shí)，發(fā)生遞歸調(diào)用：遞歸過程在實(shí)現(xiàn)時(shí)，發(fā)生遞歸調(diào)用：分為分為內(nèi)部調(diào)用和外部調(diào)用內(nèi)部調(diào)用和外部調(diào)用。 調(diào)用方式不同，返回的方式也不相同。調(diào)用方式不同，返回的方式也不相同。v遞歸調(diào)用正

14、確進(jìn)行：調(diào)用時(shí)參數(shù)傳遞正遞歸調(diào)用正確進(jìn)行：調(diào)用時(shí)參數(shù)傳遞正確確v過程結(jié)束正確返回：返回地址正確過程結(jié)束正確返回：返回地址正確數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 23 頁(yè)頁(yè)在高級(jí)語言（編譯程序）中，是利用在高級(jí)語言（編譯程序）中，是利用“遞歸工作棧遞歸工作棧”來來實(shí)現(xiàn)遞歸調(diào)用的。實(shí)現(xiàn)遞歸調(diào)用的。 f(n) f(n-1) f(n-2) f(1) f(0)調(diào)用時(shí)執(zhí)行入棧操作保存現(xiàn)場(chǎng)，返回時(shí)執(zhí)行出棧調(diào)用時(shí)執(zhí)行入棧操作保存現(xiàn)場(chǎng)，返回時(shí)執(zhí)行出棧操作恢復(fù)現(xiàn)場(chǎng)操作恢復(fù)現(xiàn)場(chǎng)調(diào)用調(diào)用返回返回調(diào)用點(diǎn)調(diào)用點(diǎn) PnPn-1Pn-2P11數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 24 頁(yè)頁(yè)層層向下遞歸，退出時(shí)的次序正好

15、相反：層層向下遞歸，退出時(shí)的次序正好相反：遞歸次序遞歸次序n! (n-1)! (n-2)! 1! 0!=1 返回次序返回次序工作記錄：工作記錄：返回地址返回地址參數(shù)參數(shù) （函數(shù)名、引用參數(shù)與數(shù)組參數(shù)等）（函數(shù)名、引用參數(shù)與數(shù)組參數(shù)等）局部變量局部變量數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 25 頁(yè)頁(yè)函數(shù)遞歸時(shí)的活動(dòng)記錄函數(shù)遞歸時(shí)的活動(dòng)記錄數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 26 頁(yè)頁(yè) long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1); RetLoc2 void main ( )

16、int Result; Result = Factorial (4);RetLoc1 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 27 頁(yè)頁(yè)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 28 頁(yè)頁(yè)堆棧堆棧: :遞歸算法轉(zhuǎn)化為非遞歸算法遞歸算法轉(zhuǎn)化為非遞歸算法CREATS ( S )：建立一個(gè)堆棧：建立一個(gè)堆棧 S;S x : 元素元素 x 進(jìn)棧；進(jìn)棧； x S : 元素元素 x 出棧；出棧；StackEmpty(S): 若若 S 為空，返回為空，返回1.最后一次發(fā)生的遞歸過程必須最先完成。最后一次發(fā)生的遞歸過程必須最先完成。6.3遞歸過程的實(shí)現(xiàn)：堆棧與遞歸遞歸過程的實(shí)現(xiàn)：堆棧與遞歸數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品

17、課程精品課程第第 29 頁(yè)頁(yè)例例2.3 計(jì)算數(shù)組計(jì)算數(shù)組 A 中最大中最大最小元素的算法最小元素的算法BS 。算法算法BS（A ，i ，j . fmax ，fmin）/ 在數(shù)組在數(shù)組A的第的第i個(gè)元素到第個(gè)元素到第j個(gè)元素之間尋找最大個(gè)元素之間尋找最大和最小元素，已知和最小元素，已知i j 。BS1 遞歸出口遞歸出口 IF i = j THEN （ fmaxfminAi. RETURN. ） IF i = j 1 THEN（ IF Ai n THEN RETURN(0). ELSE IF(n = k OR k = 0) THEN RETURN(1).COMM2遞歸調(diào)用遞歸調(diào)用RETURN (C

18、OMM(n-1, k) + COMM(n-1, k-1) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 43 頁(yè)頁(yè)遞歸的應(yīng)用回溯遞歸的應(yīng)用回溯(backtracking)尋找特定問題解的一種比較可靠的方法是首先列出尋找特定問題解的一種比較可靠的方法是首先列出所有候選解，然后依次檢查每一個(gè)候選解，在檢查所有候選解，然后依次檢查每一個(gè)候選解，在檢查完所有或部分候選解后，即可找到所需要的解。完所有或部分候選解后，即可找到所需要的解。 理理論上，當(dāng)候選解的數(shù)量有限并且通過檢查所有或部論上，當(dāng)候選解的數(shù)量有限并且通過檢查所有或部分候選解能夠得到所需要的解的時(shí)候，上述方法是分候選解能夠得到所需要的解的時(shí)候，上述

19、方法是可行的?？尚械?。 對(duì)候選解進(jìn)行系統(tǒng)檢查的方法有多種，其對(duì)候選解進(jìn)行系統(tǒng)檢查的方法有多種，其中中回溯回溯和分枝限界法是比較常用的兩種。和分枝限界法是比較常用的兩種。6.4.2 回回 溯溯數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 44 頁(yè)頁(yè) 回溯法試圖通過建立部分的解決方法來回溯法試圖通過建立部分的解決方法來得到整個(gè)問題的解決方案。該算法可將一個(gè)得到整個(gè)問題的解決方案。該算法可將一個(gè)局部的解決方法擴(kuò)展到整個(gè)問題。局部的解決方法擴(kuò)展到整個(gè)問題。 如果從局部的解決方法肯定不能得到整如果從局部的解決方法肯定不能得到整個(gè)問題的解決方案，也就是說局部的解將導(dǎo)個(gè)問題的解決方案，也就是說局部的解將導(dǎo)致走進(jìn)死

20、胡同，這時(shí)就要通過移除最近加入致走進(jìn)死胡同，這時(shí)就要通過移除最近加入的部分將算法回退，并且嘗試其他的方法。的部分將算法回退，并且嘗試其他的方法。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 45 頁(yè)頁(yè)回溯的基本思想是：為了求得問題的解，先選回溯的基本思想是：為了求得問題的解，先選擇某一種可能情況向前探索，在探索過程中，擇某一種可能情況向前探索，在探索過程中，一旦發(fā)現(xiàn)原來的選擇是錯(cuò)誤的，就退回一步重一旦發(fā)現(xiàn)原來的選擇是錯(cuò)誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至新選擇，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至得到解或證明無解。得到解或證明無解。 回溯法解決的問題：回溯法解決的問題：貨船裝箱、背

21、包、最大完貨船裝箱、背包、最大完備子圖、旅行商和電路板排列備子圖、旅行商和電路板排列數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 46 頁(yè)頁(yè)迷宮老鼠問題2,12,22,31,11,21,33,13,23,3數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 47 頁(yè)頁(yè) 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0(1,1)(1,2) (1,3)失敗失敗，回溯回溯到到(1,2)(1,1) (2,1) (3,1) (3,2) (3,3)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 48 頁(yè)頁(yè)迷宮問題迷宮問題小型迷宮小型迷宮 路口 動(dòng)作 結(jié)果 (入口) 正向走 進(jìn)到 左拐彎 進(jìn)到 右拐彎 進(jìn)到 (

22、堵死) 回溯 退到 (堵死) 回溯 退到 正向走 進(jìn)到 (堵死) 回溯 退到 右拐彎 進(jìn)到 左拐彎 進(jìn)到 (出口)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 49 頁(yè)頁(yè)例：例： n-皇后問題皇后問題在國(guó)際象棋中，最強(qiáng)大的棋子是皇后，在國(guó)際象棋中，最強(qiáng)大的棋子是皇后，因?yàn)樗芄羲谛?、所在列?nèi)或因?yàn)樗芄羲谛小⑺诹袃?nèi)或沿對(duì)角方向的任何一個(gè)棋子。沿對(duì)角方向的任何一個(gè)棋子。n-皇后皇后問題要求在棋盤上放置問題要求在棋盤上放置n個(gè)皇后，使個(gè)皇后，使得沒有哪個(gè)皇后能攻擊其他的皇后。得沒有哪個(gè)皇后能攻擊其他的皇后。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 50 頁(yè)頁(yè)在回溯中，由于每個(gè)皇后都必須放置

23、在在回溯中，由于每個(gè)皇后都必須放置在不同的行中，所以不同的行中，所以n-皇后問題的解決方皇后問題的解決方案可以表示為一個(gè)案可以表示為一個(gè)n元組元組(x1, , xn)，這，這里的里的xi 是把第是把第i個(gè)皇后放在第個(gè)皇后放在第i行的列數(shù)且行的列數(shù)且1 xi n. 由于任何兩個(gè)皇后都不能出現(xiàn)由于任何兩個(gè)皇后都不能出現(xiàn)在同一列中，因此在同一列中，因此n元組元組(x1, , xn)中沒中沒有兩個(gè)元素是相同的。有兩個(gè)元素是相同的。那么，應(yīng)該如何判斷兩個(gè)皇后是否在同那么，應(yīng)該如何判斷兩個(gè)皇后是否在同一斜角線上呢？一斜角線上呢？數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 51 頁(yè)頁(yè) 如果設(shè)想棋盤的方格像二維數(shù)

24、組如果設(shè)想棋盤的方格像二維數(shù)組A(1: n, 1: n)的的下標(biāo)那樣標(biāo)記，對(duì)于在同一條斜角線上的由左上下標(biāo)那樣標(biāo)記，對(duì)于在同一條斜角線上的由左上方到右下方的每一個(gè)元素都有相同的方到右下方的每一個(gè)元素都有相同的“行行 列列”值，值，同樣，在同一條上的由右上方到左下方的每一個(gè)同樣，在同一條上的由右上方到左下方的每一個(gè)元素則有相同的元素則有相同的“行行+列列”值。假設(shè)有兩個(gè)皇后被值。假設(shè)有兩個(gè)皇后被放置在放置在(i, j)和和(k, l)位置上，那么根據(jù)以上所述，僅位置上，那么根據(jù)以上所述，僅當(dāng)當(dāng) i j k l 或或 i+j k+l時(shí)，它們才在同一條斜角線上。將這兩個(gè)等式分時(shí)，它們才在同一條斜角線

25、上。將這兩個(gè)等式分別變換成別變換成 j l i k 或或 j l k i因此，當(dāng)且僅當(dāng)因此，當(dāng)且僅當(dāng) | j l | | i k | 時(shí)，兩個(gè)皇后在同時(shí)，兩個(gè)皇后在同一條斜角線上，這里的一條斜角線上，這里的| j l |為為j l的絕對(duì)值。的絕對(duì)值。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 52 頁(yè)頁(yè)n-皇后問題的解為一個(gè)皇后問題的解為一個(gè)n元組，使用一個(gè)大元組，使用一個(gè)大小為小為n的數(shù)組的數(shù)組queenInRow來存儲(chǔ)。其中來存儲(chǔ)。其中queenInRow k表示第表示第k行的第行的第k個(gè)皇后所個(gè)皇后所在列的位置。例如在列的位置。例如queenInRow 1=7表示表示第一個(gè)皇后被放在第一行、

26、第第一個(gè)皇后被放在第一行、第7列。列。假設(shè)已經(jīng)將第假設(shè)已經(jīng)將第k-1個(gè)皇后放入第個(gè)皇后放入第k-1行中，行中，接下來嘗試將第接下來嘗試將第k個(gè)皇后放入第個(gè)皇后放入第k行的某一行的某一列。編寫算法列。編寫算法PLACE(k, i . result)，當(dāng)?shù)?，?dāng)?shù)趉個(gè)皇后能放置于第個(gè)皇后能放置于第k行第行第i列則返回列則返回true；否；否則返回則返回false。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 53 頁(yè)頁(yè)算法算法PLACE要測(cè)試兩種情況，即要測(cè)試兩種情況，即queenInRow k是否不同于前面是否不同于前面queenInRow 1，queenInRowk 1的值以及在同一條斜角線上是否有別

27、的的值以及在同一條斜角線上是否有別的皇后?；屎?。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 54 頁(yè)頁(yè)算法算法PLACE( k, i . result)/*如果一個(gè)皇后能放在第如果一個(gè)皇后能放在第k行第行第i列則返回列則返回true；否則返回；否則返回false，結(jié)果保存在，結(jié)果保存在result中中 */PLACE1 初始化初始化 j1.PLACE2 判定能否放置判定能否放置 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 55 頁(yè)頁(yè)WHILE j k DO( IF queenInRow (j) = i /*列列i中已經(jīng)放置皇后中已經(jīng)放置皇后*/OR ABS(queenInRow j i) = ABS

28、(j k) /*斜角線上已經(jīng)放皇后了斜角線上已經(jīng)放皇后了*/ THEN (resultfalse. RETURN(result). ) jj+1.) resulttrue. RETURN (result). 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 56 頁(yè)頁(yè)算法算法NQUEENS( k)/*此算法使用遞歸算法求出在一個(gè)此算法使用遞歸算法求出在一個(gè)nn的棋盤上放置的棋盤上放置n個(gè)個(gè)皇后，使其不能互相攻擊的所有可能位置皇后，使其不能互相攻擊的所有可能位置 */NQUEENS1 FOR i = 1 TO n DO ( PLACE(k,i. canPlace). /*此處能放這個(gè)皇后嗎此處能放這個(gè)皇后

29、嗎*/ IF canPlace = true THEN /*能放置能放置*/ ( queenInRowki. IF k= n THEN PRINT(queenInRow). /*找找到一個(gè)解，打印到一個(gè)解，打印*/ ELSE NQUEENS(k+1). /*考慮下一個(gè)皇后考慮下一個(gè)皇后*/ ) )數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 57 頁(yè)頁(yè)遞歸方法雖然在解決某些問題時(shí)是最直觀、最方便的方法，但卻不是一種高效的方法，主要原因在于遞歸方法過于頻繁的函數(shù)調(diào)用和參數(shù)傳遞。在這種情況下，若采用循環(huán)或遞歸算法的非遞歸實(shí)現(xiàn)，將會(huì)大大提高算法的執(zhí)行效率。6.5 遞歸的效率遞歸的效率 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精

30、品課程精品課程第第 58 頁(yè)頁(yè)斐波那契數(shù)列的遞歸調(diào)用樹斐波那契數(shù)列的遞歸調(diào)用樹數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 59 頁(yè)頁(yè)由此可以計(jì)算出算法的復(fù)雜度為由此可以計(jì)算出算法的復(fù)雜度為O(2k)，遞歸算法的運(yùn)行時(shí)間是指數(shù)級(jí)的。遞歸算法的運(yùn)行時(shí)間是指數(shù)級(jí)的。如果我們采用簡(jiǎn)單的循環(huán)語句計(jì)算斐波如果我們采用簡(jiǎn)單的循環(huán)語句計(jì)算斐波那契數(shù)列的第那契數(shù)列的第n項(xiàng)，則算法的復(fù)雜度為項(xiàng)，則算法的復(fù)雜度為O(n)。用循環(huán)實(shí)現(xiàn)計(jì)算斐波那契數(shù)列的方法：用循環(huán)實(shí)現(xiàn)計(jì)算斐波那契數(shù)列的方法：如果如果n為為0或或1則返回則返回n值，否則用循環(huán)進(jìn)值，否則用循環(huán)進(jìn)行迭代計(jì)算。行迭代計(jì)算。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 精品課程精品課程第第 60 頁(yè)頁(yè)計(jì)算斐波