算法設計方法

算法設計方法第1章

算法設計與分析概論

1.1算法的定義和特征

1.2算法的描述

1.3算法分析

1.4遞歸方程求解

1.4.1遞歸公式的展開

1.4.2常系數(shù)線性齊次遞歸方程的特征方程求解方法

1.4.3常系數(shù)線性非齊次遞歸方程求解

1.5生成函數(shù)

1.6習題

算法設計方法第2章

分治與遞歸算法

2.1分治與遞歸算法的基本思路

2.2查找中的分治與遞歸算法

2.2.1二分查找算法

2.2.2二叉樹查找

2.2.3AVL樹

2.3排序問題的分治與遞歸算法

2.3.1合并排序

2.3.2快速排序

2.4矩陣乘法的strassen算法

2.5快速傅里葉變換

2.5.1離散傅里葉變換

2.5.2快速傅里葉變換算法

2.6減治與遞歸

2.7變治與遞歸

2.8習題

算法設計方法第3章

散列與凝聚算法

3.1散列算法

3.1.1散列查找算法

3.1.2桶排序算法

3.2矩陣乘法的凝聚算法

3.2.1非負整數(shù)矩陣乘法的凝聚算法

3.2.2矩陣乘法的凝聚算法的改進

3.2.3布爾矩陣乘法的凝聚算法

3.3非負整數(shù)向量卷積的凝聚算法

3.4習題

算法設計方法第4章

貪心算法

4.1背包問題的貪心算法

4.2求最小生成樹的Kruskal算法

4.3求最小生成樹的Prim算法

4.4求單源最短路的Dijkstra算法

4.5哈夫曼編碼

4.6習題

算法設計方法第5章

動態(tài)規(guī)劃算法

5.1多段圖問題

5.2矩陣連乘積問題

5.30.1背包問題

5.4旅行售貨員問題

5.5最長公共子序列問題

5.6流水作業(yè)調(diào)度問題

5.7資源分配問題

5.8動態(tài)規(guī)劃小結

5.9習題

算法設計方法第6章

回溯算法

6.1回溯算法的基本思想

6.2旅行售貨員問題

6.3n后問題

6.4圖的m著色問題

6.50-1背包問題

6.6批處理作業(yè)調(diào)度問題

6.7哈密爾頓回路問題

6.8子集和數(shù)問題

6.9回溯法效率分析

6.10習題

算法設計方法第7章

分支限界算法

7.1基本思想

7.20-1背包問題

7.3旅行售貨員問題

7.4任務分配問題

7.5批處理作業(yè)調(diào)度問題

7.6重排九宮問題

7.7習題

算法設計方法第8章

NP-完全問題

8.1圖靈機--可計算性和計算復雜性的度量標準

8.1.1確定的圖靈機

8.1.2圖靈機用于計算整函數(shù)

8.1.3多帶圖靈機

8.1.4不確定的圖靈機

8.1.5圖靈機的停機問題與可計算性度量

8.1.6計算復雜性的度量

8.2P類和NP類問題

8.2.1P類問題的實例

8.2.2NP類問題的實例

8.3NP完全問題與Cook定理

8.3.1多項式規(guī)約與NP完全問題的基本理論

8.3.2Cook定理

8.3.3其他NP完全問題

8.3.4CO-NP問題與NPI問題

8.4NP困難問題的近似算法和概率算法

8.4.1近似算法

8.4.2概率算法

8.5習題

2100433B

算法設計方法內(nèi)容簡介

《算法設計方法》共分為8章。第1章介紹了算法的基本概念以及算法描述和算法分析的基本知識。第2章至第7章分別論述了分治與遞歸算法、散列與凝聚算法、貪心算法、動態(tài)規(guī)劃算法、回溯算法和分支限界算法。在每一章的開頭，都先對相應的典型算法的基本思路進行詳細、清晰的闡述，然后通過多種實際問題的求解，對該典型算法的設計方法作進一步的剖析。第8章對NP完全問題的基本理論進行討論，并介紹了求解NP困難問題的近似算法和概率算法。

算法設計方法作者簡介

吳哲輝，男，教授，博士生導師，中共黨員。1941年生于廣東省連縣（現(xiàn)連州市）。1965年畢業(yè)于中山大學數(shù)學專業(yè)，1981年12月到1983年12月在美國芝加哥伊利諾大學作訪問學者?，F(xiàn)任山東科技大學信息科學與工程學院教授、博士生導師，中國科學院計算技術研究所兼職博士生導師，中國計算機學會理事，中國計算機學會petri網(wǎng)專業(yè)委員會主任。

主要研究領域有：petri網(wǎng)理論與并行分時系統(tǒng)、算法設計與分析、形式語言與自動機理論、密碼學等。先后主持承擔國家自然科學基金項目6項（從1987年到2004年，每3年1項）、山東省自然科學基金項目2項、煤炭科學基金項目2項；在《中國科學》、《科學通報》、《計算機學報》、《軟件學報》等國內(nèi)核心刊物，以及高校學報、國外刊物和國際學術會議發(fā)表學術論文90多篇，出版編、譯著3部；獲得過全國煤炭系統(tǒng)出國留學人員科研成果一等獎1項（獨立）、國家教委科技進步三等獎1項（首位）、山東省科技進步二等獎1項（1項首位，1項第二位），山東省優(yōu)秀教學成果一等獎1項（首位）、二等獎2項（均首位）。

