本書從算法之美娓娓道來,沒有高深的原理,也沒有枯燥的公式,通過趣味故事引出算法問題,包含50多個(gè)實(shí)例及完美圖解,結(jié)合學(xué)生提問,分析算法本質(zhì),并給出代碼實(shí)現(xiàn)的詳細(xì)過程和運(yùn)行結(jié)果。
本書的特色和價(jià)值:
(1)實(shí)例豐富,通俗易懂
(2)完美圖解,簡單有趣
(3)深入淺出,透析本質(zhì)
(4)實(shí)戰(zhàn)演練,循序漸進(jìn)
(5)網(wǎng)絡(luò)資源,技術(shù)支持
陳小玉,副教授,碩士,高級程序員,研究方向:智能計(jì)算、機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘。主講《數(shù)據(jù)結(jié)構(gòu)》、《算法設(shè)計(jì)與分析》、《人工智能》等專業(yè)課程,并發(fā)表過多篇計(jì)算機(jī)專業(yè)論文和項(xiàng)目。
第1章 算法之美 1
1.1 打開算法之門 2
1.2 妙不可言—算法復(fù)雜性 2
1.3 美不勝收—魔鬼序列 9
1.4 靈魂之交—馬克思手稿中的數(shù)學(xué)題 16
1.5 算法學(xué)習(xí)瓶頸 21
1.6 你怕什么 22
第2章 貪心算法 24
2.1 人之初,性本貪 25
2.1.1 貪心本質(zhì) 25
2.1.2 貪亦有道 26
2.1.3 貪心算法秘籍 26
2.2 加勒比海盜船—最優(yōu)裝載問題 27
2.2.1 問題分析 27
2.2.2 算法設(shè)計(jì) 28
2.2.3 完美圖解 28
2.2.4 偽代碼詳解 29
2.2.5 實(shí)戰(zhàn)演練 30
2.2.6 算法解析及優(yōu)化拓展 31
2.3 阿里巴巴與四十大盜—背包問題 32
2.3.1 問題分析 32
2.3.2 算法設(shè)計(jì) 33
2.3.3 完美圖解 33
2.3.4 偽代碼詳解 34
2.3.5 實(shí)戰(zhàn)演練 35
2.3.6 算法解析及優(yōu)化拓展 36
2.4 高級鐘點(diǎn)秘書—會(huì)議安排 37
2.4.1 問題分析 38
2.4.2 算法設(shè)計(jì) 39
2.4.3 完美圖解 40
2.4.4 偽代碼詳解 41
2.4.5 實(shí)戰(zhàn)演練 42
2.4.6 算法解析及優(yōu)化拓展 45
2.5 一場說走就走的旅行—最短路徑 45
2.5.1 問題分析 46
2.5.2 算法設(shè)計(jì) 46
2.5.3 完美圖解 47
2.5.4 偽代碼詳解 51
2.5.5 實(shí)戰(zhàn)演練 52
2.5.6 算法解析及優(yōu)化拓展 55
2.6 神秘電報(bào)密碼—哈夫曼編碼 59
2.6.1 問題分析 60
2.6.2 算法設(shè)計(jì) 62
2.6.3 完美圖解 63
2.6.4 偽代碼詳解 65
2.6.5 實(shí)戰(zhàn)演練 74
2.6.6 算法解析及優(yōu)化拓展 77
2.7 溝通無限校園網(wǎng)—最小生成樹 77
2.7.1 問題分析 78
2.7.2 算法設(shè)計(jì) 79
2.7.3 完美圖解 80
2.7.4 偽代碼詳解 87
2.7.5 實(shí)戰(zhàn)演練 88
2.7.6 算法解析 90
2.7.7 算法優(yōu)化拓展 90
第3章 分治法 99
3.1 山高皇帝遠(yuǎn) 100
3.1.1 治眾如治寡—分而治之 100
3.1.2 天時(shí)地利人和—分治算法要素 100
3.1.3 分治算法秘籍 101
3.2 猜數(shù)游戲—二分搜索技術(shù) 101
3.2.1 問題分析 101
3.2.2 算法設(shè)計(jì) 102
3.2.3 完美圖解 102
3.2.4 偽代碼詳解 103
3.2.5 實(shí)戰(zhàn)演練 104
3.2.6 算法解析與拓展 105
3.3 合久必分,分久必合—合并排序 107
3.3.1 問題分析 108
3.3.2 算法設(shè)計(jì) 108
3.3.3 完美圖解 108
3.3.4 偽代碼詳解 108
3.3.5 實(shí)戰(zhàn)演練 111
3.3.6 算法解析與拓展 112
3.4 兵貴神速—快速排序 113
3.4.1 問題分析 114
3.4.2 算法設(shè)計(jì) 115
3.4.3 完美圖解 116
3.4.4 偽代碼詳解 117
3.4.5 實(shí)戰(zhàn)演練 118
3.4.6 算法解析與拓展 120
3.5 效率至上—大整數(shù)乘法 124
3.5.1 問題分析 124
3.5.2 算法設(shè)計(jì) 125
3.5.3 完美圖解 126
3.5.4 偽代碼詳解 128
3.5.5 實(shí)戰(zhàn)演練 132
3.5.6 算法解析與拓展 135
3.6 分治算法復(fù)雜度求解秘籍 137
第4章 動(dòng)態(tài)規(guī)劃 141
4.1 神奇的兔子序列 142
4.2 動(dòng)態(tài)規(guī)劃基礎(chǔ) 143
4.2.1 算法思想 143
4.2.2 算法要素 143
4.2.3 解題秘籍 143
4.3 孩子有多像爸爸—最長的公共子序列 145
4.3.1 問題分析 145
4.3.2 算法設(shè)計(jì) 147
4.3.3 完美圖解 148
4.3.4 偽代碼詳解 152
4.3.5 實(shí)戰(zhàn)演練 153
4.3.6 算法解析及優(yōu)化拓展 155
4.4 DNA基因鑒定—編輯距離 156
4.4.1 問題分析 156
4.4.2 算法設(shè)計(jì) 158
4.4.3 完美圖解 159
4.4.4 偽代碼詳解 161
4.4.5 實(shí)戰(zhàn)演練 162
4.4.6 算法解析及優(yōu)化拓展 163
4.5 長江一日游—游艇租賃 164
4.5.1 問題分析 164
4.5.2 算法設(shè)計(jì) 166
4.5.3 完美圖解 166
4.5.4 偽代碼詳解 170
4.5.5 實(shí)戰(zhàn)演練 171
4.5.6 算法解析及優(yōu)化拓展 172
4.6 快速計(jì)算—矩陣連乘 172
4.6.1 問題分析 173
4.6.2 算法設(shè)計(jì) 176
4.6.3 完美圖解 176
4.6.4 偽代碼詳解 180
4.6.5 實(shí)戰(zhàn)演練 181
4.6.6 算法解析及優(yōu)化拓展 182
4.7 切呀切披薩—最優(yōu)三角剖分 183
4.7.1 問題分析 183
4.7.2 算法設(shè)計(jì) 186
4.7.3 完美圖解 187
4.7.4 偽代碼詳解 191
4.7.5 實(shí)戰(zhàn)演練 192
4.7.6 算法解析及優(yōu)化拓展 194
4.8 小石子游戲—石子合并 194
4.8.1 問題分析 195
4.8.2 算法設(shè)計(jì) 197
4.8.3 完美圖解 198
4.8.4 偽代碼詳解 203
4.8.5 實(shí)戰(zhàn)演練 205
4.8.6 算法解析及優(yōu)化拓展 206
4.9 大賣場購物車1—0-1背包問題 209
4.9.1 問題分析 210
4.9.2 算法設(shè)計(jì) 211
4.9.3 完美圖解 212
4.9.4 偽代碼詳解 216
4.9.5 實(shí)戰(zhàn)演練 217
4.9.6 算法解析及優(yōu)化拓展 218
4.10 快速定位—最優(yōu)二叉搜索樹 220
4.10.1 問題分析 221
4.10.2 算法設(shè)計(jì) 225
4.10.3 完美圖解 226
4.10.4 偽代碼詳解 239
4.10.5 實(shí)戰(zhàn)演練 241
4.10.6 算法解析及優(yōu)化拓展 243
4.11 動(dòng)態(tài)規(guī)劃算法秘籍 246
第5章 回溯法 248
5.1 回溯法基礎(chǔ) 249
5.1.1 算法思想 249
5.1.2 算法要素 249
5.1.3 解題秘籍 251
5.2 大賣場購物車2—0-1背包問題 252
5.2.1 問題分析 252
5.2.2 算法設(shè)計(jì) 253
5.2.3 完美圖解 255
5.2.4 偽代碼詳解 258
5.2.5 實(shí)戰(zhàn)演練 259
5.2.6 算法解析 262
5.2.7 算法優(yōu)化拓展 262
5.3 部落護(hù)衛(wèi)隊(duì)—最大團(tuán) 265
5.3.1 問題分析 266
5.3.2 算法設(shè)計(jì) 267
5.3.3 完美圖解 269
5.3.4 偽代碼詳解 274
5.3.5 實(shí)戰(zhàn)演練 275
5.3.6 算法解析及優(yōu)化拓展 277
5.4 地圖調(diào)色板—地圖著色 278
5.4.1 問題分析 278
5.4.2 算法設(shè)計(jì) 279
5.4.3 完美圖解 280
5.4.4 偽代碼詳解 285
5.4.5 實(shí)戰(zhàn)演練 286
5.4.6 算法解析及優(yōu)化拓展 288
5.5 一山不容二虎—n皇后問題 289
5.5.1 問題分析 290
5.5.2 算法設(shè)計(jì) 291
5.5.3 完美圖解 292
5.5.4 偽代碼詳解 300
5.5.5 實(shí)戰(zhàn)演練 301
5.5.6 算法解析及優(yōu)化拓展 303
5.6 機(jī)器零件加工—最優(yōu)加工順序 305
5.6.1 問題分析 305
5.6.2 算法設(shè)計(jì) 308
5.6.3 完美圖解 308
5.6.4 偽代碼詳解 313
5.6.5 實(shí)戰(zhàn)演練 314
5.6.6 算法解析 316
5.6.7 算法優(yōu)化拓展 316
5.7 奇妙之旅1—旅行商問題 319
5.7.1 問題分析 319
5.7.2 算法設(shè)計(jì) 320
5.7.3 完美圖解 321
5.7.4 偽代碼詳解 330
5.7.5 實(shí)戰(zhàn)演練 331
5.7.6 算法解析及優(yōu)化拓展 333
5.8 回溯法算法秘籍 336
第6章 分支限界法 338
6.1 橫行天下—廣度優(yōu)先 339
6.1.1 算法思想 340
6.1.2 算法步驟 340
6.1.3 解題秘籍 341
6.2 大賣場購物車3—0-1背包問題 341
6.2.1 問題分析 342
6.2.2 算法設(shè)計(jì) 343
6.2.3 完美圖解 345
6.2.4 偽代碼詳解 350
6.2.5 實(shí)戰(zhàn)演練 352
6.2.6 算法解析 355
6.2.7 算法優(yōu)化拓展—優(yōu)先隊(duì)列式分支限界法 356
6.3 奇妙之旅2—旅行商問題 366
6.3.1 問題分析 366
6.3.2 算法設(shè)計(jì) 367
6.3.3 完美圖解 368
6.3.4 偽代碼詳解 371
6.3.5 實(shí)戰(zhàn)演練 373
6.3.6 算法解析 376
6.3.7 算法優(yōu)化拓展 377
6.4 鋪設(shè)電纜—最優(yōu)工程布線 385
6.4.1 問題分析 386
6.4.2 算法設(shè)計(jì) 386
6.4.3 完美圖解 387
6.4.4 偽代碼詳解 399
6.4.5 實(shí)戰(zhàn)演練 400
6.4.6 算法解析及優(yōu)化拓展 403
6.5 回溯法與分支限界法的異同 404
第7章 線性規(guī)劃網(wǎng)絡(luò)流 405
7.1 線性規(guī)劃問題 406
7.1.1 線性規(guī)劃標(biāo)準(zhǔn)型 408
7.1.2 單純形算法圖解 409
7.1.3 解題秘籍 413
7.1.4 練習(xí) 413
7.2 工廠最大效益—單純形算法 414
7.2.1 問題分析 414
7.2.2 完美圖解 415
7.2.3 偽代碼詳解 418
7.2.4 實(shí)戰(zhàn)演練 420
7.2.5 算法解析及優(yōu)化拓展 423
7.3 最大網(wǎng)絡(luò)流—最短增廣路算法 424
7.3.1 問題分析 424
7.3.2 增廣路算法 427
7.3.3 完美圖解 431
7.3.4 偽代碼詳解 437
7.3.5 實(shí)戰(zhàn)演練 439
7.3.6 算法解析 441
7.3.7 算法優(yōu)化拓展—重貼標(biāo)簽算法ISAP 442
7.4 最小費(fèi)用最大流—最小費(fèi)用路算法 455
7.4.1 問題分析 456
7.4.2 算法設(shè)計(jì) 456
7.4.3 完美圖解 457
7.4.4 偽代碼詳解 459
7.4.5 實(shí)戰(zhàn)演練 461
7.4.6 算法解析 465
7.4.7 算法優(yōu)化拓展—消圈算法 466
7.5 精明的老板—配對方案問題 468
7.5.1 問題分析 468
7.5.2 算法設(shè)計(jì) 469
7.5.3 完美圖解 469
7.5.4 偽代碼詳解 470
7.5.5 實(shí)戰(zhàn)演練 471
7.5.6 算法解析 475
7.5.7 算法優(yōu)化拓展—匈牙利算法 475
7.6 國際會(huì)議交流—圓桌問題 480
7.6.1 問題分析 481
7.6.2 算法設(shè)計(jì) 482
7.6.3 完美圖解 482
7.6.4 偽代碼詳解 484
7.6.5 實(shí)戰(zhàn)演練 485
7.6.6 算法解析及優(yōu)化拓展 489
7.7 要考試?yán)病囶}庫問題 489
7.7.1 問題分析 490
7.7.2 算法設(shè)計(jì) 490
7.7.3 完美圖解 491
7.7.4 偽代碼詳解 493
7.7.5 實(shí)戰(zhàn)演練 494
7.7.6 算法解析及優(yōu)化拓展 498
7.8 太空實(shí)驗(yàn)計(jì)劃—最大收益問題 499
7.8.1 問題分析 499
7.8.2 算法設(shè)計(jì) 500
7.8.3 完美圖解 502
7.8.4 偽代碼詳解 505
7.8.5 實(shí)戰(zhàn)演練 506
7.8.6 算法解析及優(yōu)化拓展 510
7.9 央視娛樂節(jié)目購物街—方格取數(shù)問題 511
7.9.1 問題分析 511
7.9.2 算法設(shè)計(jì) 512
7.9.3 完美圖解 513
7.9.4 偽代碼詳解 514
7.9.5 實(shí)戰(zhàn)演練 516
7.9.6 算法解析及優(yōu)化拓展 520
7.10 走著走著,就走到了西藏—旅游路線問題 521
7.10.1 問題分析 521
7.10.2 算法設(shè)計(jì) 523
7.10.3 完美圖解 523
7.10.4 偽代碼詳解 525
7.10.5 實(shí)戰(zhàn)演練 528
7.10.6 算法解析及優(yōu)化拓展 532
7.11 網(wǎng)絡(luò)流問題解題秘籍 533
附錄A 特征方程和通項(xiàng)公式 534
附錄B sort函數(shù) 537
附錄C 優(yōu)先隊(duì)列 541
附錄D 鄰接表 549
附錄E 并查集 555
附錄F 四邊不等式 561
附錄G 排列樹 565
附錄H 貝爾曼規(guī)則 579
附錄I 增廣路中稱為關(guān)鍵邊的次數(shù) 582
附錄J 最大流最小割定理 585