•注重常用算法的選取與組織。結合本科教學實際，精心選取了幾個常用算法。

•注重典型案例的精選與提煉。對選取的每一種算法，設計了基礎型、應用型與綜合型三種難度梯度的典型案例。

•注重算法設計與實現的緊密結合。采用功能豐富、應用面廣、高校學生使用率最高的C語言描述算法，并直接在VC++環境下測試通過，大大縮減了算法設計與程序實現的距離。

•注重算法設計的改進與優化。對某些典型案例提供了多種算法設計，編寫出不同表現形式和設計風格的算法，體現了算法設計的靈活性和多樣性。

進入21世紀，隨著計算機的廣泛普及與信息技術的深入發展，培養應用型軟件開發人才成為提高國家科技水平的重要方面。國家“973”信息技術與高性能軟件基礎規劃項目首席科學家顧鈞教授與中國工程院院士李國杰教授指出：“我國的軟件開發要算法先行，這樣才能推動軟件技術的研究與開發，提高我國企業軟件產品的技術競爭力和市場競爭力。”

“算法設計與分析”是計算機科學技術學科體系的一個核心問題，是大學計算機專業一門重要的專業基礎課。計算機算法設計是應用計算機解決實際問題的核心環節，是一種創造性思維活動，其教育必須面向應用。針對目前相關教材中，算法內容貪多求全、貪廣求深，算法理論與實際應用脫節的現狀，探索與改革適合計算機本科層次教學的“算法設計與分析”教材，直接關系到學生應用算法設計解決實際問題能力的培養與提高，是實現算法課程教學目標的當務之急。

為此，我們在《計算機常用算法與程序設計教程》（“十一五”國家級規劃教材，人民郵電出版社，2008.11）與《計算機常用算法與程序設計案例教程》（清華大學出版社，2011.7）兩本書的基礎上進行整合優化，推出適合計算機本科教學實際的《算法設計與分析實用教程》，對算法的組織與案例的選取、算法理論闡述與案例實際應用結合進行精心設計，力求適合高校本科教學目標與知識結構的要求。

本書遵循“精選算法，面向設計，突出案例應用，注重能力培養”的編寫宗旨，具有以下“四注重”特色。

（1）注重常用算法的選取與組織

本書在常用算法的選取方面，克服以往貪多求全、貪廣求深的弊端，結合本科教學實際，精心選取了枚舉、遞推、遞歸、動態規劃、回溯、貪心算法與模擬等常用算法，避免出現本科階段與研究生階段的教學內容混雜不分的局面。其中，模擬算法中的“豎式運算模擬”是我們總結推廣應用于數論高精計算的創新成果。

對選取的常用算法，在介紹算法的基本理論與設計規范的基礎上，推介該算法設計應用的常用模式，聯系典型案例講述該算法中要求本科生掌握的基本內容與應用設計，刪除一些難度大、理論深、應用少的帶研究性質的算法內容。

（2）注重典型案例的精選與提煉

算法是程序設計的核心，算法需要典型案例的展示與支撐。培養學生學習算法設計的興趣，激發學生應用算法設計解決實際問題的學習熱情，不是一兩句空洞說教所能奏效的，必須通過一些有趣的、有啟發性的典型案例來引導。教程在算法材料的組織上，克服以往羅列算法多、應用算法設計解決實際問題少、算法理論與實際應用脫節的弊端，對選取的每一種算法，設計了基礎型、應用型與綜合型三種難度梯度的典型案例，包括基礎的數值求解、常見的數據處理、有趣的智力測試、巧妙的模擬探索，既有啟發引導的基礎案例，也有難度較大的綜合案例，既有構思巧妙的新創趣題，也有歷史悠久的經典名題，難度適宜，深入淺出。

這些典型案例的精選與提煉有利于提高學生學習算法設計的興趣，有利于學生在計算機實際案例求解上開闊視野，使之在算法思路的開拓與設計技巧的應用上有一個深層次的鍛煉與提高。通過典型案例來展開算法設計與分析，突出算法設計在解決實際案例中的核心地位與指導作用。其中一些難度較大的綜合型案例可作為課后的專題研究與課程設計選用。

