算法設計與分析實踐案例解析

楊烜，教授，博士生導師，深圳大學計算機與軟件學院教學副院長，1991年畢業於西安電子科技大學，獲學士學位，1994、1998年畢業西安交通大學獲碩士、博士學位，1998年至2001年期間在西安電子科技大學博士後流動站工作，2001年至今在深圳大學工作。主持完成科技支撐計劃項目課題一項，國家自然科學基金面上項目三項，作為參研單位主持人完成國家自然科學基金廣東省聯合基金一項，國家重點實驗室項目一項，廣東省自然科學基金一項，深圳市科技計劃項目多項。獲得總參科技進步二等獎一項，陜西省科學技術三等獎一項，陜西高等學校科學技術一等獎一項。深圳市優秀教師，獲國家教學成果二等獎一項，廣東省教學成果一等獎一項。

目錄

 

 

配套資源

第1章算法和計算思維1

1.1算法基本概念及效率分析1

1.1.1什麼是算法1

1.1.2算法設計的基本過程2

1.1.3算法效率分析的基本方法3

1.2算法與計算思維11

第2章分治法13

2.1分治法概述13

2.2分治法中的計算思維15

2.3分治法的實踐案例16

2.3.1求第k個數16

2.3.2粉刷問題21

2.3.3棋盤覆蓋問題24

2.3.4數組的反轉計數27

2.3.5天際線問題32

2.3.6凸包問題36

第3章回溯法45

3.1回溯法概述45

3.2剪枝48

3.3回溯法與尋優問題49

3.4回溯法與分支界限法50

3.5回溯法中的計算思維51

3.6回溯法的實踐案例52

3.6.1數獨問題52

3.6.2騎士巡遊問題55

3.6.3子集劃分問題58

3.6.4括號生成問題61

3.6.5地圖填色問題62

3.6.6運算表達式優先級66

第4章動態規劃68

4.1動態規劃概述68

4.2動態規劃中的計算思維71

4.3動態規劃的實踐案例72

4.3.1最長等差子序列72

4.3.2子系列和最大問題74

4.3.3股票獲益最大問題76

4.3.4圖像編碼問題80

4.3.5最長不重疊子串問題83

4.3.6粉刷問題85

4.3.7樹的最大高度問題87

4.3.8分割等和子集問題92

4.3.9跳躍問題96

4.3.10最長嚴格遞增子序列100

4.3.11回文串劃分問題102

4.3.12括號生成問題110

4.3.13作業調度問題112

第5章貪心法115

5.1貪心法概述115

5.2貪心法中的計算思維117

5.3貪心法的實踐案例117

5.3.1最少站臺問題117

5.3.2最短超級字符串121

5.3.3重排字符串問題124

5.3.4圖頂點填色問題127

5.3.5奶茶找零問題129

5.3.6將整數n變成1131

第6章圖論算法134

6.1圖論基本算法134

6.1.1圖的基本概念134

6.1.2圖的數據結構表示136

6.1.3廣度優先搜索136

6.1.4深度優先搜索138

6.1.5圖搜索算法應用140

6.1.6連通性141

6.1.7最小生成樹算法145

6.1.8最大流算法149

6.2圖論算法應用實例155

6.2.1蛇梯問題155

6.2.2橋問題157

6.2.3查找超級節點162

6.2.4二分圖匹配問題165

6.2.5點連通度和邊連通度166

6.2.6邊不相交問題170

6.2.7環流問題171

6.2.8機場調度問題174

6.2.9項目選擇問題178

6.2.10棒球比賽問題180

第7章攤還分析184

7.1攤還分析與漸進分析184

7.1.1棧操作185

7.1.2二進制計數185

7.2聚合分析186

7.2.1棧操作186

7.2.2二進制計數186

7.2.3字典187

7.3核算法188

7.3.1棧操作188

7.3.2二進制計數189

7.3.3動態表189

7.3.4234樹190

7.4勢能法192

7.4.1棧操作193

7.4.2二進制計數194

7.4.3動態表195

7.4.4234樹195

7.4.5笛卡兒樹197

參考文獻201