算法設計與分析 — 基於計算教學論的解析

本教材是基於作者所創立的計算教學論編寫的，是為實現教學效率顯著提升而對計算教學論提出的思想、 方法和工具的深廣應用。 本教材共 12 章。第 1 章由 Euclid GCD 算法引出算法的定義，並介紹基於可視化的算法學習方法，第 2～5 章分別介紹算法的窮舉設計方法、算法復雜度分析、算法的遞歸設計方法和基於比較的排序算法，第 6～10 章 分別介紹分治、動態規劃、貪心、回溯和分支限界等經典的算法設計方法，第 11 章介紹 RSA 算法，第 12 章介 紹 NP 理論。 本教材可作為高等學校電腦科學與技術專業算法設計與分析課程的教材，也可作為電腦及相關專業研 究生和科研、工程或技術人員自學算法設計與分析的參考書。

目 錄 第 1 章 算法及其可視化教學支持系統 ............ 1 初識算法：Euclid GCD 算法 .............. 1 1.1.1 GCD 及因子分解方法 .............. 1 1.1.2 Euclid GCD 算法 ....................... 3 算法的定義 .......................................... 3 1.2.1 算法是一種求解問題的 科學方法 ................................... 4 1.2.2 算法的克努特定義.................... 5 1.2.3 算法的圖靈機定義.................... 6 算法的描述方法 .................................. 8 1.3.1 算法的自然語言描述方法 ........ 8 1.3.2 算法的流程圖描述方法 ............ 8 1.3.3 算法的偽代碼描述方法 ............ 9 1.3.4 算法的現代版 C++描述方法 ... 10 1.3.5 設計算法求解問題的 基本過程 ................................. 10 可視化算法學習的支持工具............. 12 1.4.1 CAAIS 的基本界面及其 功能 ......................................... 12 1.4.2 算法 CD-AV 演示的基本 操作 ......................................... 13 使用現代版 C++進行算法實驗 ........ 15 1.5.1 現代版 C++的算法實驗 環境建議 ................................. 15 1.5.2 算法的現代版 C++實現 方式——以 Euclid GCD 算法為例 ................................. 16 算法國粹——《九章算術》中的 二進制 GCD 算法 .............................. 17 1.6.1 《九章算術》中的更相減 損術——最早的二進制 GCD 算法 ................................ 17 1.6.2 現代版的二進制 GCD 算法 .... 18 習題 ............................................................ 19 參考文獻 ..................................................... 20 第 2 章 算法的窮舉設計方法 .......................... 22 窮舉算法設計基礎 ............................ 22 窮舉算法設計示例 ............................ 23 2.2.1 百錢買百雞問題算法設計 ..... 23 2.2.2 素性測試的試除算法設計 ..... 26 2.2.3 順序搜索算法設計及 CD-AV 演示 ......................................... 28 2.2.4 洗牌算法設計及 CD-AV 演示 29 偽隨機數發生器及其在算法實驗 中的應用 ............................................ 31 2.3.1 生成偽隨機數的線性同餘法 ... 31 2.3.2 傳統 C 語言標準庫中的 偽隨機函數及其應用 ............. 32 2.3.3 現代版 C++標準庫中的 偽隨機函數及其應用 ............. 33 2.4 算法國粹——圖靈獎獲得者姚期智 院士的偽隨機數理論 ........................ 34 2.4.1 姚期智院士密碼學安全的 偽隨機數理論 ......................... 35 2.4.2 LCG 不是密碼學安全的 ........ 35 2.4.3 Java JDK 提供的密碼學 安全的偽隨機數發生器 ......... 37 習題 ........................................................... 39 參考文獻 ..................................................... 40 第 3 章 算法復雜度分析 .................................. 42 算法復雜度分析基礎 ........................ 42 3.1.1 算法的輸入規模及復雜度 計量 ......................................... 42 3.1.2 算法的最好、最壞和平均 情況復雜度 ............................. 43 算法復雜度的漸近分析方法 ............ 45 3.2.1 算法的漸近復雜度及其記法 . 46 3.2.2 常見的算法復雜度階及其 關系 ......................................... 51 算法設計與分析——基於計算教學論的解析 - VIII - 3.2.3 算法復雜度漸近分析的 基本範型 ................................. 53 大整數算術運算的復雜度 ................ 55 3.3.1 二進制數的豎式算術運算的 復雜度 ..................................... 55 3.3.2 大整數的多精度表示 .............. 57 3.3.3 多精度整數算術運算的 復雜度 ..................................... 57 Euclid GCD 算法的復雜度分析 ........ 59 3.4.1 Fibonacci 數列及其通項的 閉式解 ..................................... 59 3.4.2 Euclid GCD 算法復雜度的 詳細分析 ................................. 62 算法復雜度的平攤分析方法............. 64 3.5.1 平攤分析方法概述.................. 64 3.5.2 Fibonacci 堆的基本操作及其 復雜度的平攤分析.................. 66 算法復雜度的實驗分析法 ................ 70 3.6.1 算法復雜度實驗分析的 必要性和基本過程.................. 70 3.6.2 算法復雜度的實驗分析法 示例 ......................................... 72 問題的復雜度 .................................... 73 3.7.1 問題的復雜度概述.................. 73 3.7.2 基於比較的排序問題的 復雜度 ..................................... 74 算法國粹——姚期智院士的通信 復雜性理論 ........................................ 76 3.8.1 通信復雜性的問題定義 .......... 76 3.8.2 通信復雜性理論的基本成果.... 77 習題 ............................................................ 80 參考文獻 ..................................................... 81 第 4 章 算法的遞歸設計方法 .......................... 84 遞歸算法的普適性及其理論內涵 ..... 84 4.1.1 遞歸算法的基本特性及實例 .... 84 4.1.2 遞歸是一種普適的算法表達 方法 ......................................... 86 子集遍歷問題的遞歸窮舉算法 ......... 88 4.2.1 子集遍歷問題及其遞歸窮舉 算法設計 ................................. 88 4.2.2 現代版 C++實現與 CD-AV 演示設計 ................................. 90 全排列遍歷問題的遞歸窮舉算法 .... 93 4.3.1 全排列遍歷問題及其遞歸 窮舉算法設計 ......................... 93 4.3.2 現代版 C++實現與 CD-AV 演示設計 ................................. 96 0-1 背包問題及其遞歸窮舉算法 ...... 98 4.4.1 0-1 背包問題的定義及 解空間分析 ............................. 99 4.4.2 0-1 背包問題的遞歸窮舉 算法 ....................................... 100 TSP 問題及其遞歸窮舉算法 .......... 101 4.5.1 TSP 問題的定義及解空間 分析 ....................................... 101 4.5.2 TSP 問題的遞歸窮舉算法 ... 103 棧框架及將遞歸算法轉換為迭代 算法的方法 ...................................... 105 4.6.1 函數調用的棧框架 ............... 105 4.6.2 將遞歸算法轉換為迭代 算法的方法 ........................... 107 算法國粹——管梅谷教授的 中國郵遞員問題 ............................... 111 4.7.1 CPP 與歐拉迴路 .................... 111 4.7.2 CPP 的求解思路與算法 ........ 112 習題 .......................................................... 114 參考文獻 .................................................... 116 第 5 章 基於比較的排序算法 ......................... 118 冒泡排序算法 ................................... 118 5.1.1 基本思想、偽代碼與復雜度 分析 ........................................ 118 5.1.2 現代版 C++實現 ................... 120 5.1.3 CD-AV 演示設計 .................. 121 插入排序算法 .................................. 122 5.2.1 基本思想、偽代碼與復雜度 分析 ....................................... 123 5.2.2 現代版 C++實現 ................... 125 5.2.3 CD-AV 演示設計 .................. 125 堆排序算法 ...................................... 126 5.3.1 二叉堆的理論及相關算法 ... 127 目錄 - IX - 5.3.2 基本思想、偽代碼與復雜度 分析 ....................................... 131 5.3.3 現代版 C++實現 ................... 133 5.3.4 CD-AV 演示設計 .................. 133 5.3.5 優先隊列簡介 ....................... 136 算法國粹——π 值計算方法 ............ 137 5.4.1 劉徽關於 π 值的“割圓術” 計算方法 ............................... 137 5.4.2 祖沖之的 π 值計算成果 ........ 138 5.4.3 π 值的近現代計算方法和 計算成果 ............................... 138 習題 .......................................................... 139 參考文獻 ................................................... 140 第 6 章 算法的分治設計方法 ........................ 141 分治法基礎 ...................................... 141 6.1.1 分治法概述 ........................... 141 6.1.2 二分搜索算法 ....................... 142 Karatsuba 乘法算法 ......................... 144 6.2.1 大整數乘法的樸素分治 算法 ....................................... 144 6.2.2 大整數乘法的 Karatsuba 算法 ....................................... 145 歸並排序算法 .................................. 147 6.3.1 基本思想、偽代碼與復雜度 分析 ....................................... 147 6.3.2 現代版 C++實現與 CD-AV 演示設計 ............................... 150 快速排序算法 .................................. 152 6.4.1 基本思想、偽代碼與復雜度 分析 ....................................... 152 6.4.2 現代版 C++實現與 CD-AV 演示設計 ............................... 155 大師定理及其應用 .......................... 156 6.5.1 大師定理簡介 ....................... 157 6.5.2 大師定理的應用 ................... 157 算法國粹——賈憲的增乘開平 方法 .................................................. 158 6.6.1 增乘開平方法詳解................ 158 6.6.2 近代開平方法——牛頓 迭代法 ................................... 160 習題 ......................................................... 161 參考文獻 ................................................... 163 第 7 章 算法的動態規劃設計方法 ................ 164 DP 方法概述 .................................... 164 7.1.1 Fibonacci 數的 DP 計算 ....... 164 7.1.2 DP 方法的基本思想及其所 求解問題的兩個重要特徵 ... 166 7.1.3 DP 算法設計的基本步驟 ..... 167 兩個字符串間的編輯距離問題的 DP 算法 ........................................... 168 7.2.1 DP 方程及算法設計 ............. 168 7.2.2 現代版 C++實現與復雜度 分析 ....................................... 172 7.2.3 CD-AV 演示設計 .................. 174 矩陣鏈相乘問題的 DP 算法 ........... 176 7.3.1 DP 方程及算法設計 ............. 176 7.3.2 現代版 C++實現與復雜度 分析 ....................................... 179 7.3.3 CD-AV 演示設計 .................. 181 0-1 背包問題的 DP 算法 ................. 184 7.4.1 DP 方程及算法設計 ............. 184 7.4.2 現代版 C++實現與復雜度 分析 ....................................... 187 7.4.3 CD-AV 演示設計 .................. 189 TSP 問題的 DP 算法 ....................... 191 7.5.1 DP 方程及算法設計 ............. 191 7.5.2 現代版 C++實現與復雜度 分析 ....................................... 196 7.5.3 CD-AV 演示設計 .................. 200 算法國粹——秦九韶的正負開方術 與最優多項式計算算法 .................. 202 7.6.1 秦九韶的正負開方術 ........... 202 7.6.2 秦九韶的最優多項式計算 算法 ....................................... 205 習題 ......................................................... 206 參考文獻 ................................................... 207 第 8 章 算法的貪心設計方法 ........................ 209 貪心法概述 ...................................... 209 算法設計與分析——基於計算教學論的解析 - X - 8.1.1 找零錢問題、局部最優與 全局最優 ............................... 209 8.1.2 貪心法的基本特徵................ 211 圖中單源最短路徑的 Dijkstra 算法 .................................................. 213 8.2.1 最短路徑的最優子結構 性質 ....................................... 213 8.2.2 Dijkstra 算法的基本思想與 貪心選擇策略 ....................... 214 8.2.3 現代版 C++實現與復雜度 分析 ....................................... 215 8.2.4 CD-AV 演示設計 .................. 219 圖的最小生成樹的 Prim 算法 ......... 222 8.3.1 最小生成樹的最優子 結構性質 ............................... 222 8.3.2 Prim 算法的基本思想與 貪心選擇策略 ....................... 223 8.3.3 現代版 C++實現與 CD-AV 演示設計 ............................... 224 圖的最小生成樹的 Kruskal 算法 .... 225 8.4.1 Kruskal 算法的基本思想與 貪心選擇策略 ....................... 225 8.4.2 不相交集合及其 Union 與 Find 操作 ............................... 227 8.4.3 現代版 C++實現與復雜度 分析 ....................................... 228 8.4.4 CD-AV 演示設計 .................. 231 Huffman 編碼算法 ........................... 233 8.5.1 變長編碼、前綴編碼及其 滿二叉樹表示 ....................... 233 8.5.2 Huffman 編碼算法的基本 思想與復雜度分析................ 235 8.5.3 最優前綴編碼的最優子結構 性質與 Huffman 編碼算法的 貪心選擇策略 ....................... 236 8.5.4 現代版 C++實現 ................... 238 8.5.5 CD-AV 演示設計 .................. 240 算法國粹——姚期智院士的 最小生成樹算法 .............................. 242 8.6.1 算法描述 ............................... 242 8.6.2 復雜度分析 ........................... 244 習題 ......................................................... 244 參考文獻 ................................................... 245 第 9 章 算法的回溯設計方法 ........................ 247 圖的 DFS 算法 ................................. 247 9.1.1 圖及其表示 ........................... 247 9.1.2 圖的 DFS 算法、DFS 樹及 拓撲排序 ............................... 248 9.1.3 現代版 C++實現 ................... 251 9.1.4 CD-AV 演示設計 .................. 252 回溯法概述 ...................................... 254 9.2.1 回溯法基礎 ........................... 254 9.2.2 問題解的形態與回溯 算法的基本流程及相 關的節點狀態 ....................... 257 0-1 背包問題的回溯算法 ................ 258 9.3.1 約束條件和限界條件設計 ... 259 9.3.2 0-1 背包問題回溯算法的 偽代碼及運行實例 ............... 260 N-皇後問題的回溯算法 .................. 263 9.4.1 N-皇後問題的定義、解空間 分析及約束條件設計 ........... 263 9.4.2 現代版 C++實現 ................... 265 9.4.3 CD-AV 演示設計 .................. 266 K-著色問題的回溯算法 .................. 268 9.5.1 圖著色問題的定義與分析 ... 268 9.5.2 K-著色問題的回溯算法 設計 ....................................... 270 9.5.3 現代版 C++實現 ................... 270 9.5.4 CD-AV 演示設計 .................. 272 算法國粹——線性方程組的 消元求解法 ...................................... 274 9.6.1 中國古代數學家對線性 方程組消元求解法的探索 ... 274 9.6.2 線性方程組求解的高斯 消元法 ................................... 276 習題 ......................................................... 277 參考文獻 ................................................... 278 第 10 章 算法的分支限界設計方法 .............. 280 目錄 - XI - 圖的廣度優先搜索 ........................ 280 10.1.1 圖的 BFS 算法 .................... 280 10.1.2 現代版 C++實現 ................. 282 10.1.3 CD-AV 演示設計 ................ 282 分支限界法概述 ............................ 283 10.2.1 分支限界算法設計的 基本要領 ............................. 283 10.2.2 兩類分支限界法 ................. 284 0-1 背包問題的分支限界算法 ...... 286 10.3.1 約束條件和限界函數設計.... 286 10.3.2 現代版 C++實現 ................. 287 10.3.3 CD-AV 演示設計 ................ 289 TSP 問題的分支限界算法 ............. 292 10.4.1 TSP 問題與哈密爾頓迴路 ... 292 10.4.2 費用矩陣及其歸約矩陣上的 哈密爾頓迴路 ..................... 293 10.4.3 基於費用矩陣歸約的 TSP 問題的分支限界條件設計... 295 10.4.4 現代版 C++實現 ................. 299 10.4.5 CD-AV 演示設計 ................ 303 算法國粹——內插法與招差術 ..... 306 10.5.1 中國古代數學家對內插法與 招差術的探索 ..................... 306 10.5.2 現代插值法 ......................... 309 習題 .......................................................... 311 參考文獻 ................................................... 312 第 11 章 RSA 算法 ......................................... 313 公鑰密碼學基礎 ............................ 313 11.1.1 凱撒加密 .............................. 313 11.1.2 對稱密鑰體制 ...................... 314 11.1.3 公鑰密碼學簡介 .................. 315 模冪運算的反復平方算法 ............. 317 11.2.1 模運算基礎 .......................... 317 11.2.2 模冪運算的反復平方表示與 算法 ..................................... 318 模同餘、模的乘法逆元及擴展 Euclid GCD 算法 ........................... 320 11.3.1 模同餘的定義及其 運算性質 ............................. 320 11.3.2 模的乘法逆元及 擴展 Euclid GCD 算法 ....... 322 Miller-Rabin 素性測試算法 .......... 324 11.4.1 關於素數的定理 ................. 324 11.4.2 費馬小定理及相關的素性 測試算法 ............................. 326 11.4.3 Miller-Rabin 素性測試算法 詳解 ..................................... 328 RSA 算法的基本原理與實現 ........ 331 11.5.1 RSA 算法的基本原理 ......... 331 11.5.2 現代版 C++實現 ................. 333 11.5.3 CD-AV 演示設計 ................ 335 算法國粹——中國餘數算法 ......... 339 11.6.1 《孫子算經》中的中國 餘數算法 ............................. 339 11.6.2 秦九韶關於中國餘數算法的 普適設計 ............................. 340 11.6.3 中國餘數算法的現代版 C++ 實現及 CD-AV 演示設計 ... 341 11.6.4 中國餘數算法在加快 RSA 解密運算中的應用 ............. 343 習題 ......................................................... 345 參考文獻 ................................................... 346 第 12 章 NP 理論............................................ 348 算法不可解的問題 ........................ 348 12.1.1 停機問題的不可計算性 ..... 348 12.1.2 希爾伯特第十問題的 不可計算性 ......................... 349 易解問題與難解問題、NP 理論 基礎 ................................................ 350 12.2.1 易解問題與難解問題 ......... 350 12.2.2 NP 理論基礎 ....................... 351 NP 完全性理論 .............................. 356 12.3.1 判定性問題的多項式 時間歸約 ............................. 356 12.3.2 通過定義證明的 NP 完全問題 ............................. 357 12.3.3 通過多項式歸約證明的 NP 完全問題 ....................... 360 算法設計與分析——基於計算教學論的解析 - XII - 12.3.4 問題復雜性類間的關系 ...... 365 算法國粹——姚期智院士的百萬富翁 問題 ................................................ 366 12.4.1 多方安全計算簡介 .............. 367 12.4.2 百萬富翁問題及其 求解協議 ............................. 368 習題 .......................................................... 369 參考文獻 ................................................... 370 附錄：教材算法的現代版 C++實現及 計算教學論簡介 .................................... 372 附錄 1-1 Euclid GCD 算法 .................... 372 附錄 2-1 洗牌算法 ................................. 373 附錄 2-2 順序搜索算法 ......................... 374 附錄 4-1 子集遍歷問題的遞歸窮舉 算法 ......................................... 374 附錄 4-2 全排列遍歷問題的遞歸窮舉 算法 ......................................... 376 附錄 5-1 冒泡排序算法 ......................... 376 附錄 5-2 插入排序算法 ......................... 377 附錄 5-3 堆排序算法 ............................. 378 附錄 6-1 歸並排序算法 ......................... 379 附錄 6-2 快速排序算法 ......................... 380 附錄 7-1 Levenshtein 編輯距離問題的 DP 算法 .................................. 381 附錄 7-2 矩陣鏈相乘問題的 DP 算法 .... 384 附錄 7-3 0-1 背包問題的 DP 算法 ....... 387 附錄 7-4 TSP 問題的 DP 算法 .............. 389 附錄 8-1 Dijkstra 最短路徑算法 ........... 392 附錄 8-2 Prim 算法 ................................ 396 附錄 8-3 Kruskal 算法 ........................... 399 附錄 8-4 Huffman 編碼算法 ................. 404 附錄 9-1 圖遍歷的 DFS 算法 ............... 408 附錄 9-2 N-皇後問題的回溯算法 ......... 410 附錄 9-3 K-著色問題的回溯算法 .......... 411 附錄 10-1 圖的 BFS 算法 ...................... 414 附錄 10-2 0-1 背包問題的分支限界 算法 ....................................... 415 附錄 10-3 TSP 問題的分支限界算法 .... 420 附錄 11-1 RSA 算法 .............................. 426 附錄 11-2 中國餘數算法 ....................... 429 附錄 12 計算教學論簡介 ...................... 431