《數(shù)據(jù)結(jié)構(gòu)與算法項目化教程》課件第1章

學(xué)習(xí)情境1認識數(shù)據(jù)與算法1.1任務(wù)一初識數(shù)據(jù)結(jié)構(gòu)和算法1.2任務(wù)二數(shù)據(jù)結(jié)構(gòu)1.3任務(wù)三算法

“數(shù)據(jù)結(jié)構(gòu)(datastructure)與算法(algorithm)”是計算機專業(yè)重要的專業(yè)基礎(chǔ)課程，課程的學(xué)習(xí)直接關(guān)系到后續(xù)課程的學(xué)習(xí)和軟件設(shè)計水平的提高。本學(xué)習(xí)情境介紹數(shù)據(jù)結(jié)構(gòu)與算法課程的作用以及在計算機專業(yè)課程中的地位、有關(guān)的概念、術(shù)語、算法及其描述語言和算法分析方法。1.1任務(wù)一初識數(shù)據(jù)結(jié)構(gòu)和算法數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。1.1.1子任務(wù)1什么是數(shù)據(jù)結(jié)構(gòu)和算法

1．?dāng)?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，這種關(guān)系稱為結(jié)構(gòu)，它可以是線性排列結(jié)構(gòu)，也可以是樹形結(jié)構(gòu)，還可以是圖形結(jié)構(gòu)等。從計算機學(xué)科角度看，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象(數(shù)據(jù)元素)以及它們之間的關(guān)系和運算等的學(xué)科。本教程介紹線性表、棧和隊列、串、樹和二叉樹、圖等數(shù)據(jù)結(jié)構(gòu)及基于數(shù)據(jù)結(jié)構(gòu)之上的排序和查找算法等。

2．算法算法是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機制。算法能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。解決相同問題可以有不同的算法，從而可能需要用不同的時間、空間來完成同樣的任務(wù)。一個算法的優(yōu)劣可以用空間復(fù)雜度與時間復(fù)雜度以及穩(wěn)定性來衡量。1.1.2子任務(wù)2數(shù)據(jù)結(jié)構(gòu)與算法的重要性

1．?dāng)?shù)據(jù)的組織結(jié)構(gòu)

(1)數(shù)據(jù)的邏輯結(jié)構(gòu)。一個數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。對數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。

(2)數(shù)據(jù)的存儲結(jié)構(gòu)。數(shù)據(jù)必須在計算機內(nèi)存儲，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)形式，是其在計算機內(nèi)的表示。

2．?dāng)?shù)據(jù)結(jié)構(gòu)與算法的關(guān)系數(shù)據(jù)結(jié)構(gòu)必須有在該類數(shù)據(jù)結(jié)構(gòu)上執(zhí)行的算法運算才有意義。在許多類型的程序的設(shè)計中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的設(shè)計考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗表明，系統(tǒng)實現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重地依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時候事情也會反過來，我們根據(jù)特定算法來選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。選擇了數(shù)據(jù)結(jié)構(gòu)，算法也隨之確定，數(shù)據(jù)結(jié)構(gòu)是系統(tǒng)構(gòu)造的關(guān)鍵因素，好的數(shù)據(jù)結(jié)構(gòu)是算法的重要基礎(chǔ)。這導(dǎo)致了許多種軟件設(shè)計方法和程序設(shè)計語言的出現(xiàn)，面向?qū)ο蟮某绦蛟O(shè)計語言就是其中之一。

3．?dāng)?shù)據(jù)結(jié)構(gòu)與算法是程序設(shè)計的基礎(chǔ)計算機信息的表示和組織直接關(guān)系到處理信息的程序的效率。隨著計算機的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)與算法這門課程所要研究的問題。眾所周知，計算機的程序往往要對信息進行加工處理。這些信息需要很好組織，使信息(數(shù)據(jù))之間具有良好的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。數(shù)據(jù)的結(jié)構(gòu)與算法直接影響著程序設(shè)計效率和質(zhì)量。1.1.3子任務(wù)3數(shù)據(jù)結(jié)構(gòu)與算法課程

