算法設計與問題求解（第2版）——計算思維培養

《算法設計與問題求解（第2版）——計算思維培養》是2020年5月電子工業出版社出版的圖書，作者是李清勇。

基本介紹

• 書名：算法設計與問題求解（第2版）——計算思維培養
• 作者：李清勇
• ISBN：9787121295157
• 出版社：電子工業出版社
• 出版時間：2020年5月
• 頁數：256
• 字數：408千字
• 開本：16開
• 版次：01-01

內容簡介

在資訊時代，計算思維是解決複雜工程問題的重要思維方式，計算機則是求解問題的重要工具。本書以計算機經典問題求解為導向，通用算法思維和編程能力培養為目標，引入ACM國際大學生程式設計競賽的有益元素，組織教材的理論教學和編程實踐兩方面的內容。本書主要內容包括計算機問題求解的經典算法模型和設計範式，包括計算機問題求解中常用的數據結構、枚舉算法、遞歸與分治策略、動態規劃、貪心算法和搜尋技術。除了強調經典的問題原型和算法原理，本書兼顧編程實踐能力，力圖使得學生面對複雜問題時既能“想到”還能“做到”。

圖書目錄

目 錄

第1章 計算機問題求解概述1

1.1 問題與問題實例1

1.2 計算機問題求解周期2

1.3 算法與程式5

1.4　算法複雜性分析5

1.4.1　空間複雜性6

1.4.2 時間複雜性7

習題115

第2章 程式設計語言與數據結構16

2.1 程式設計語言的“盲點”16

2.1.1 long不夠長17

2.1.2 double不夠準19

2.1.3 遞歸不夠快25

2.2 基本數據結構26

2.2.1 線性表26

2.2.2 棧和佇列30

2.2.3 樹和二叉樹36

2.2.4 優先佇列和堆44

2.2.5 圖45

2.2.6 並查集47

2.3 標準模板庫49

2.3.1 模板的基本概念49

2.3.2 標準模板庫概述51

2.3.3 標準模板庫套用52

習題263

第3章 枚舉算法69

3.1 枚舉的基本思想69

3.2 模糊數字70

3.3 真假銀幣72

3.4 m錢n雞75

3.5 數字配對77

3.6 繩子切割79

3.7 石頭距離81

習題384

第4章 遞歸與分治90

4.1 遞歸程式90

4.2 分治法的基本原理94

4.3 合併排序96

4.4 逆序對問題100

4.5 快速排序102

4.6 最接近點對問題106

4.7 指數運算111

4.8 二分查找113

習題4114

第5章 動態規劃122

5.1 動態規劃的基本思想122

5.1.1 動態規劃的基本要素124

5.1.2 動態規劃的求解步驟125

5.2 矩陣連乘126

5.3 最優二叉搜尋樹131

5.4 多段圖最短路徑136

5.5 最長公共子序列140

5.6 0-1背包問題143

5.7 最大上升子序列146

習題5149

第6章 貪心算法155

6.1 貪心算法的基本要素155

6.2 活動安排問題157

6.3 小數背包問題161

6.4 最優前綴碼164

6.5 單源最短路徑169

6.6 最小生成樹174

6.6.1 Prim算法175

6.6.2 Kruskal算法178

習題6182

第7章 搜尋技術187

7.1 問題的狀態空間表示187

7.2 深度優先搜尋189

7.3 廣度優先搜尋191

7.4 回溯算法193

7.4.1 回溯算法的基本原理和框架程式193

7.4.2 裝載問題的回溯算法199

7.4.3 圓排列問題203

7.5 分支限界206

7.5.1 分支限界法的基本原理206

7.5.2 裝載問題的分支限界法208

7.6 啟發式搜尋211

7.6.1 啟發式搜尋基本原理211

7.6.2 裝載問題的啟發式搜尋215

習題7217

附錄A 複雜度分析的數學基礎225

附錄B 常用C語言和STL函式235

附錄C 程式設計競賽和OnlineJudge介紹241

附錄D 教學資源244

參考文獻245