1989年被評為全國優(yōu)秀教師；1991年被評為全國有突出貢獻的回國留學人員，并獲得國務院頒發(fā)的政府特殊津貼；1992年被評為國家有突出貢獻的中青年專家；1993年和1994年兩度被評為山東省專業(yè)技術拔尖人才；1995年被評為山東省十大優(yōu)秀教師；1998年被評為全國教育系統(tǒng)勞動模范，并被授予全國模范教師稱號和獎章。

本書簡要介紹了算法設計、分析和優(yōu)化的基礎知識，重點放在算法設計方法的學習上，通過大量的典型例題講解了常用算法設計方法（共10種）： 求值法、累加法、累乘法、遞推法、遞歸法、枚舉法、分治法、貪心法、回溯法和動態(tài)規(guī)劃法，最后通過實例給出算法設計綜合應用。每個例題從問題描述、問題分析、算法說明、算法設計、運行結果和算法優(yōu)化6個方面進行講解。

本書結合實例、內(nèi)容豐富、深入淺出、結構清晰，可以作為高等院校計算機及其相關專業(yè)本科生和研究生算法設計課程的教材，也適合IT技術人員和計算機編程愛好者學習參考。

第1章算法概述1

1.1算法與問題求解1

1.1.1算法的定義1

1.1.2問題求解2

1.2算法的要素和特性3

1.2.1算法的要素3

1.2.2算法的基本特性4

1.3算法的描述5

1.3.1基本控制結構的描述5

1.3.2C算法描述約定7

1.4算法分析9

1.4.1算法的評價標準9

1.4.2算法的時間復雜度10

1.4.3算法的空間復雜度11

1.5算法的優(yōu)化12

1.5.1全局優(yōu)化12

1.5.2局部優(yōu)化13

1.5.3算法優(yōu)化中的注意事項14第2章求值法17

2.1算法設計思想17

2.2典型例題17

2.2.1求最大值17

2.2.2求平均分19

2.2.3判斷閏年21

2.2.4素數(shù)23

2.2.5孿生數(shù)25 算法設計方法與優(yōu)化 目錄 2.2.6巧排螺旋陣27

2.2.7百燈判熄31

2.3小結33

習題233第3章累加法35

3.1算法設計思想35

3.2典型例題35

3.2.1自然數(shù)求和35

3.2.2自然數(shù)倒數(shù)求和37

3.2.3統(tǒng)計及格人數(shù)38

3.2.4計算π值41

3.2.5統(tǒng)計對稱數(shù)42

3.2.6數(shù)列求和45

3.2.7判斷天數(shù)46

3.3小結48

習題349第4章累乘法51

4.1算法設計思想51

4.2典型例題51

4.2.1求n的階乘51

4.2.2計算偶數(shù)積52

4.2.3求階乘之和54

4.2.4大整數(shù)階乘56

4.2.5國王獎賞問題58

4.2.6計算e值60

4.3小結62

習題462第5章遞推法65

5.1算法設計思想65

5.2典型例題66

5.2.1兔子繁殖問題66

5.2.2最大公約數(shù)問題68

5.2.3猴子吃桃問題70

5.2.4楊輝三角問題71

5.2.5穿越沙漠問題74

5.2.6分西瓜問題75

5.3小結77

習題577第6章遞歸法81

6.1算法設計思想81

6.2典型例題81

6.2.1母牛繁殖問題81

6.2.2輸出各位數(shù)字83

6.2.3最大值問題85

6.2.4計算x的n次冪87

6.2.5數(shù)組逆置89

6.2.6漢諾塔問題91

6.3小結93

習題693第7章枚舉法97

7.1算法設計思想97

7.2典型例題97

7.2.1百雞問題97

7.2.2水仙花數(shù)100

7.2.3完數(shù)102

7.2.4可逆素數(shù)104

7.2.5串匹配問題107

7.2.6最小公倍數(shù)問題111

7.2.7獄吏問題113

7.3小結116

習題7116第8章分治法119

8.1算法設計思想119

8.2典型例題119

8.2.1折半查找119

8.2.2金塊問題121

8.2.3尋找第二的問題124

8.2.4歸并排序127

8.2.5大整數(shù)乘法131

8.2.6二叉樹遍歷133

8.3小結138

習題8138第9章貪心法141

9.1算法設計思想141

9.2典型例題142

9.2.1找零錢問題142

9.2.2最優(yōu)裝載145

9.2.3哈夫曼編碼149

9.2.4單源最短路徑155

9.2.5埃及分數(shù)問題158

9.2.6多機調(diào)度問題162

9.3小結165

習題9166第10章回溯法169

10.1算法設計思想169

10.2典型例題170

10.2.1八皇后問題170

10.2.2圖著色問題174

10.2.3橋本分數(shù)式176

10.2.4高逐位整除數(shù)180

10.2.5直尺刻度分布問題183

10.2.6素數(shù)環(huán)問題186

10.2.7伯努利裝錯信封問題190

10.3小結194

習題10195第11章動態(tài)規(guī)劃197

11.1算法設計思想197

11.2典型例題198

11.2.1數(shù)塔問題198

11.2.2矩陣連乘問題202

11.2.3最長公共子序列問題207

11.2.4最長上升子序列問題211

11.2.5陪審團問題215

11.3小結218

習題11218第12章綜合應用223

12.1Fibonacci數(shù)列223

12.2π值求法227

12.3循環(huán)賽日程表230

12.4最大子段和問題239

12.5背包問題246

習題12256 2100433B

旋轉門算法除了平行四邊形算法之外，還能用三角形算法來表示。