1．?dāng)?shù)據(jù)結(jié)構(gòu)課程及其歷史“數(shù)據(jù)結(jié)構(gòu)”作為一門獨立的課程在國外是從1968年才開始設(shè)立的。1968年美國克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計算機程序設(shè)計技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。

2．?dāng)?shù)據(jù)結(jié)構(gòu)與算法課程的地位數(shù)據(jù)結(jié)構(gòu)與算法課程是計算機學(xué)科中一門綜合性的專業(yè)基礎(chǔ)課。它是介于數(shù)學(xué)、計算機硬件和計算機軟件三者之間的一門核心課程，不僅是一般程序設(shè)計(特別是非數(shù)值性程序設(shè)計)的基礎(chǔ)，而且是設(shè)計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。1.2任務(wù)二數(shù)據(jù)結(jié)構(gòu)1.2.1子任務(wù)1數(shù)據(jù)的處理

1．計算機如何解決問題計算機解決一個具體問題時，大致需要經(jīng)過下列幾個步驟：

(1)從具體問題中抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型。

(2)設(shè)計一個求解此數(shù)學(xué)模型的算法。

(3)編出程序，進行測試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實質(zhì)是分析問題，從中提取操作的數(shù)據(jù)對象，并找出這些操作對象之間含有的關(guān)系，然后用數(shù)學(xué)的語言加以描述。計算機算法與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān)，算法無不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率。運算由計算機來完成，這就要設(shè)計相應(yīng)的插入、刪除和修改的算法。也就是說，數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種運算的算法。

2．?dāng)?shù)據(jù)相關(guān)術(shù)語

(1)數(shù)據(jù)。數(shù)據(jù)是對客觀事物的符號表示，在計算機科學(xué)中是指所有能輸入到計算機中并由計算機程序處理的符號的總稱。

(2)數(shù)據(jù)元素。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體考慮。一個數(shù)據(jù)元素由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。有兩類數(shù)據(jù)元素：一類是不可分割的原子型數(shù)據(jù)元素，如整數(shù)“8”，字符“N”等；另一類是由多項構(gòu)成的數(shù)據(jù)元素，其中每一項被稱為一個數(shù)據(jù)項。例如描述一個學(xué)生的信息的數(shù)據(jù)元素可由下列6個數(shù)據(jù)項組成。其中的出生日期又可以由三個數(shù)據(jù)項：“年”、“月”和“日”組成，則稱“出生日期”為組合項，而其他不可分割的數(shù)據(jù)項為原子項。

(3)關(guān)鍵字。關(guān)鍵字指的是能識別一個或多個數(shù)據(jù)元素的數(shù)據(jù)項。若能起唯一識別作用，則稱之為主關(guān)鍵字，否則稱之為次關(guān)鍵字。

(4)數(shù)據(jù)對象。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)對象可以是有限的，也可以是無限的。

(5)數(shù)據(jù)處理。數(shù)據(jù)處理是指對數(shù)據(jù)進行查找、插入、刪除、合并、排序、統(tǒng)計以及簡單計算等操作的過程。在早期，計算機主要用于科學(xué)和工程計算，進入20世紀(jì)80年代以后，計算機主要用于數(shù)據(jù)處理。據(jù)有關(guān)統(tǒng)計資料表明，現(xiàn)在計算機用于數(shù)據(jù)處理的時間比例超過80%，隨著時間的推移和計算機應(yīng)用的進一步普及，計算機用于數(shù)據(jù)處理的時間比例必將進一步增大。1.2.2子任務(wù)2數(shù)據(jù)結(jié)構(gòu)的分類

