1、算法設(shè)計(jì)與分析 歸納法歸納法 主要內(nèi)容： 介紹遞歸算法設(shè)計(jì)的基本要素和方法。 歸納法 一. 遞歸的概念和遞歸算法設(shè)計(jì)要素1遞歸的概念 遞歸是一種十分重要的程序設(shè)計(jì)方法，對(duì)于一些問(wèn)題，用遞歸方法設(shè)計(jì)算法可使算法簡(jiǎn)潔明了，邏輯清晰，易于設(shè)計(jì)。遞歸指算法自己調(diào)用自己, 相應(yīng)的算法稱為遞歸算法。 直接遞歸與間接遞歸遞歸方法用于解決一類滿足遞歸關(guān)系的問(wèn)題。遞歸關(guān)系：對(duì)原問(wèn)題的求解可轉(zhuǎn)化為對(duì)其性質(zhì)相同 的子問(wèn)題的求解。歸納法 一. 遞歸的概念和遞歸算法設(shè)計(jì)要素1遞歸的概念例：多項(xiàng)式求值的Horner規(guī)則 （5.5 P94） Pn(x)=anxn + an-1xn-1 + a1x + a0 Horner規(guī)則

2、： Pn(x)=（anx + an-1）x + an-2）x + an-3）x+ a1）x+ a0歸納法 一. 遞歸的概念和遞歸算法設(shè)計(jì)要素1遞歸的概念 令 Pn-1(x)=anxn-1 + an-1xn-2 + a2x + a1 則根據(jù)Horner規(guī)則， Pn-1(x)=（anx + an-1）x + an-2）x + an-3）x+ a1 于是有 Pn(x)=x Pn-1(x) + a0 從而將求Pn(x)的值的問(wèn)題轉(zhuǎn)化為求Pn-1(x)的值的問(wèn)題。歸納法 一. 遞歸的概念和遞歸算法設(shè)計(jì)要素1遞歸的概念 一般的有： Pm(x) = x Pm-1(x) + an-m , m=1, 2, ,

3、n P0(x) = an 其中，Pm(x)=anxm + an-1xm-1 + an-m+1x + an-m 。 求Pn(x)的值的遞歸算法：算法 HORNERERC 求Pn(x)的值的迭代算法：算法5.6 HORNER（P95）歸納法 一. 遞歸的概念和遞歸算法設(shè)計(jì)要素1遞歸的概念遞歸算法與迭代算法遞歸算法中所蘊(yùn)含的歸納法思想歸納法 一. 遞歸的概念和遞歸算法設(shè)計(jì)要素2遞歸算法設(shè)計(jì)要素 遞歸關(guān)系（特性）：產(chǎn)生遞歸的基礎(chǔ)。 當(dāng)算法中某步驟要通過(guò)解性質(zhì)相同的子問(wèn)題實(shí)現(xiàn)時(shí)，該步驟用遞歸調(diào)用實(shí)現(xiàn)。 遞歸出口（結(jié)束條件）：確定遞歸的層數(shù)。 當(dāng)子問(wèn)題的規(guī)模充分小時(shí)可直接求解時(shí)，遞歸結(jié)束。歸納法 一. 遞

4、歸的概念和遞歸算法設(shè)計(jì)要素2遞歸算法設(shè)計(jì)要素 參數(shù)設(shè)置：參數(shù)表示了原問(wèn)題及其不同的子問(wèn)題。 參數(shù)表示了子問(wèn)題的大小和狀態(tài)，以區(qū)別原問(wèn)題以及不同層次的子問(wèn)題。算法功能的設(shè)定：嚴(yán)格規(guī)定遞歸算法要解決什么樣的問(wèn)題。 算法功能的正確設(shè)定是保證遞歸過(guò)程正確進(jìn)行的前提。 例：多項(xiàng)式求值 注意： 初始化，遞歸與循環(huán)，算法正確性的驗(yàn)證，歸納法 二.簡(jiǎn)單的遞歸算法設(shè)計(jì)之例 1選擇排序與插入排序 ( 5.2 P90 ) 設(shè)對(duì)n個(gè)數(shù)據(jù)升序排序。(1)選擇排序 基本思想： 遞歸關(guān)系：當(dāng)選出最小元素并交換到第一個(gè)位置上后， 問(wèn)題轉(zhuǎn)換為對(duì)其余元素的排序。 遞歸出口：當(dāng)只剩下一個(gè)元素時(shí)，自然有序。 參數(shù)：待排序子序列的起始

5、位置。 功能：對(duì)待排序子序列按升序選擇排序。 選擇排序遞歸算法：選擇排序算法 (P90 算法5.1) 歸納法 二.簡(jiǎn)單的遞歸算法設(shè)計(jì)之例 1選擇排序與插入排序 ( 5.2 P90 ) (2) 插入排序 基本思想： 遞歸關(guān)系：若前n-1個(gè)元素組成的子序列為有序的，則將第n個(gè)元素插入到前面的有序子序列中就可完成對(duì)n個(gè)元素的排序。問(wèn)題轉(zhuǎn)換為對(duì)前n-1個(gè)元素組成的子序列的插入排序問(wèn)題。 遞歸出口：長(zhǎng)度為1的子序列自然有序。 參數(shù)：待排序子序列的終止位置。 功能：對(duì)待排序子序列按升序插入排序。 插入排序遞歸算法：插入排序算法 (P91算法5.2) 遞歸算法中遞歸調(diào)用的位置歸納法 二.簡(jiǎn)單的遞歸算法設(shè)計(jì)之

