計算機常用算法與程式設計案例教程（第2版）

《計算機常用算法與程式設計案例教程（第2版）》是2014年清華大學出版社出版的圖書。

基本介紹

• 書名：計算機常用算法與程式設計案例教程（第2版）
• ISBN：9787302382942
• 定價：39元
• 出版社：清華大學出版社
• 出版時間：2014-12-8
• 裝幀：平裝

圖書簡介

本書遵循“精選案例，面向設計，深入淺出，注重能力培養”的要求，以案例形式實現算法與程式設計教學。本書精選了枚舉、遞推、遞歸、回溯、動態規劃、貪心算法與模擬等常用算法，精選各算法求解的典型案例。每一個案例求解，從案例提出到算法設計，從程式實現到算法複雜度分析，環環相扣，融為一體，力求算法理論與實際套用相結合，算法與程式相統一，突出算法在解決實際問題中的核心地位與引導作用。

目錄

第1章算法與程式設計概述1

1.1算法及其描述1

1.1.1算法定義1

1.1.2算法描述3

1.2算法的複雜性分析7

1.2.1時間複雜度7

1.2.2空間複雜度12

1.3算法設計與分析示例13

1.3.1求解最大公約數13

1.3.2拆分為連續正整數之和15

1.3.3統計n!尾部零17

1.4算法與程式設計19

1.4.1算法與程式19

1.4.2結構化程式設計23

習題126第2章枚舉28

2.1枚舉概述28

2.2統計與求和29

2.2.1全素組30

2.2.2最簡真分數32

2.3解方程33

2.3.1佩爾方程33

2.3.2超越方程35

2.4解不等式37

2.4.1分數不等式37

2.4.2代數和不等式38

2.5求最值41

2.5.1基於素數的代數和41

2.5.2整數的因數比43

2.6數組與序列44

2.6.1雙和二組44

2.6.2和積三組46

2.6.3雙碼二部數序列47

2.7數式探求50

2.7.1逆序乘積式50

2.7.2完美綜合式51

2.8趣味數陣55

2.8.1素數幻方55

2.8.2和積三角形58

2.9枚舉套用小結60

習題265第3章遞推66

3.1遞推概述66

3.1.1遞推算法66

3.1.2遞推實施步驟與描述67

3.2超級素數搜尋69

3.3遞推數列72

3.3.1擺動數列72

3.3.2分數數列73

3.4冪序列75

3.4.1雙冪序列75

3.4.2冪積序列76

3.5數陣與格線82

3.5.1楊輝三角82

3.5.2交通方格網84

3.6整數劃分問題86

3.6.1整數劃分遞推設計86

3.6.2整數劃分遞推最佳化88

3.7水手分椰子問題90

3.7.15個水手分椰子90

3.7.2n個水手分椰子93

3.8猴子爬山94

3.8.1簡單案例的具體遞推95

3.8.2一般情形的分級遞推95

3.9遞推套用小結97

習題399第4章遞歸101

4.1遞歸概述101

4.2排隊購票104

4.3漢諾塔問題106

4.3.1求移動次數106

4.3.2展示移動過程107

4.4旋轉數陣109

4.4.1雙轉向旋轉方陣109

4.4.2m行n列順轉矩陣111

4.5快速排序與選擇114

4.5.1快速排序114

4.5.2分區交換選擇117

4.6排列組合的實現119

4.6.1實現排列A(n,m)119

4.6.2實現組合C(n,m)121

4.6.3複雜排列123

4.7整數的拆分125

4.7.1拆分零數取自連續區間126

4.7.2拆分零數取自指定整數127

4.8遞歸套用小結129

習題4132

第5章回溯法133

5.1回溯法概述133

5.1.1回溯的概念133

5.1.2回溯描述133

5.2橋本分數式137

5.2.1橋本分數式138

5.2.210數字分數式140

5.3直尺與串珠141

5.3.1古尺神奇141

5.3.2數碼串珠144

5.4逐位整除數146

5.5環序列149

5.5.1素數和環150

5.5.2德布魯金環151

5.6伯努利裝錯信封問題154

5.6.1裝錯信封問題154

5.6.2特殊錯位探索157

5.7別出心裁的情侶拍照問題159

5.7.1逐位安排與回溯159

5.7.2成對安排與回溯161

5.8回溯套用小結163

習題5166第6章動態規劃167

6.1動態規劃概述167

6.1.1動態規劃的概念167

6.1.2動態規劃實施步驟168

6.2最長子序列探索169

6.2.1最長非降子序列169

6.2.2最長公共子序列172

6.3最優路徑搜尋175

6.3.1點數值三角形的最優路徑175

6.3.2邊數值矩形的最優路徑177

6.4裝載問題180

6.501背包問題183

6.5.1一般01背包問題184

6.5.2二維約束01背包問題188

6.6凸n邊形的三角形劃分190

6.7插入乘號問題193

6.8動態規劃套用小結195

習題6198第7章貪心算法200

7.1貪心算法概述200

7.2刪數字問題202

7.3埃及分數式205

7.3.1選擇最小分母構建205

7.3.2貪心選擇範圍的擴展207

7.4可拆背包問題208

7.5數列操作與極差209

7.5.1數列操作210

7.5.2數列操作最佳化211

7.5.3數列極差212

7.6哈夫曼樹及其套用215

7.6.1哈夫曼樹215

7.6.2哈夫曼編碼217

7.7貪心算法套用小結221

習題7222第8章模擬224

8.1模擬概述224

8.1.1模擬分類224

8.1.2豎式運算模擬227

8.2乘數探求229

8.2.1積為若干個1構成229

8.2.2積為若干個2015構成230

8.2.3積的任意指定構成231

8.3尾數前移問題233

8.3.1限1位尾數前移233

8.3.2多位尾數前移235

8.4階乘冪與排列組合數的計算236

8.5圓周率計算238

8.5.1蒙特卡羅模擬計算238

8.5.2指定高精度計算239

8.6漫步坐標系241

8.7模擬發橋牌244

8.8泊松分酒問題247

8.9模擬套用小結250

習題8251第9章算法的綜合套用253

9.1高斯皇后問題253

9.1.1高斯八皇后問題253

9.1.2n皇后問題255

9.1.3皇后全控棋盤問題259

9.2翻轉硬幣遊戲263

9.2.1翻轉m×9矩陣263

9.2.2翻轉m×n矩陣266

9.2.3大規模矩陣求解270

9.3最優複雜路徑探索273

9.3.1矩陣迷宮中的最短通道273

9.3.2三角數陣中的最小路徑277

9.4馬步遍歷與哈密頓圈280

9.4.1馬步遍歷280

9.4.2馬步型哈密頓圈287

9.4.3組合型哈密頓圈292

9.5綜合套用小結299

習題9300

附錄A部分習題求解要點301

附錄B在VisualC++6.0環境下運行C程式方法簡介315

附錄CC語言常用庫函式320

參考文獻324