1．?dāng)?shù)據(jù)的組織結(jié)構(gòu)數(shù)據(jù)的組織結(jié)構(gòu)分別為邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)(物理結(jié)構(gòu))和數(shù)據(jù)的運算。數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)之間關(guān)系的描述，有時就把邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。

2．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素相互之間的邏輯關(guān)系稱為邏輯結(jié)構(gòu)。有四類基本邏輯結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)(網(wǎng)狀結(jié)構(gòu))。樹形結(jié)構(gòu)和圖形結(jié)構(gòu)全部稱為非線性結(jié)構(gòu)。不同結(jié)構(gòu)中數(shù)據(jù)之間的關(guān)系：

(1)集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其他關(guān)系。

(2)線性結(jié)構(gòu)中元素之間存在一對一關(guān)系。

(3)樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系。

(4)圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。在圖形結(jié)構(gòu)中，每個節(jié)點的前驅(qū)節(jié)點數(shù)和后續(xù)節(jié)點數(shù)可以任意多個。

3．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(映像)稱為數(shù)據(jù)的存儲(物理)結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法：順序映像和非順序映像，并由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，與之對應(yīng)，也有四種存儲方法。

(1)順序存儲方法：它是把邏輯上相鄰的節(jié)點存儲在物理位置相鄰的存儲單元里，節(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)是一種最基本的存儲表示方法，通常借助于程序設(shè)計語言中的數(shù)組來實現(xiàn)。

(2)鏈接存儲方法：它不要求邏輯上相鄰的節(jié)點在物理位置上亦相鄰，節(jié)點間的邏輯關(guān)系是由附加的引用(指針)表示的，由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。鏈?zhǔn)酱鎯Y(jié)構(gòu)通常借助于程序設(shè)計語言中的引用(指針)類型來實現(xiàn)。

(3)索引存儲方法：除建立存儲節(jié)點信息外，還建立附加的索引表來標(biāo)識節(jié)點的地址。

(4)散列存儲方法：就是根據(jù)節(jié)點的關(guān)鍵字直接計算出該節(jié)點的存儲地址。1.2.3子任務(wù)3常用的數(shù)據(jù)結(jié)構(gòu)

1．?dāng)?shù)組(Array)在程序設(shè)計中，為了處理方便，把具有相同類型的若干變量按有序的形式組織起來。這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組。在Ｃ語言中，數(shù)組屬于構(gòu)造數(shù)據(jù)類型。一個數(shù)組可以分解為多個數(shù)組元素，這些數(shù)組元素可以是基本數(shù)據(jù)類型或是構(gòu)造類型。因此按數(shù)組元素的類型不同，數(shù)組又可分為數(shù)值數(shù)組、字符數(shù)組、對象數(shù)組等各種類別。數(shù)組結(jié)構(gòu)如圖1-1所示。圖1-1數(shù)組結(jié)構(gòu)

2．棧(Stack)棧是只能在某一端插入和刪除數(shù)據(jù)的特殊線性表。它按照后進先出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后進入的數(shù)據(jù)在棧頂。需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)，最后一個數(shù)據(jù)被第一個讀出來，即后進先出，如圖1-2所示。具體請參閱學(xué)習(xí)情境3。圖1-2棧的結(jié)構(gòu)

3．隊列(Queue)隊列是一種特殊的線性表，它只允許在表的前端(front)進行刪除操作，而在表的后端(rear)進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。隊列是一種先進先出的結(jié)構(gòu)，其結(jié)構(gòu)如圖1-3所示。具體請參閱學(xué)習(xí)情境3。

4．鏈表(LinkedList)鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的引用(指針)鏈接次序?qū)崿F(xiàn)的。鏈表由一系列節(jié)點(鏈表中每一個元素稱為節(jié)點)組成，節(jié)點可以在運行時動態(tài)生成。每個節(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個節(jié)點地址的引用(指針)域，其結(jié)構(gòu)如圖1-4所示。具體請參閱學(xué)習(xí)情境2。圖1-3隊列的結(jié)構(gòu)圖1-4鏈?zhǔn)浇Y(jié)構(gòu)