（3）注重算法設計與實現的緊密結合

算法是程序設計的核心與靈魂，程序是算法的一種描述與實現手段。算法與程序實際上是一個統一體，不應該也不能將它們對立或分割。教程采用功能豐富、應用面廣、高校學生使用率最高的C語言描述算法，并直接在VC++環境下測試通過，大大縮減了算法設計與程序實現的距離。對每一個實際案例，從案例提出、算法設計與描述，到算法測試與分析、算法改進與優化，環環相扣，融為一體。學生看得懂、學得會、用得上，可以收到立竿見影、舉一反三的效果，力求理論與實際相結合、算法設計與應用實際相統一，突出算法在解決實際案例中的核心地位與引導作用，切實提高學生對算法思想的理解和算法設計的把握，有效提高學生應用算法設計解決實際問題的水平和能力。

（4）注重算法設計的改進與優化

算法設計不可能是一成不變的，教材對某些典型案例提供了多種算法設計，編寫出不同表現形式與不同設計風格的算法，并對一些常規設計實施多層次多方位的變通、改進與優化，集中體現了算法設計的靈活性和多樣性。對不同算法的復雜性分析，確立不同算法的特點與適應環境，比較出不同算法的優劣。

變通出成果，變通長能力。算法改進與優化的過程既是提高案例求解效率的過程，也是對學生算法設計能力培養與提高的過程，更是優化意識與創新能力增強的過程。

為方便師生教學，本書配套的教學課件、源代碼與習題的參考解答均可從指定網站下載。

本書可作為各高等院校計算機及相關專業“算法設計與分析”、“計算機程序設計應用基礎”等課程教材，供各級程序設計選拔賽與ACM復習參考；也可供IOI、NOI及各省程序設計競賽培訓選用；還可作為廣大程序設計愛好者與軟件開發人員的參考書。

本書由楊克昌、嚴權峰進行策劃、編著與統稿。在本書的編寫過程中，湖南理工學院的王岳斌教授、周持中教授以及甘靖、方世林等老師給予了多方面的指導與幫助，唐雁、陳凱、姜鎮林等同學閱讀了書稿并測試了相關算法，在此深表感謝。

盡管每一算法設計都經反復核實檢查與檢測調試，但因涉及內容較廣，難免存在差錯，懇請專家與讀者批評指正。

編著者

2013年6月

前言

