目 錄 第1章 算法概述 1 算法分析題1 1 1-1 函數(shù)的漸近表達(dá)式 1 1-2 O(1)和O(2)的區(qū)別 1 1-3 按漸近階排列表達(dá)式 1 1-4 算法效率 1 1-5 硬件效率 1 1-6 函數(shù)漸近階 2 1-7 n!的階 2 1-8 3n+1問(wèn)題 2 1-9 平均情況下的計(jì)算時(shí)間復(fù)雜性 2 算法實(shí)現(xiàn)題1 3 1-1 統(tǒng)計(jì)數(shù)字問(wèn)題 3 1-2 字典序問(wèn)題 4 1-3 最多約數(shù)問(wèn)題 4 1-4 金幣陣列問(wèn)題 6 1-5 最大間隙問(wèn)題 8 第2章 遞歸與分治策略 11 算法分析題2 11 2-1 證明Hanoi塔問(wèn)題的遞歸算法與非遞歸算法實(shí)際上是一回事 11 2-2 判斷這7個(gè)算法的正確性 12 2-3 改寫(xiě)二分搜索算法 15 2-4 大整數(shù)乘法的O(nmlog(3/2))算法 16 2-5 5次n/3位整數(shù)的乘法 16 2-6 矩陣乘法 18 2-7 多項(xiàng)式乘積 18 2-8 O(1)空間子數(shù)組換位算法 19 2-9 O(1)空間合并算法 21 2-10 段合并排序算法 27 2-11 自然合并排序算法 28 2-12 第k小元素問(wèn)題的計(jì)算時(shí)間下界 29 2-13 非增序快速排序算法 31 2-14 構(gòu)造Gray碼的分治算法 31 2-15 網(wǎng)球循環(huán)賽日程表 32 2-16 二叉樹(shù)T的前序、中序和后序序列 35 算法實(shí)現(xiàn)題2 36 2-1 眾數(shù)問(wèn)題 36 2-2 馬的Hamilton周游路線(xiàn)問(wèn)題 37 2-3 半數(shù)集問(wèn)題 44 2-4 半數(shù)單集問(wèn)題 46 2-5 有重復(fù)元素的排列問(wèn)題 46 2-6 排列的字典序問(wèn)題 47 2-7 集合劃分問(wèn)題 49 2-8 集合劃分問(wèn)題 50 2-9 雙色Hanoi塔問(wèn)題 51 2-10 標(biāo)準(zhǔn)二維表問(wèn)題 52 2-11 整數(shù)因子分解問(wèn)題 53 第3章 動(dòng)態(tài)規(guī)劃 54 算法分析題3 54 3-1 最長(zhǎng)單調(diào)遞增子序列 54 3-2 最長(zhǎng)單調(diào)遞增子序列的O(nlogn)算法 54 3-3 整數(shù)線(xiàn)性規(guī)劃問(wèn)題 55 3-4 二維0-1背包問(wèn)題 56 3-5 Ackermann函數(shù) 57 算法實(shí)現(xiàn)題3 59 3-1 獨(dú)立任務(wù)最優(yōu)調(diào)度問(wèn)題 59 3-2 最優(yōu)批處理問(wèn)題 61 3-3 石子合并問(wèn)題 67 3-4 數(shù)字三角形問(wèn)題 68 3-5 乘法表問(wèn)題 69 3-6 租用游艇問(wèn)題 70 3-7 汽車(chē)加油行駛問(wèn)題 70 3-8 最小m段和問(wèn)題 71 3-9 圈乘運(yùn)算問(wèn)題 72 3-10 最大長(zhǎng)方體問(wèn)題 78 3-11 正則表達(dá)式匹配問(wèn)題 79 3-12 雙調(diào)旅行售貨員問(wèn)題 83 3-13 最大k乘積問(wèn)題 84 3-14 最少費(fèi)用購(gòu)物問(wèn)題 86 3-15 收集樣本問(wèn)題 87 3-16 最優(yōu)時(shí)間表問(wèn)題 89 3-17 字符串比較問(wèn)題 89 3-18 有向樹(shù)k中值問(wèn)題 90 3-19 有向樹(shù)獨(dú)立k中值問(wèn)題 94 3-20 有向直線(xiàn)m中值問(wèn)題 98 3-21 有向直線(xiàn)2中值問(wèn)題 101 3-22 樹(shù)的最大連通分支問(wèn)題 103 3-23 直線(xiàn)k中值問(wèn)題 105 3-24 直線(xiàn)k覆蓋問(wèn)題 109 3-25 m處理器問(wèn)題 113 第4章 貪心算法 116 算法分析題4 116 4-1 程序最優(yōu)存儲(chǔ)問(wèn)題 116 4-2 最優(yōu)裝載問(wèn)題的貪心算法 116 4-3 Fibonacci序列的哈夫曼編碼 116 4-4 最優(yōu)前綴碼的編碼序列 117 算法實(shí)現(xiàn)題4 117 4-1 會(huì)場(chǎng)安排問(wèn)題 117 4-2 最優(yōu)合并問(wèn)題 118 4-3 磁帶最優(yōu)存儲(chǔ)問(wèn)題 118 4-4 磁盤(pán)文件最優(yōu)存儲(chǔ)問(wèn)題 119 4-5 程序存儲(chǔ)問(wèn)題 120 4-6 最優(yōu)服務(wù)次序問(wèn)題 120 4-7 多處最優(yōu)服務(wù)次序問(wèn)題 121 4-8 d森林問(wèn)題 122 4-9 虛擬汽車(chē)加油問(wèn)題 123 4-10 區(qū)間覆蓋問(wèn)題 124 4-11 刪數(shù)問(wèn)題 124 4-12 磁帶最大利用率問(wèn)題 125 4-13 非單位時(shí)間任務(wù)安排問(wèn)題 126 4-14 多元Huffman編碼問(wèn)題 127 4-15 最優(yōu)分解問(wèn)題 128 第5章 回溯法 130 算法分析題5 130 5-1 裝載問(wèn)題改進(jìn)回溯法1 130 5-2 裝載問(wèn)題改進(jìn)回溯法2 131 5-3 0-1背包問(wèn)題的最優(yōu)解 132 5-4 最大團(tuán)問(wèn)題的迭代回溯法 134 5-5 旅行售貨員問(wèn)題的費(fèi)用上界 135 5-6 旅行售貨員問(wèn)題的上界函數(shù) 136 算法實(shí)現(xiàn)題5 137 5-1 子集和問(wèn)題 137 5-2 最小長(zhǎng)度電路板排列問(wèn)題 138 5-3 最小重量機(jī)器設(shè)計(jì)問(wèn)題 140 5-4 運(yùn)動(dòng)員最佳配對(duì)問(wèn)題 141 5-5 無(wú)分隔符字典問(wèn)題 142 5-6 無(wú)和集問(wèn)題 144 5-7 n色方柱問(wèn)題 145 5-8 整數(shù)變換問(wèn)題 150 5-9 拉丁矩陣問(wèn)題 151 5-10 排列寶石問(wèn)題 152 5-11 重復(fù)拉丁矩陣問(wèn)題 154 5-12 羅密歐與朱麗葉的迷宮問(wèn)題 156 5-13 工作分配問(wèn)題 158 5-14 布線(xiàn)問(wèn)題 159 5-15 最佳調(diào)度問(wèn)題 160 5-16 無(wú)優(yōu)先級(jí)運(yùn)算問(wèn)題 161 5-17 世界名畫(huà)陳列館問(wèn)題 163 5-18 世界名畫(huà)陳列館問(wèn)題（不重復(fù)監(jiān)視） 166 5-19 算m點(diǎn)問(wèn)題 169 5-20 部落衛(wèi)隊(duì)問(wèn)題 171 5-21 子集樹(shù)問(wèn)題 173 5-22 0-1背包問(wèn)題 174 5-23 排列樹(shù)問(wèn)題 176 5-24 一般解空間搜索問(wèn)題 177 5-25 最短加法鏈問(wèn)題 179 第6章 分支限界法 185 算法分析題6 185 6-1 0-1背包問(wèn)題的棧式分支限界法 185 6-2 釋放結(jié)點(diǎn)空間的隊(duì)列式分支限界法 187 6-3 及時(shí)刪除不用的結(jié)點(diǎn) 188 6-4 用最大堆存儲(chǔ)活結(jié)點(diǎn)的優(yōu)先隊(duì)列式分支限界法 189 6-5 釋放結(jié)點(diǎn)空間的優(yōu)先隊(duì)列式分支限界法 192 6-6 團(tuán)頂點(diǎn)數(shù)的上界 194 6-7 團(tuán)頂點(diǎn)數(shù)改進(jìn)的上界 194 6-8 修改解旅行售貨員問(wèn)題的分支限界法 195 6-9 試修改解旅行售貨員問(wèn)題的分支限界法，使得算法保存已產(chǎn)生的排列樹(shù) 197 6-10 電路板排列問(wèn)題的隊(duì)列式分支限界法 199 算法實(shí)現(xiàn)題6 201 6-1 最小長(zhǎng)度電路板排列問(wèn)題 201 6-2 最小權(quán)頂點(diǎn)覆蓋問(wèn)題 203 6-3 無(wú)向圖的最大割問(wèn)題 206 6-4 最小重量機(jī)器設(shè)計(jì)問(wèn)題 209 6-5 運(yùn)動(dòng)員最佳配對(duì)問(wèn)題 212 6-6 n后問(wèn)題 214 6-7 布線(xiàn)問(wèn)題 216 6-8 最佳調(diào)度問(wèn)題 218 6-9 無(wú)優(yōu)先級(jí)運(yùn)算問(wèn)題 220 6-10 世界名畫(huà)陳列館問(wèn)題 223 6-11 子集空間樹(shù)問(wèn)題 226 6-12 排列空間樹(shù)問(wèn)題 229 6-13 一般解空間的隊(duì)列式分支限界法 232 6-14 子集空間樹(shù)問(wèn)題 236 6-15 排列空間樹(shù)問(wèn)題 241 6-16 一般解空間的優(yōu)先隊(duì)列式分支限界法 246 6-17 推箱子問(wèn)題 250 第7章 概率算法 256 算法分析題7 256 7-1 模擬正態(tài)分布隨機(jī)變量 256 7-2 隨機(jī)抽樣算法 256 7-3 隨機(jī)產(chǎn)生m個(gè)整數(shù) 257 7-4 集合大小的概率算法 258 7-5 生日問(wèn)題 258 7-6 易驗(yàn)證問(wèn)題的拉斯維加斯算法 259 7-7 用數(shù)組模擬有序鏈表 260 7-8 O(n3/2)舍伍德型排序算法 260 7-9 n后問(wèn)題解的存在性 260 7-10 整數(shù)因子分解算法 262 7-11 非蒙特卡羅算法的例子 262 7-12 重復(fù)3次的蒙特卡羅算法 263 7-13 集合隨機(jī)元素算法 263 7-14 由蒙特卡羅算法構(gòu)造拉斯維加斯算法 265 7-15 產(chǎn)生素?cái)?shù)算法 265 7-16 矩陣方程問(wèn)題 265 算法實(shí)現(xiàn)題7 266 7-1 模平方根問(wèn)題 266 7-2 素?cái)?shù)測(cè)試問(wèn)題 268 7-3 集合相等問(wèn)題 269 7-4 逆矩陣問(wèn)題 269 7-5 多項(xiàng)式乘積問(wèn)題 270 7-6 皇后控制問(wèn)題 270 7-7 3-SAT問(wèn)題 274 7-8 戰(zhàn)車(chē)問(wèn)題 275 第8章 線(xiàn)性規(guī)劃與網(wǎng)絡(luò)流 278 算法分析題8 278 8-1 線(xiàn)性規(guī)劃可行區(qū)域無(wú)界的例子 278 8-2 單源最短路與線(xiàn)性規(guī)劃 278 8-3 網(wǎng)絡(luò)最大流與線(xiàn)性規(guī)劃 279 8-4 最小費(fèi)用流與線(xiàn)性規(guī)劃 279 8-5 運(yùn)輸計(jì)劃問(wèn)題 279 8-6 單純形算法 280 8-7 邊連通度問(wèn)題 281 8-8 有向無(wú)環(huán)網(wǎng)絡(luò)的最大流 281 8-9 無(wú)向網(wǎng)絡(luò)的最大流 281 8-10 最大流更新算法 282 8-11 混合圖歐拉回路問(wèn)題 282 8-12 單源最短路與最小費(fèi)用流 282 8-13 中國(guó)郵路問(wèn)題 282 算法實(shí)現(xiàn)題8 283 8-1 飛行員配對(duì)方案問(wèn)題 283 8-2 太空飛行計(jì)劃問(wèn)題 284 8-3 最小路徑覆蓋問(wèn)題 285 8-4 魔術(shù)球問(wèn)題 286 8-5 圓桌問(wèn)題 287 8-6 最長(zhǎng)遞增子序列問(wèn)題 287 8-7 試題庫(kù)問(wèn)題 290 8-8 機(jī)器人路徑規(guī)劃問(wèn)題 291 8-9 方格取數(shù)問(wèn)題 294 8-10 餐巾計(jì)劃問(wèn)題 298 8-11 航空路線(xiàn)問(wèn)題 299 8-12 軟件補(bǔ)丁問(wèn)題 300 8-13 星際轉(zhuǎn)移問(wèn)題 301 8-14 孤島營(yíng)救問(wèn)題 302 8-15 汽車(chē)加油行駛問(wèn)題 304 8-16 數(shù)字梯形問(wèn)題 307 8-17 運(yùn)輸問(wèn)題 311 8-18 分配工作問(wèn)題 314 8-19 負(fù)載平衡問(wèn)題 315 8-20 最長(zhǎng)k可重區(qū)間集問(wèn)題 317 8-21 最長(zhǎng)k可重線(xiàn)段集問(wèn)題 319 第9章 串與序列的算法 323 算法分析題9 323 9-1 簡(jiǎn)單子串搜索算法最壞情況復(fù)雜性 323 9-2 后綴重疊問(wèn)題 323 9-3 改進(jìn)前綴函數(shù) 323 9-4 確定所有匹配位置的KMP算法 324 9-5 特殊情況下簡(jiǎn)單子串搜索算法的改進(jìn) 325 9-6 簡(jiǎn)單子串搜索算法的平均性能 325 9-7 帶間隙字符的模式串搜索 326 9-8 串接的前綴函數(shù) 326 9-9 串的循環(huán)旋轉(zhuǎn) 327 9-10 失敗函數(shù)性質(zhì) 327 9-11 輸出函數(shù)性質(zhì) 328 9-12 后綴數(shù)組類(lèi) 328 9-13 最長(zhǎng)公共擴(kuò)展查詢(xún) 329 9-14 最長(zhǎng)公共擴(kuò)展性質(zhì) 332 9-15 后綴數(shù)組性質(zhì) 333 9-16 后綴數(shù)組搜索 334 9-17 后綴數(shù)組快速搜索 335 算法實(shí)現(xiàn)題9 338 9-1 安全基因序列問(wèn)題 338 9-2 最長(zhǎng)重復(fù)子串問(wèn)題 342 9-3 最長(zhǎng)回文子串問(wèn)題 343 9-4 相似基因序列性問(wèn)題 344 9-5 計(jì)算機(jī)病毒問(wèn)題 345 9-6 帶有子串包含約束的最長(zhǎng)公共子序列問(wèn)題 347 9-7 多子串排斥約束的最長(zhǎng)公共子序列問(wèn)題 349 參考文獻(xiàn) 351