5．樹(Tree)樹是包含n(n>0)個節(jié)點的有窮集合K，且在K中定義了一個關(guān)系N，N滿足以下條件：

(1)有且僅有一個節(jié)點K0，它對于關(guān)系N來說沒有前驅(qū)，稱K0為樹的根節(jié)點，簡稱為根(root)。

(2)除K0外，K中的每個節(jié)點，對于關(guān)系N來說有且僅有一個前驅(qū)。

(3)?K中各節(jié)點，對關(guān)系N來說可以有m個后繼(m≥0)。樹的結(jié)構(gòu)如圖1-5所示，具體請參閱學(xué)習(xí)情境5。圖1-5樹的結(jié)構(gòu)

6．圖(Graph)圖是由節(jié)點的有窮集合V和邊的集合E組成的。其中，為了與樹形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常常將節(jié)點稱為頂點，邊是頂點的有序偶對，若兩個頂點之間存在一條邊，就表示這兩個頂點具有相鄰關(guān)系，其結(jié)構(gòu)如圖1-6所示。具體請參閱學(xué)習(xí)情境6。

7．堆(Heap)在計算機科學(xué)中，堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，每個節(jié)點都有一個值。通常我們所說的堆的數(shù)據(jù)結(jié)構(gòu)是指二叉堆。堆的特點是根節(jié)點的值最小(或最大)，且根節(jié)點的兩個子樹也是一個堆。具體請參閱學(xué)習(xí)情境7中的二叉排序樹。圖1-6圖的結(jié)構(gòu)

8．散列表(Hash)若結(jié)構(gòu)中存在關(guān)鍵字和K相等的記錄，則必定在f(K)的存儲位置上。由此，不需比較便可直接取得所查記錄。這個對應(yīng)關(guān)系f稱為散列函數(shù)(Hashfunction)，按這個思想建立的表為散列表。具體請參閱學(xué)習(xí)情境8。1.3任務(wù)三算法1.3.1子任務(wù)1認識算法1．算法的歷史“算法”即演算法，中文名稱出自《周髀算經(jīng)》，而英文名稱Algorithm來自于9世紀(jì)波斯數(shù)學(xué)家al-Khwarizmi，因為al-Khwarizmi在數(shù)學(xué)上提出了算法這個概念?！八惴ā痹瓰椤癮lgorism”，意思是阿拉伯?dāng)?shù)字的運算法則，在18世紀(jì)演變?yōu)椤癮lgorithm”。歐幾里得算法被人們認為是史上第一個算法。人類歷史上第一次編寫的程序是AdaByron于1842年為巴貝奇分析機編寫的求解伯努利方程的程序，因此AdaByron被大多數(shù)人認為是世界上第一位程序員。因為查爾斯·巴貝奇(CharlesBabbage)未能完成他的巴貝奇分析機，所以這個算法也未能在巴貝奇分析機上執(zhí)行。因為“well-definedprocedure”缺少數(shù)學(xué)上精確的定義，故19世紀(jì)和20世紀(jì)早期的數(shù)學(xué)家、邏輯學(xué)家在定義算法上出現(xiàn)了困難。20世紀(jì)的英國數(shù)學(xué)家圖靈提出了著名的圖靈論題，并提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。圖靈機的出現(xiàn)解決了算法定義的難題，圖靈的思想對算法的發(fā)展起到了重要作用。

2．算法分類

1)算法涉及范圍算法可包括：基本算法、數(shù)據(jù)結(jié)構(gòu)的算法、數(shù)論與代數(shù)算法、計算幾何的算法、圖論的算法、動態(tài)規(guī)劃以及數(shù)值分析、加密算法、排序算法、檢索算法、隨機化算法、并行算法。

2)算法分類