第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.2.3 NP完全問題 12
1.3 算法設計與分析實例 13
1.3.1 求解最大公約數 13
1.3.2 計算n! 14
1.3.3 全碼倍數搜索 16
1.4 算法與程序設計 17
1.4.1 算法與程序 17
1.4.2 結構化程序設計 21
習題1 23
第2章 枚舉 26
2.1 枚舉概要 26
2.2 統計求和 27
2.2.1 同碼小數 27
2.2.2 三角網格 30
2.3 整數搜索 32
2.3.1 整數對 32
2.3.2 基于s的雙和數組 33
2.3.3 最小連續m個合數 34
2.4 解方程與不等式 37
2.4.1 佩爾方程 37
2.4.2 分數不等式 38
2.5 數式與運算 40
2.5.1 奇數序列運算式 40
2.5.2 完美綜合運算式 41
2.6 數列與數陣 44
2.6.1 H形數序列 44
2.6.2 三階素數幻方 46
2.7 表格與圖形 48
2.7.1 p進制乘法表 48
2.7.2 基于s的和積三角形 49
2.8 枚舉設計的改進與優化 52
2.8.1 選擇枚舉路線 52
2.8.2 精簡枚舉結構 54
2.8.3 優化枚舉參數 55
習題2 56
第3章 遞推 59
3.1 遞推概述 59
3.1.1 遞推的概念 59
3.1.2 遞推常用模式 60
3.2 遞推數列 61
3.2.1 雙關系遞推數列 62
3.2.2 振動數列 63
3.2.3 分數數列 65
3.3 超級素數搜索 66
3.4 數陣與網格 69
3.4.1 楊輝三角 69
3.4.2 方格網交通線路 71
3.5 六六順數組 73
3.6 猴子爬山 76
3.6.1 簡單遞推設計 76
3.6.2 分級遞推設計 77
3.7 整數劃分 79
3.7.1 整數劃分式的個數 79
3.7.2 整數劃分式的實現 80
3.7.3 實現整數劃分式的優化 82
3.8 遞推與迭代 84
習題3 86
第4章 遞歸 88
4.1 分治策略與遞歸 88
4.2 漢諾塔游戲 92
4.2.1 移動次數求解 93
4.2.2 移動過程實現 94
4.3 排隊購票問題 96
4.3.1 常規排隊 96
4.3.2 帶條件限制的排隊 98
4.4 多轉向旋轉方陣 100
4.5 快速排序與選擇 102
4.5.1 分區交換排序 103
4.5.2 分區交換選擇 105
4.6 實現排列組合 107
4.6.1 基本排列實現 107
4.6.2 復雜排列實現 109
4.6.3 組合實現 111
4.7 整數的拆分式 113
4.8 遞歸與遞推 115
習題4 117
第5章 回溯法 119
5.1 回溯法概述 119
5.1.1 回溯的概念 119
5.1.2 回溯的數學概括與效益分析 120
5.1.3 回溯法的分類 121
5.2 橋本分數式 124
5.3 直尺與串珠 127
5.3.1 古尺神奇 127
5.3.2 數碼串珠 129
5.4 逐位整除數 132
5.4.1 回溯探索 132
5.4.2 遞推求解 133
5.5 二組均分 135
5.6 伯努利裝錯信封問題 136
5.6.1 回溯設計 137
5.6.2 遞歸探索 138
5.7 情侶拍照 140
5.7.1 逐位安排回溯設計 140
5.7.2 成對安排回溯設計 142
5.8 回溯應用小結 144
習題5 145
第6章 動態規劃 147
6.1 動態規劃概述 147
6.1.1 動態規劃的概念 147
6.1.2 動態規劃實施步驟 149
6.2 0-1背包問題 150
6.2.1 一般0-1背包問題 150
6.2.2 二維約束0-1背包問題 153
6.3 西瓜分堆 156
6.4 凸n邊形的三角形劃分 158
6.5 最長子序列 160
6.5.1 最長非降子序列 160
6.5.2 最長公共子序列 163
6.6 插入乘號問題 165
6.7 數陣中的最優路徑 167
6.7.1 三角數陣中的最大路徑 167
6.7.2 矩陣中的最大路徑 169
6.8 動態規劃設計小結 172
習題6 172
第7章 貪心算法 174
7.1 貪心算法概述 174
7.1.1 貪心算法的概念 174
7.1.2 貪心算法的理論基礎 175
7.2 背包問題 176
7.2.1 可拆背包問題 176
7.2.2 0-1背包問題 178
7.3 刪數字問題 179
7.4 埃及分數式 182
7.4.1 選擇最小分母構建 182
7.4.2 貪心選擇范圍的擴展 184
7.5 數列操作與極差 185
7.5.1 數列操作 185
7.5.2 數列操作優化 187
7.5.3 數列極差 188
7.6 哈夫曼樹及其應用 190
7.6.1 哈夫曼樹 190
7.6.2 哈夫曼編碼 193
7.7 貪心算法應用小結 196
習題7 197
第8章 模擬 199
8.1 模擬概述 199
8.1.1 模擬分類 199
8.1.2 豎式運算模擬 202
8.2 乘數探求 203
8.2.1 積為若干個1構成 203
8.2.2 積為若干個2014構成 204
8.2.3 積為任意指定構成 205
8.3 特殊數積 206
8.3.1 01串積 206
8.3.2 二部數積 209
8.4 尾數前移問題 213
8.4.1 限1位尾數前移 213
8.4.2 多位尾數前移 215
8.5 圓周率計算 218
8.5.1 蒙特卡羅模擬計算 218
8.5.2 指定高精度計算 219
8.6 模擬發橋牌 221
8.7 泊松分酒 223
8.8 模擬應用小結 226
習題8 227
第9章 算法的綜合應用與優化案例 228
9.1 冪積序列 228
9.1.1 雙冪積枚舉設計 228
9.1.2 雙冪積遞推設計 230
9.1.3 多冪積拓廣 233
9.2 高斯皇后問題 234
9.2.1 高斯八皇后問題 235
9.2.2 n皇后問題 236
9.2.3 皇后全控棋盤 238
9.3 翻轉硬幣 241
9.3.1 m×9矩陣枚舉設計 241
9.3.2 m×n矩陣回溯設計 247
9.3.3 大規模矩陣貪心設計 251
9.4 最優復雜路徑 257
9.4.1 三角數陣中的最小路徑 257
9.4.2 矩陣迷宮中的最小通道 260
9.5 馬步遍歷與哈密頓圈 263
9.5.1 馬步遍歷 263
9.5.2 馬步型哈密頓圈 268
9.5.3 組合型哈密頓圈 272
9.6 算法綜合應用小結 277
習題9 278
附錄A 在VC++ 6.0環境下運行C程序
方法簡介 280
附錄B C常用庫函數 284
參考文獻 288