6、例 2整數(shù)冪問(wèn)題 (5.4 P93) 問(wèn)題描述：求實(shí)數(shù)x的n次冪（n為非負(fù)整數(shù)）。遞歸關(guān)系及遞歸出口： 例：x9=x( x4)2 x4=( x2)2 參數(shù)：m, x。 算法：算法 5.4 EXPERC歸納法 三. 遞歸算法設(shè)計(jì)之例 1棋子移動(dòng)游戲 問(wèn)題描述：有2n（n=4為整數(shù)）棋子，黑白棋子各n個(gè)，初始 狀態(tài)為： _ _ （右邊有兩個(gè)空位） 終止?fàn)顟B(tài)為： _ _ （左邊有兩個(gè)空位） 將棋子從初始狀態(tài)移動(dòng)成終止?fàn)顟B(tài)。移動(dòng)規(guī)則如下： 1) 每次必須同時(shí)移動(dòng)相鄰兩個(gè)棋子； 2) 移動(dòng)方向不限； 3) 每次移動(dòng)必須跳過(guò)若干棋子。 歸納法 三. 遞歸算法設(shè)計(jì)之例 1棋子移動(dòng)游戲 遞歸關(guān)系： 當(dāng)n=5時(shí)

7、，經(jīng)過(guò)2次移動(dòng)，規(guī)模為n的問(wèn)題可轉(zhuǎn)化為規(guī)模為n-1的子問(wèn)題。 分析：棋子移動(dòng)游戲.ppt遞歸出口： n=4參數(shù)：?jiǎn)栴}規(guī)模n算法：算法 CHESS歸納法 三. 遞歸算法設(shè)計(jì)之例 2生成全排列 （5.6） 問(wèn)題描述：生成n個(gè)互異元素a1 , a2, an的全排列（所有排列）。分析： 記A為a1 , a2, an的所有排列組成的集合， Ai為A中以ai開(kāi)頭的所有排列組成的集合，i=1, 2, n, 則Ai互不相交且 A=A1UA2UUAn 記Bi為a1 , ai-1, ai+1, an的所有排列組成 的集合，i=1, 2, n, 則 Ai=Bi中的排列前加ai 歸納法 三. 遞歸算法設(shè)計(jì)之例 2生成

8、全排列 （5.6） 遞歸關(guān)系：求解n個(gè)元素的全排列問(wèn)題可轉(zhuǎn)化為求解n個(gè)n-1個(gè)元素的全排列問(wèn)題（即要求A只要求B1 , B2, Bn）。遞歸出口：求一個(gè)元素的全排列。參數(shù)：指定當(dāng)前需要求全排列的子序列的位置。算法：算法及其時(shí)間復(fù)雜性 歸納法 三. 遞歸算法設(shè)計(jì)之例 3尋找多數(shù)元素 （5.7 P98） 問(wèn)題描述：求n個(gè)元素序列中的多數(shù)元素，多數(shù)元素為在序列中出現(xiàn)的次數(shù)多于n/2的元素。 一個(gè)序列不一定存在多數(shù)元素。 一個(gè)序列的多數(shù)元素若存在則唯一。歸納法 三. 遞歸算法設(shè)計(jì)之例 3尋找多數(shù)元素 （5.7 P98） 有關(guān)方法： 蠻力方法：計(jì)數(shù)每個(gè)元素在序列中的出現(xiàn)次數(shù)。 時(shí)間復(fù)雜性：(n2)。 蠻

9、力方法是一種簡(jiǎn)單直接地解決問(wèn)題的方法，常常直接基于問(wèn)題的描述和所涉及的概念定義。 排序方法：先對(duì)序列排序，然后掃描排序結(jié)果序列，求序列中的出現(xiàn)次數(shù)最多的元素。 時(shí)間復(fù)雜性：(nlogn)。歸納法 三. 遞歸算法設(shè)計(jì)之例 3尋找多數(shù)元素 （5.7 P98） 有關(guān)方法： 求中間元素方法：先求序列的中間元素，然后判斷中間元素是否為多數(shù)元素。 時(shí)間復(fù)雜性：(n)。 中間元素為序列中的第 小元素，多數(shù)元素一定是中間元素，求中間元素的分治算法時(shí)間復(fù)雜性為(n)，但其中的常系數(shù)較大。歸納法 三. 遞歸算法設(shè)計(jì)之例 3尋找多數(shù)元素 （5.7 P98） 一種更高效的方法： 觀察結(jié)論5.1：在原序列中除去兩個(gè)不同

10、元素后，原序列中的多數(shù)元素在新序列中還是多數(shù)元素。 思考：觀察結(jié)論5.1的逆命題是否成立？ 推論：在原序列中除去多對(duì)不同元素后，原序列中的多數(shù)元素在新序列中還是多數(shù)元素。歸納法 三. 遞歸算法設(shè)計(jì)之例 3尋找多數(shù)元素 （5.7 P98） 遞歸關(guān)系： 通過(guò)對(duì)除去多對(duì)不同元素后的子序列的多數(shù)元素問(wèn)題的求解可得到原序列的多數(shù)元素問(wèn)題的候選解。 注意：子序列的多數(shù)元素只是原序列的候選多數(shù)元素，必須驗(yàn)證。但若子序列不存在多數(shù)元素，則原序列就一定不存在多數(shù)元素。 歸納法 三. 遞歸算法設(shè)計(jì)之例 3尋找多數(shù)元素 （5.7 P98） 算法的基本思想：逐個(gè)掃描序列元素，不斷除去不同的元素對(duì)，得到新的子序列，對(duì)子序列做同樣的運(yùn)算，直至序列掃描完畢。遞歸出口：序列已掃描完。參數(shù)：待掃描的子序列的起始位置。算法：尋找多數(shù)元素.doc 歸納法 遞歸算法設(shè)計(jì)