(1)有限的確定性算法：這類算法在有限的一段時間內(nèi)終止。它們可能要花很長時間來執(zhí)行指定的任務(wù)，但仍將在一定的時間內(nèi)終止。這類算法得出的結(jié)果常取決于輸入值。

(2)有限的非確定算法：這類算法在有限的時間內(nèi)終止。然而，對于一個(或一些)給定的數(shù)值，算法的結(jié)果并不是唯一的或確定的。

(3)無限的算法：那些由于沒有定義終止定義條件，或定義的條件無法由輸入的數(shù)據(jù)滿足而不能終止運行的算法。通常，無限算法的產(chǎn)生是由于未能確定的定義終止條件，本教程不討論這類算法。

3．經(jīng)典算法與著作經(jīng)典的算法有很多，如歐幾里德算法、割圓術(shù)、秦九韶算法。有許多論述算法的書籍，其中最著名的便是高德納(DonaldE.Knuth)的《計算機程序設(shè)計藝術(shù)》(TheArtOfComputerProgramming)，科曼(CormenT.H.)的《算法導(dǎo)論》(IntroductiontoAlgorithms)。1.3.2子任務(wù)2算法的重要特征算法可以使用自然語言(中文、英文或其他語言)、偽代碼、流程圖等多種不同的方法來描述。一個算法應(yīng)該具有以下五個重要的特征。

(1)有窮性：算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止。

(2)確切性：算法的每一步驟必須有確切的定義。

(3)輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定出了初始條件。

(4)輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的。

(5)可行性：算法中執(zhí)行的任何計算步驟都是可以被分解為基本的可執(zhí)行的操作步驟，即每個計算步驟都可以在有限時間內(nèi)完成。計算機科學(xué)家尼克勞斯-沃思曾著過一本著名的《數(shù)據(jù)結(jié)構(gòu)?+?算法?=?程序》，由此可見算法在計算機科學(xué)界與計算機應(yīng)用界的地位。1.3.3子任務(wù)3算法分析

1．算法的復(fù)雜度同一問題可用不同的算法解決，而一個算法的復(fù)雜度將影響到算法乃至程序的效率。算法復(fù)雜度的分析目的在于選擇合適算法和改進算法。

2．時間復(fù)雜度算法的時間復(fù)雜度是指執(zhí)行算法所需要的時間。一般來說，計算機算法的時間復(fù)雜度是問題規(guī)模n的函數(shù)f(n)，通常記作：

T(n)?=?Ο(f(n))

O(f(n))給出了函數(shù)的復(fù)雜度的量級。因此，隨著問題的規(guī)模n的增加，算法執(zhí)行的時間的增長率與f(n)的增長率成正比，稱做漸進時間復(fù)雜度(AsymptoticTimeComplexity)。

3．空間復(fù)雜度算法的空間復(fù)雜度是指算法需要消耗的內(nèi)存空間。與時間復(fù)雜度類似，空間復(fù)雜度是指算法在計算機內(nèi)執(zhí)行時所需存儲空間的度量，記作：

S(n)?=?O(f(n))一般所討論的空間復(fù)雜度是除正常占用內(nèi)存開銷外的輔助存儲單元規(guī)模。與時間復(fù)雜度一樣，一般都用復(fù)雜度的漸進性來表示。同時間復(fù)雜度相比，空間復(fù)雜度的分析要簡單得多。1.3.4子任務(wù)4算法設(shè)計方法算法設(shè)計有多種方法，本子任務(wù)簡要介紹常見的算法。

1．遞推法遞推法是利用問題本身所具有的一種遞推關(guān)系求解問題的一種方法。它把問題分成若干步，找出相鄰幾步的關(guān)系，從而達到目的，此方法稱為遞推法。

2．遞歸遞歸指的是一個過程：函數(shù)不斷引用自身，直到引用的對象已知。

