新編實用算法分析與程序設計檢視原始碼討論檢視歷史

新編實用算法分析與程序設計

原圖鏈接來自搜狗的圖片

《新編實用算法分析與程序設計》是由王建德編寫的一本書籍。講述了算法的基本概念、各種排序與解題的方法及策略，論述了初等數論、計算幾何學、搜索和圖論的有關算法，最後討論了動態規劃。本書從教學的角度詳細講解算法理論，從競賽的角度對經典習題進行詳細解析，培養學生靈活運用算法的能力。

基本內容

書 名: 新編實用算法分析與程序設計

作　者：王建德

出版社： 人民郵電出版社

出版時間： 2008

ISBN: 9787115177063

開本： 16

定價: 39.00 元

內容簡介

本書是一部程序設計競賽教程。書中首先講述了算法的基本概念、各種排序與解題的方法及策略，然後論述了初等數論、計算幾何學、搜索和圖論的有關算法，最後討論了動態規劃。本書不僅從教學的角度詳細講解算法理論，而且從競賽的角度對經典習題進行詳細解析，培養學生靈活運用算法的能力。本書既可以作為大專院校計算機專業算法類課程的教材，亦可以作為大中學校計算機競賽活動的培訓教材，還可供計算機軟硬件研發人員參考。

作者簡介

王建德：著名的信息學奧林匹克競賽金牌教練，國務院特殊津貼專家，中學特級教師。他所輔導的學生在國際奧林匹克信息學競賽中獲7金，2銀，2銅的信奉異教成績。先後出版了22本關於程序設計和算法的學術專著，其中《實用算法的分析與程序設計》廣受好評，長期以來是國內各類程序設計競賽的必備教程。吳永輝：博士，復旦大學計算機科學與工程系副教授，ACM-ICPC中國賽區指導委員會成員，復旦大學ACM程序設計競賽隊教練。自2001年起連續帶隊進入ACM-ICPC世界總決賽，並取得過世界第6名的佳績。主要研究方向為數據庫，在《計算機研究與發展》，《軟件學報》以及重大學術會議上發表多篇論文，參與譯著《數據通信與網絡》和《數據通信，計算機網絡與開放系統》。

目錄

第1章　緒論　1

1.1　算法的基本定義　1

1.2　算法的空間複雜度　2

1.2.1　壓縮存儲技術　2

1.2.2　原地工作　3

1.3　算法的時間複雜度　3

1.3.1　基本運算　4

1.3.2　輸入規模　4

1.3.3　輸入情況　5

1.3.4　時間複雜度的階　6

1.4　優化時間效率的方法　8

1.4.1　編程實現算法時注意細節優化　8

1.4.2　尋找解題思路時儘可能考慮最優性　13

1.5　實際生活中常見的算法問題　16

第2章　排序、順序統計與解題的基本策略　18

2.1　計數排序與貪心策略　19

2.1.1　計數排序　19

2.1.2　貪心策略　22

2.2　「二分」思想與快速排序　30

2.2.1　分類和分治思想　30

2.2.2　快速排序採用二分法　30

2.2.3　快速排序和二分法在順序統計問題上的應用　32

2.3　堆排序的思想與應用　36

2.3.1　在調整中保持堆性質　37

2.3.2　建堆　37

2.3.3　堆排序　38

2.4　數據有序化　46

2.4.1　預處理階段的數據有序化　46

2.4.2　實時處理階段的數據有序化　47

習題　51

第3章　初等數論的有關算法　54

3.1　計算a和b最大公約數的歐幾里得公式gcd(a,b)　54

3.2　計算N的最大互質數　55

3.3　歐幾里得公式推廣：計算最大公約數的線性組合　56

3.4　計算同餘方程ax≡b(modn)(n＞0)　56

3.5　求解同餘式組　61

3.6　解不定方程ax+by=c　68

3.7　初等數論知識的應用　75

3.7.1　運用反覆平方法求數的冪模n　75

3.7.2　素數的測試　81

3.7.3　整數的因子分解　82

習題　83

第4章　計算幾何學的有關算法　86

4.1　線段的性質　86

4.2　計算兩條相交線段的交點　94

4.3　判斷任意一組線段中是否存在相交情況　95

4.4　計算線段p1p2的中垂線方程　97

4.5　計算凸多邊形的重心位置和面積　101

4.6　尋找最近點對　102

4.7　計算包含平面所有點的二維凸包　105

4.8　將凸包問題由二維拓展至三維　110

4.8.1　計算三維凸包體積的基本思想　110

4.8.2　計算由3個空間點組成的劈面三稜柱的體積V(R(i))　111

4.8.3　計算包含點集p的三維凸包體積　112

4.9　計算幾何類問題的類型和應對的基本方法　114

習題　120

第5章　搜索的有關算法　124

5.1　枚舉法　124

5.2　寬度優先搜索　129

5.2.1　寬度優先搜索的定義　129

5.2.2　寬度優先搜索的應用　130

5.3　深度優先搜索與回溯法　134

5.3.1　深度優先搜索　134

5.3.2　回溯法——採用縱深搜索的策略構建與處理隱式圖　139

5.4　搜索的剪枝優化　150

5.5　二分搜索　167

5.6　參數搜索　173

習題　183

第6章　圖論的有關算法　187

6.1　計算圖的傳遞閉包　187

6.2　最小生成樹的算法及其應用　193

6.2.1　計算最小生成樹的基本思路　193

6.2.2　計算最小生成樹的兩種算法　195

6.2.3　最小生成樹的應用實例　202

6.3　最短路徑的算法及其應用　209

6.3.1　最短路徑計算的基本原理　209

6.3.2　計算最短路徑的常用算法　212

6.4　二分圖的匹配及其應用　223

6.4.1　二分圖和匹配的基本概念　224

6.4.2　怎樣判別二分圖　225

6.4.3　怎樣計算二分圖的最大匹配　226

6.4.4　二分圖的最小覆蓋問題　231

6.4.5　二分圖的最佳匹配問題　235

6.5　網絡流圖的思想和應用　246

6.5.1　計算網絡流量的基本思想　247

6.5.2　按層次計算最大流的Dinic算法　250

6.5.3　計算網絡流量的應用實例　253

6.5.4　網絡增加多源多匯和容量下界因素後的流量計算問題　263

6.5.5　網絡增加費用因素後的流量計算問題　271

習題　283

第7章　討論動態規劃　286

7.1　動態規劃的基本思想　286

7.2　動態規劃的計算步驟　286

7.3　動態規劃的優化策略　294

習題　324

參考文獻　328

……