算法設計與分析（微課版 附動畫視頻）

王紅梅：

長春工業大學教授，全國優秀教師，吉林省高等學校教學名師，吉林省五一巾幗標兵；國家級一流本科專業建設點負責人，國家級一流本科課程負責人；主編教育部精品教材1部、“十一五”國家級規劃教材1部、“十二五”國家級規劃教材4部，獲吉林省高等教育教學成果獎6項；主持省級科研項目5項、橫向課題6項，參與國家自然科學基金項目1項、省級科研項目5項；發表學術論文30余篇，其中SClI/EI檢索24篇。

【章名目錄】

第 一篇 基礎知識

第 1章　緒論

第 2章　工之利器——編程珠璣

第二篇 基本的算法設計技術

第3章　按圖索驥——模擬法

第4章　數學歸納——遞推法

第5章　愚公移山——蠻力法

第6章　分而治之——分治法

第7章　分而治一——減治法

第8章　急功近利——貪心法

第9章　表格收納——動態規劃法

第三篇 基礎搜索的算法設計技術

第 10章　深度優先搜索

第 11章　廣度優先搜索

第四篇 NP類問題及求解方法

第 12章　給問題分類——問題的復雜性

 

【詳細目錄】

第 一篇 基礎知識

第 1章　緒論 2

1.1　引言 2

1.1.1　引例——美妙的節奏 3

1.1.2　引例——數組循環左移問題 3

1.1.3　用計算機求解問題的一般過程 5

1.2　為什麼要學習和研究算法 5

1.2.1　算法研究推動計算機技術發展 5

1.2.2　算法訓練提高計算思維能力 6

1.2.3　程序員必須學習算法嗎 6

1.3　算法及其描述方法 7

1.3.1　什麼是算法 7

1.3.2　什麼是好算法 8

1.3.3　算法的描述方法 9

1.4　算法的時間復雜度 11

1.4.1　輸入規模與基本語句 11

1.4.2　算法的漸近時間 13

1.4.3　最好、最壞和平均情況 13

1.5　算法的空間復雜度 15

1.6　拓展與演練 15

1.6.1　角谷猜想 15

1.6.2　算法的實驗分析 16

習題 17

 

第 2章　工之利器——編程珠璣 19

2.1　程序設計基礎 19

2.1.1　數據類型與變量 20

2.1.2　控制結構 22

2.1.3　自定義函數 24

2.2　程序設計技巧 26

2.2.1　優化代碼的技巧 26

2.2.2　表示狀態的技巧——標誌變量 28

2.2.3　掃描數組的技巧——尺取法 29

2.3　遞歸簡論 31

2.3.1　遞歸的基本法則 31

2.3.2　遞歸函數的性能分析 33

2.4　數據結構簡論 35

2.4.1　數據結構的基本概念 35

2.4.2　基本的數據結構 35

2.4.3　數據結構的存儲表示 37

2.5　拓展與演練 38

2.5.1　遞歸函數求數組最大值 38

2.5.2　合並數組 39

習題 39

 

第二篇 基本的算法設計技術

第3章　按圖索驥——模擬法 42

3.1　引言 42

3.1.1　模擬法的設計思想 43

3.1.2　引例——雞兔同籠問題 43

3.2　數學問題中的模擬法 43

3.2.1　約瑟夫環問題 43

3.2.2　埃拉托色尼篩法 45

3.3　排序問題中的模擬法 46

3.3.1　顏色排序 46

3.3.2　計數排序 48

3.4　拓展與演練 50

3.4.1　裝箱問題 50

3.4.2　數字回轉方陣 51

實驗　優化埃氏篩法 52

習題 52

第4章　數學歸納——遞推法 54

4.1　引言 54

4.1.1　遞推法的設計思想 54

4.1.2　引例——猴子吃桃 55

4.2　數學問題中的遞推法 55

4.2.1　Fibonacci數列 55

4.2.2　Catalan數列 56

4.3　組合問題中的遞推法 58

4.3.1　伯努利錯裝信封問題 58

4.3.2　旋轉的萬花筒 59

4.4　拓展與演練 60

4.4.1　整數劃分 60

4.4.2　捕魚知多少 61

實驗　楊輝三角形 62

習題 63

第5章　愚公移山——蠻力法 64

5.1　引言 64

5.1.1　蠻力法的設計思想 64

5.1.2　引例——百錢買百雞問題 65

5.2　查找問題中的蠻力法 66

5.2.1　順序查找 66

5.2.2　串匹配問題 67

5.3　排序問題中的蠻力法 71

5.3.1　選擇排序 71

5.3.2　起泡排序 72

5.4　圖問題中的蠻力法 73

5.4.1　哈密頓回路 73

5.4.2　TSP 74

5.5　幾何問題中的蠻力法 75

5.5.1　最近對問題 75

5.5.2　凸包問題 76

5.6　拓展與演練 78

5.6.1　KMP算法計算next值 78

5.6.2　0/1背包問題 79

實驗　任務分配問題 80

習題 81

第6章　分而治之——分治法 82