3．窮舉搜索法窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，并從中找出符合要求的候選解作為問題的解。

4．貪婪法貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不需回溯。

5．分治法分治法是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單地直接求解，原問題的解即子問題的解的合并。

6．動態(tài)規(guī)劃法動態(tài)規(guī)劃是一種在數(shù)學(xué)和計算機科學(xué)中使用的，用于求解包含重疊子問題的最優(yōu)化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。動態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計算機科學(xué)和工程領(lǐng)域。

7．迭代法迭代法是數(shù)值分析中通過從一個初始估計出發(fā)尋找一系列近似解來解決問題(一般是解方程或者方程組)的過程，為實現(xiàn)這一過程所使用的方法統(tǒng)稱為迭代法。1.3.5子任務(wù)5遞歸算法及案例

1．遞歸算法遞歸(recursion)：用一個概念本身直接或間接地定義它自己。遞歸是數(shù)學(xué)中一種重要的概念定義方式，遞歸算法是軟件設(shè)計中求解遞歸問題的方法，在后續(xù)的結(jié)構(gòu)定義和程序?qū)崿F(xiàn)中有不少地方要用到遞歸算法，對這一方法應(yīng)盡早領(lǐng)會和使用。

2．案例1階乘算法階乘函數(shù)f(n)=n!

(1)非遞歸算法程序。由于n!?=?1?×?2?×?…?×?i?×?…?×?(n?-?1)?×?n，因此程序?qū)崿F(xiàn)可以使用一個變量i從1開始連乘至n即可，算法較為簡單，不具體描述，下面是階乘非遞歸算法的完整程序代碼：importjava.util.Scanner;//階乘的非遞歸實現(xiàn)publicclassFactorial{publicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);intproduct=1;System.out.print("\n階乘非遞歸實現(xiàn)\n請輸入N=");intnumber=scan.nextInt();for(inti=2;i<=number;i++){product=product*i;}System.out.println(number+"!="+product);}}

(2)遞歸算法程序。由于n階乘也可以表示為

n!?=?1?×?2?×?…?×?i?×?…?×?(n?-?1)?×?n?=?((n?-?1)!)?×?n?=?n?×?(n?-?1)!而(n-1)!?與n!?類似，但規(guī)模小些，因此可以把n!?分解為n和一個相同結(jié)構(gòu)的子模型(n-1)!,可以以此類推，最后1!=1，這一思想就是遞歸算法。按照遞歸定義將問題簡單化為已知值，逐步遞推直到獲得一個確定值。設(shè)f(n)=n!，遞歸通式是f(n)=n*f(n-1)，將f(n)遞推到f(n-1)，算法不變，最終遞推到f(1)=1獲得確定值，遞歸結(jié)束。階乘遞歸算法的完整程序代碼如下：

importjava.util.Scanner;

//階乘的遞歸實現(xiàn)

publicclassFactorialRecursion{

publicstaticintFactorial(intnumber){

if(number<=1){

return1;

}else{

returnnumber*Factorial(number-1);

}

}

publicstaticvoidmain(String[]args){

System.out.print("\n階乘遞歸實現(xiàn)\n請輸入N=");

Scannerscan=newScanner(System.in);

intnumber=scan.nextInt();

System.out.println(Factorial(number));

}

}運行結(jié)果如下：階乘遞歸實現(xiàn)請輸入N=6

720

3．遞歸條件遞歸定義必須滿足以下兩個條件：

(1)至少有一條初始定義是非遞歸的，如1！=1。

(2)由已知函數(shù)值逐步遞推計算出未知函數(shù)值，如用(n-1)!定義n!。遞歸定義也用于定義數(shù)據(jù)結(jié)構(gòu)。階乘算法有兩種算法，當(dāng)然還有其他算法，僅從階乘的非遞歸算法程序和遞歸算法程序來看，似乎非遞歸算法程序稍為簡單一點，但有的問題使用遞歸算法非常方便。

