《程式設計算法基礎》是2023年清華大學出版社出版的圖書，作者：喻梅、於瑞國 主編；李雪威、趙滿坤 副主編。
基本介紹
- 中文名：程式設計算法基礎
- 作者：喻梅、於瑞國 主編；李雪威、趙滿坤 副主編
- 出版時間：2023年7月1日
- 出版社：清華大學出版社
- ISBN：9787302618560
- 定價：79.90 元
內容簡介,圖書目錄,
內容簡介
本書所介紹的內容均為程式設計的基礎算法，包括程式設計基礎知識、基礎算法、基礎數據結構、搜尋、圖論、字元串、動態規劃、初等數論、計算幾何等內容，結合實際問題，講解使用基礎算法進行問題求解的思路、方法，給出示例代碼。
圖書目錄
目錄
第 1章基礎算法 ....................................1
1.1枚舉 ..........................................1
1.2模擬 ..........................................4
1.3遞歸 ..........................................7
1.4分治基礎 ...................................9
1.5貪心 ........................................16
1.6排序 ........................................ 20
第 2章基礎數據結構 ........................... 24
2.1棧和佇列 ................................. 24
2.2堆 ........................................... 27
2.3並查集..................................... 30
2.4前綴和與差分........................... 35
2.5樹狀數組 ................................. 38
2.6線段樹..................................... 41
2.7 ST表....................................... 46
2.8分塊 ........................................ 48
2.9莫隊算法 ................................. 52
第 3章搜尋 ......................................... 57
3.1深度優先搜尋........................... 57
3.2寬度優先搜尋........................... 58
3.3搜尋最佳化策略........................... 62
3.3.1雙向廣搜 ....................... 62
3.3.2剪枝 .............................. 64
3.3.3記憶化搜尋 .................... 66
3.3.4疊代加深搜尋.................68
3.4 A. ........................................... 70
第 4章圖論 ......................................... 74
4.1圖論基礎 ................................. 74
4.1.1度和路徑 ....................... 74
4.1.2圖的定義 ....................... 74
4.1.3存儲結構 ....................... 74
4.1.4樹的直徑 ....................... 75
4.1.5歐拉迴路 ....................... 76
4.1.6哈密爾頓迴路................. 77
4.2最近公共祖先........................... 79
4.2.1 Tarjan法 ........................ 79
4.2.2倍增法........................... 79
4.2.3樹鏈剖分法 .................... 80
4.3生成樹..................................... 80
4.3.1 Prim算法 ...................... 80
4.3.2 Kruskal算法 .................. 81
4.3.3次小生成樹 .................... 84
4.3.4矩陣樹定理 .................... 87
4.4最短路問題 .............................. 90
4.4.1 Dijkstra..........................90
4.4.2 Bellman-Ford..................90
4.4.3 SPFA.............................91
4.4.4 Floyd.............................91
4.5次短路與 k短路 ....................... 96
4.6差分約束問題........................... 99
4.7拓撲排序 ................................101
4.8連通性問題 .............................102
4.8.1強連通分量 ...................102
4.8.2 2-SAT問題 ...................103
4.8.3割點與割邊 ...................104
4.9圖的匹配問題..........................111
4.9.1二分圖最大匹配 ............111
4.9.2二分圖最大權匹配 .........113
4.9.3一般圖最大匹配 ............115
4.10支配樹 ..................................118
第 5章高級數據結構 ..........................122
5.1樹鏈剖分 ................................122
5.2可持久化數據結構 ...................127
5.2.1主席樹..........................127
5.2.2可持久化 trie.................131
5.3虛樹 .......................................133
5.4平衡樹....................................137
5.4.1 Treap............................137
5.4.2伸展樹..........................141
5.5動態樹....................................148
5.6數據結構的嵌套 ......................152
5.7 K-Dimensional樹 .....................156
第 6章網路流 ....................................162
6.1最大流....................................162
6.1.1網路流概述 ...................162
6.1.2殘餘網路與增廣路 .........163
6.1.3 Ford-Fulkerson算法 .......163
6.1.4最小割最大流定理 .........164
6.1.5 Dinic算法.....................165
6.2費用流....................................174
6.3上下界網路流..........................178
6.3.1無源匯上下界可行流......178
6.3.2有源匯上下界網路流......179
6.4常見模型 ................................180
6.4.1混合圖歐拉迴路 ............180
6.4.2 最大權閉合子圖 ............181
6.4.3 動態加點 ......................181
第 7章動態規劃 .................................183
7.1動態規劃基礎..........................183
7.1.1 線性動態規劃................183
7.1.2 多維動態規劃................188
7.2背包問題 ................................195
7.2.1 01背包.........................195
7.2.2 完全背包 ......................199
7.2.3 多重背包 ......................203
7.3狀態壓縮動態規劃 ...................205
7.4區間動態規劃..........................210
7.5樹形動態規劃..........................214
7.6數位動態規劃..........................219
7.7機率期望動態規劃 ...................224
7.8插頭動態規劃..........................229
7.9動態規劃的最佳化 ......................234
7.9.1 四邊形不等式最佳化 .........234
7.9.2 斜率最佳化 ......................238
7.9.3 數據結構最佳化................240
7.10動態規劃例題 ........................245
第 8章分治 ........................................255
8.1二分答案 ................................255
8.2快速冪....................................260
8.3 CDQ分治 ...............................263
8.4整體二分 ................................268
8.5樹分治....................................273
第 9章數學 ........................................278
9.1數學基礎 ................................278
9.1.1 組合數學基礎................278
9.1.2 線性代數基礎................280
9.1.3 數論基礎 ......................284
9.1.4 素數 .............................287
9.2同餘式....................................289
9.2.1 同餘方程 ......................289
9.2.2 逆元 .............................290
9.2.3 歐拉公式 ......................291
9.2.4 歐拉降冪 ......................291
9.2.5 中國剩餘定理................292
9.2.6 擴展中國剩餘定理 .........293
9.2.7 盧卡斯定理與擴展盧卡斯..........................293
9.2.8 非對稱加密—— RSA算法......................295
9.3數論函式 ................................296
9.3.1 積性函式 ......................296
9.3.2 狄利克雷卷積................296
9.3.3 莫比烏斯函式................297
9.3.4 莫比烏斯反演................298
9.3.5 杜教篩..........................300
9.3.6 Min_25篩.....................303
9.4數列 .......................................308
9.4.1 卡特蘭數 ......................308
9.4.2 斐波那契數列................309
9.4.3 伯努利數列 ...................314
9.5多項式理論 .............................317
9.5.1 傅立葉變換 ...................317
9.5.2 原根 .............................322
9.5.3 快速數論變換................323
9.5.4 生成函式 ......................323
9.6簡單博弈 ................................336
9.6.1 組合博弈模型及變形......336
9.6.2 SG函式和 SG定理 ........344
第 10章字元串...................................347
10.1 Hash算法..............................347
10.2最小循環表示 ........................350
10.3 Lyndon分解 ..........................352
10.4 Manacher算法 .......................355
10.5回文自動機 ...........................357
10.6 KMP算法 .............................364
10.7擴展 KMP算法......................371
10.8字典樹 ..................................376
10.9 AC自動機.............................380
10.10後綴數組 .............................389
10.11後綴自動機..........................395
第 11章計算幾何 ...............................407
11.1計算幾何基礎 ........................407
11.1.1 幾何元素定義.............407
11.1.2 向量的基本運算 .........408
11.1.3 幾何元素間的位置關係..........................411
11.2凸包 .....................................416
11.3半平面交...............................418
11.4旋轉卡殼...............................423
11.5三維幾何...............................427
11.5.1 三維幾何基礎.............427
11.5.2 三維凸包 ...................429
參考文獻 ..............................................433