1. 計算思維與大學計算機基礎 [主編　趙旭劍]
2. 大學信息技術實訓教程 [主編 任云暉 丁紅 趙琳琳]
3. 大學信息技術教程 [主編 任云暉 馮政軍 魏斌]
4. 信息技術基礎立體化教程 [鄒承俊 周洪林 劉和文 葉煜 ]
5. 大學計算機基礎與計算思維 [主編 閔笛 汪瑩]
6. 信息技術基礎項目化教程 [主編 王宏斌 王萬麗 王芳]
7. 大學計算機信息素養（第二版） [主編 盧山]
8. 全國計算機等級考試一級（MS Office）指導手冊 [主編 王宏斌 孫元 禹晨]
9. 大學計算機基礎實驗指導及習題解析 [主編 閔笛 李明]
10. 大學計算機信息素養實驗指導（第二版） [主編 盧山]
11. 信息技術基礎（微課版） [主編　趙艷莉　喻林]
12. 大學信息技術基礎 [主編 黎夏克 張倩文 王靜]
13. 計算機信息素養基礎實踐教程 [王錦 姚曉杰 王立武 等 編著]
14. 計算機基礎與應用實踐教程 [楊毅 劉立君 張春芳 梁寧玉 ]
15. 計算機信息素養基礎 [主編 陳艷 秦凱 黃海玉]
16. 計算機基礎與應用 [主編 秦凱 梁寧玉 王毅]
17. 大學計算機基礎上機實踐教程（第六版） [主編 何振林 羅奕]
18. 大學計算機基礎教程實驗指導與測試題集 [主編 饒拱維 吳華光 巫滿秀]
19. 大學計算機基礎（等級考試版） [主編 鐘誠]
20. 大學計算機基礎教程（第二版） [主編 安志遠 崔巖]
21. 計算機應用基礎實訓教程（第三版） [主 編 王向慧 康秀蘭]
22. 計算機應用基礎（第三版） [主 編 王向慧 康秀蘭]
23. 計算機應用基礎 [主編　趙艷莉]
24. 大學計算機基礎案例教程（第二版） [主 編 葉潮流 金 瑩]
25. 大學信息技術 [主編　連衛民　張志明　陳炎龍]
26. 新編計算機應用基礎教程 [主編　戴毅　吳瑞芝　賈姍姍]
27. 計算機應用基礎 [主編 譚慧 楊志茹]
28. 大學計算機基礎實驗指導與習題解析 [主編 闕清賢 羅如為]
29. 計算機應用基礎實訓教程 [主編 王蒙田 李衛星]
30. 計算機基礎及信息素養 [主編 周永福 鐘建坤]