算法設計與問題求解（微課版）

《算法設計與問題求解（微課版）》是清華大學出版社於2022年出版的圖書，作者是鄧澤林、李峰

基本介紹

• 中文名：算法設計與問題求解（微課版）
• 作者：李峰、鄧澤林
• 出版社：清華大學出版社
• 出版時間：2022年8月1日
• 定價：54 元
• ISBN：9787302613695

內容簡介

本書是為以算法設計、問題求解為閱讀目的的讀者編寫的教材，注重培養讀者的算法設計與分析、問題求解的能力。本書讀者需要掌握程式設計、數據結構等基礎知識，並具備一定的編程能力。 本書以算法設計與分析為主線，通過問題和案例引入內容，重點講解利用算法求解問題的思路、算法執行過程及能力拓展。本書主要內容為算法基礎、蠻力法、遞歸法、分治法、貪心法、回溯法、分支限界法、動態規劃法、圖算法、隨機算法等，講解了背包問題、任務分配問題、批處理作業調度問題、**裝載問題、旅行商問題、計算幾何等經典問題，並提供了能力拓展環節，引導讀者開展算法套用實踐。算法使用C語言程式、偽代碼等形式加以描述，並用圖解的形式詳細描述算法的執行過程，使讀者能夠深入了解算法的運行過程和結果。

目錄

第1章算法基礎1

1.1算法概念1

1.2算法描述1

1.3算法主要類別及典型問題2

1.3.1遞歸法2

1.3.2遞推法2

1.3.3窮舉法3

1.3.4貪心算法3

1.3.5分治法4

1.3.6動態規劃法4

1.3.7分支限界法5

1.3.8回溯法6

1.4算法複雜度6

1.4.1算法輸入規模度量6

1.4.2算法運行時間的度量7

1.4.3漸進符號7

1.4.4算法複雜度分析8

1.5標準模板庫13

1.5.1動態數組vector的使用13

1.5.2集合set的使用15

1.5.3映射map的使用17

1.5.4棧stack的使用19

1.5.5佇列與優先佇列的使用20

1.5.6排序sort的使用23

習題25

第2章遞歸算法設計26

2.1概述26算法設計與問題求解（微課版）目錄2.2遞歸算法設計思想27

2.2.1遞歸定義27

2.2.2遞歸套用28

2.3遞歸算法示例與過程分析30

2.3.1漢諾塔問題30

2.3.2逆波蘭表達式33

2.4遞歸轉化為非遞歸34

2.4.1遞歸轉尾遞歸34

2.4.2遞歸轉非遞歸36

2.5能力拓展38

2.5.1K數列38

2.5.2猴子爬樹40

2.5.3分黑球41

習題43

第3章蠻力法46

3.1概述46

3.2蠻力法的主要設計思想46

3.2.1使用蠻力法的幾種情況46

3.2.2蠻力法的求解步驟46

3.3蠻力法示例與分析47

3.3.1選擇排序47

3.3.2旅行商問題48

3.3.3字元串匹配蠻力解決50

3.3.401背包問題52

3.4能力拓展53

3.4.1連續數和53

3.4.2矩形個數54

習題56

第4章分治法59

4.1概述59

4.2分治法設計思路59

4.3分治法套用與過程分析62

4.3.1最大子段和62

4.3.2歸併排序63

4.3.3棋盤覆蓋問題66

4.3.4最近點對問題68

4.4能力拓展72

4.4.1第k位數72

4.4.2二進制的完全表示74

4.4.3最小違和度75

習題78

第5章回溯法81

5.1概述81

5.2回溯法設計思路81

5.3回溯法示例與過程分析81

5.3.1n皇后問題81

5.3.201背包問題83

5.3.3圖的m著色問題85

5.3.4批處理作業調度問題86

5.4能力拓展88

5.4.1全排列問題88

5.4.2存在障礙物的迷宮問題89

5.4.3圖的m著色問題變種90

5.5習題91

第6章貪心法96

6.1概述96

6.2貪心法設計思路96

6.3貪心法示例與過程分析96

6.3.1部分背包問題96

6.3.2最優裝載問題98

6.3.3乘船問題99

6.3.4旅行商問題100

6.4能力拓展101

6.4.1田忌賽馬問題101

6.4.2過河問題102

習題103

第7章分支限界法108

7.1概述108

7.2分支限界法設計思路108

7.3分支限界法示例與過程分析110

7.3.101背包問題110

7.3.2多段圖最短路徑問題112

7.3.3旅行商問題115

7.3.4作業調度問題119

7.4能力拓展124

7.4.1大富翁遊戲124

7.4.2最優裝載問題126

習題128

第8章動態規劃131

8.1概述131

8.2動態規划算法設計規則131

8.3動態規划算法問題求解132

8.3.101背包問題132

8.3.2最長公共子序列137

8.3.3最長上升子序列141

8.3.4字元串相似度/編輯距離146

8.3.5最大子段和149

8.4能力拓展152

8.4.1帶通配符的字元串匹配152

8.4.2爬樓梯156

習題158

第9章圖算法設計164

9.1概述164

9.1.1圖的定義164

9.1.2圖的相關概念164

9.2圖算法示例與分析165

9.2.1最短路問題165

9.2.2網路最大流問題169

9.2.3二分圖染色問題173

9.3能力拓展176

9.3.1上學問題176

9.3.2聖誕老人的煩惱179

9.3.3烤箱問題182

習題185

第10章計算幾何192

10.1概述192

10.2相關幾何知識193

10.2.1向量193

10.2.2點積和叉積195

10.2.3基本套用196

10.2.4點是否在面內197

10.2.5方向198

10.2.6面積和角度198

10.2.7凸性199

10.3計算幾何示例與分析199

10.3.1點到直線的距離、判斷線段是否相交199

10.3.2凸包問題(極角排序)204

10.3.3利用叉積計算多邊形面積 206

10.4能力拓展208

10.4.1不同直線計數208

10.4.2面積最大的三角形209

10.4.3面積最大的多邊形212

習題215

第11章計算複雜度理論221

11.1計算模型221

11.2P類和NP類問題225

11.3NPC問題227

習題229

第12章機率算法和近似算法230

12.1機率算法230

12.1.1機率算法的基本概念230

12.1.2機率算法的分類231

12.1.3數值機率算法232

12.1.4舍伍德算法232

12.1.5拉斯維加斯算法235

12.1.6蒙特卡羅算法237

12.2近似算法240

12.2.1介紹240

12.2.2頂點覆蓋問題242

12.2.3旅行商問題243

習題244