4．漢諾塔及程序?qū)崿F(xiàn)漢諾塔(Hanoi)問題是源于印度一個古老傳說：在印度被稱為世界中心的貝拿勒斯(在印度北部)的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上疊放由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天的原始那根針上移到另外一根針上時，世界就將在一聲霹靂中消亡，而梵塔、廟宇和眾生也都將同歸于盡。漢諾塔(Hanoi)模型如圖1-7所示，移動規(guī)則是：①在三根柱子之間一次只能移動一個圓盤；②大圓盤不能壓放在小圓盤上。目標(biāo)是將所有圓盤從X柱移到Z柱。圖1-7漢諾塔初始狀態(tài)

(1)漢諾塔問題分析。如果考慮把64片金片由一根針上移到另一根針上，并且始終保持上小下大的順序，這需要多少次移動呢?假設(shè)有n片，且移動次數(shù)是f(n)，這里移動次數(shù)取最小值，也就是不做無用的移動。只有一片，直接移到目標(biāo)柱，顯然f(1)=1；有兩片，很容易移動并算出f(2)=3；有三片，也不難算法f(3)=7；有四片、五片，似乎有點亂了……注意到f(1)=1=21-1，f(2)=3=22-1，f(3)=7=23-1……這個猜想是否正確呢？如果有四片，可以看成最底下的一片加最上面三片，考慮移動：①將最上面的三片從X移到Y(jié)柱，次數(shù)為f(3)=7；②將最下面一片從X移到Z柱，次數(shù)為1；③將Y柱中的三片從Y移到Z柱，次數(shù)為f(3)=7，完成任務(wù)。所以移動四片的次數(shù)：f(4)=f(3)+1+f(3)=7+1+7=15=24-1。四片的算法可用于五片、六片……，所以n片移動次數(shù)：f(n)=2n-1。

(2)漢諾塔遞歸算法。其實在計算移動次數(shù)時，已經(jīng)使用了遞歸算法，從上述分析很容易得到漢諾塔遞歸算法。將n片漢諾塔分成n和n-1，如圖1-8所示。漢諾塔遞歸算法的中文描述如下：如果只有1個盤，欲將n從X移到Z，則：①n-1從X移到Y(jié)(Z做中間柱)，如圖1-9所示；②n從X移到Z(直接移動)，如圖1-10所示；③n-1從Y移到Z(X做中間柱)，如圖1-11所示。圖1-8n片漢諾塔分成n和n-1圖1-9n-1從X移到Y(jié)圖1-10n從X移到Z圖1-11n-1從Y移到Z將中文描述翻譯成英語描述如下：

ifn=1move(n,x,z)

else

han(n-1,x(z)toy)

move(n,x,z)

han(n-1,y(x)toz)

end再用程序設(shè)計語言來表達，代碼如下(C語言和Java語言在此時算法正好一樣)：

if(n==1{

move(n,x,z);

}else{

hanoi(n-1,x,z,y);

move(n,x,z);

hanoi(n-1,y,x,z);

}算法清楚了，程序表達也完成了，最后還要在計算機上編寫可運行代碼，以查看和驗證。

(3)漢諾塔遞歸實現(xiàn)的完整代碼如下：

importjava.util.Scanner;

publicclasshanoi{

privatestaticStringx="X柱";

privatestaticStringy="Y柱";

privatestaticStringz="Z柱";

privatestaticinti=1;

publicstaticvoidmain(String[]args){

System.out.print("\n漢諾塔遞歸實現(xiàn)\n請輸入盤子個數(shù):n=");

Scannerscan=newScanner(System.in);

intn=scan.nextInt();

hanoiH=newhanoi();

H.hanoi(n,x,y,z);

}

publicstaticvoidhanoi(intn,Stringx,Stringy,Stringz){

if(n==1){

move(n,x,z);

}else{

hanoi(n-1,x,z,y);

m