6.1　引言 82

6.1.1　分治法的設計思想 83

6.1.2　引例——漢諾塔問題 83

6.2　排序問題中的分治法 84

6.2.1　歸並排序 84

6.2.2　快速排序 86

6.3　組合問題中的分治法 89

6.3.1　最大子段和問題 89

6.3.2　棋盤覆蓋問題 91

6.4　幾何問題中的分治法 93

6.4.1　最近對問題 93

6.4.2　凸包問題 95

6.5　拓展與演練 97

6.5.1　擴展歐幾裏得算法 97

6.5.2　中國剩余定理 98

實驗　Karatsuba乘法 99

習題 100

第7章　分而治一——減治法 101

7.1　引言 101

7.1.1　減治法的設計思想 101

7.1.2　引例——俄式乘法 102

7.2　查找問題中的減治法 102

7.2.1　折半查找 102

7.2.2　選擇問題 104

7.3　排序問題中的減治法 106

7.3.1　插入排序 106

7.3.2　堆排序 108

7.4　組合問題中的減治法 110

7.4.1　淘汰賽冠軍問題 110

7.4.2　假幣問題 111

7.5　拓展與演練 112

7.5.1　兩個序列的中位數 112

7.5.2　topK問題 114

實驗　假幣問題的復雜版本 116

習題 117

第8章　急功近利——貪心法 119

8.1　引言 119

8.1.1　貪心法的設計思想 119

8.1.2　引例——付款問題 120

8.2　數學問題中的貪心法 121

8.2.1　刪數問題 121

8.2.2　埃及分數 122

8.3　圖問題中的貪心法 123

8.3.1　TSP 123

8.3.2　圖著色問題 125

8.4　組合問題中的貪心法 127

8.4.1　背包問題 127

8.4.2　活動安排問題 128

8.5　拓展與演練 130

8.5.1　田忌賽馬 130

8.5.2　多機調度問題 132

實驗　合並字符串 134

習題 134

第9章　表格收納——動態規劃法 136

9.1　引言 136

9.1.1　多階段決策過程 137

9.1.2　動態規劃法的設計思想 137

9.1.3　引例——網格上的最短路徑 138

9.2　組合問題中的動態規劃法 140

9.2.1　最長公共子序列問題 140

9.2.2　0/1背包問題 142

9.3　圖問題中的動態規劃法 144

9.3.1　多段圖的最短路徑 144

9.3.2　TSP 146

9.4　查找問題中的動態規劃法 147

9.4.1　近似串匹配問題 147

9.4.2　最優二叉查找樹 150

9.5　拓展與演練 152

9.5.1　最優性原理 152

9.5.2　數塔問題 153

實驗　最大子段和問題 155

習題 155

 

第三篇 基礎搜索的算法設計技術

第 10章　深度優先搜索 158

10.1　縱深推進——深度優先搜索 158

10.1.1　深度優先搜索的設計思想 159

10.1.2　山洞尋寶 159

10.1.3　城堡問題 160

10.2　及時止損——回溯法 162

10.2.1　問題的解空間樹 162

10.2.2　回溯法的設計思想 162

10.2.3　素數環問題 163

10.2.4　八皇後問題 165

10.2.5　圖著色問題 167

10.3　拓展與演練 169

10.3.1　批處理作業調度 169

10.3.2　哈密頓回路 171

實驗　0/1背包問題 173

習題 174

第 11章　廣度優先搜索 176

11.1　由近及遠——廣度優先搜索 176

11.1.1　廣度優先搜索的設計思想 177

11.1.2　農夫抓牛 178

11.1.3　騎士旅行 179

11.2　向最優解前進——A*算法 181

11.2.1　A*算法的設計思想 181

11.2.2　八數碼問題 182

11.2.3　多段圖的最短路徑 183

11.3　丟掉包袱——限界剪枝法 184

11.3.1　限界剪枝法的設計思想 184

11.3.2　0/1背包問題 185

11.3.3　TSP 186

11.4　拓展與演練 188

11.4.1　任務分配問題 188

11.4.2　限界剪枝法的關鍵問題 189

實驗　電路布線問題 189

習題 190

 

第四篇 NP類問題及求解方法

第 12章　給問題分類——問題的復雜性 192

12.1　問題的復雜性分類 192

12.1.1　什麼是計算 193

12.1.2　可計算問題與不可計算問題 195

12.1.3　易解問題與難解問題 196

12.2　P類問題與NP類問題 197

12.2.1　判定問題 197

12.2.2　確定性算法與P類問題 198

12.2.3　非確定性算法與NP類問題 198

12.3　NP完全問題 199

12.3.1　問題歸約 199

12.3.2　NP完全問題的定義 200

12.3.3　基本的NP完全問題 200

12.4　NP類問題的求解方法 201

12.4.1　近似算法 201

12.4.2　隨機算法 203

12.5　拓展與演練 204

12.5.1　頂點覆蓋問題 204

12.5.2　素數測試 205

實驗　SAT問題 206

習題 206

 

參考文獻 208