程序設(shè)計(jì)競(jìng)賽訓(xùn)練營(yíng)：算法與實(shí)踐

定　價(jià)：￥99.90

作　者：	邱秋
出版社：	人民郵電出版社
叢編項(xiàng)：
標(biāo)　簽：	暫缺

購(gòu)買這本書(shū)可以去

ISBN：	9787115579843	出版時(shí)間：	2022-03-01	包裝：	平裝-膠訂
開(kāi)本：	128開(kāi)	頁(yè)數(shù)：	346	字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

　　本書(shū)是以大學(xué)生程序設(shè)計(jì)競(jìng)賽為基礎(chǔ)、面向已有C1 入門知識(shí)且想要進(jìn)一步學(xué)習(xí)的讀者編寫的 C 進(jìn)階訓(xùn)練指南。全書(shū)分為回湖法、圖、動(dòng)態(tài)規(guī)劃、網(wǎng)格等部分?；睾ú糠纸榻B單向搜索和雙向搜索，給出高級(jí)搜索的技巧；圖部分分為圖遍歷和圖算法章節(jié)，先介紹圖遍歷的方法，再以小生成樹(shù)問(wèn)題、單源短路徑問(wèn)題、多源短路徑問(wèn)題、網(wǎng)絡(luò)流問(wèn)題中的經(jīng)典算法為例，介紹了十余種算法的原理和相關(guān)應(yīng)用；動(dòng)態(tài)規(guī)劃部分逐一介紹了集合型、區(qū)間型、圖論型、概率型、非典型動(dòng)態(tài)規(guī)劃，并介紹了空間、時(shí)間上的優(yōu)化技巧，以及相應(yīng)的備忘、松弛技巧；網(wǎng)格部分作為獨(dú)立的專題匯集了與網(wǎng)格相關(guān)的各種習(xí)題本書(shū)適合有意參加大學(xué)生程序設(shè)計(jì)競(jìng)賽的本科生、研究生閱讀，對(duì)有意參加信息學(xué)奧林匹克競(jìng)賽的中學(xué)生具有參考價(jià)值。

作者簡(jiǎn)介

　　邱秋，自學(xué)計(jì)算機(jī)技術(shù)，并于2004年和2006年分別取得了全國(guó)計(jì)算機(jī)技術(shù)與軟件專業(yè)技術(shù)資格考試中的程序員和軟件工程師的證書(shū)。對(duì)數(shù)據(jù)庫(kù)技術(shù)感興趣，在住院醫(yī)師實(shí)習(xí)期間曾幫助科室開(kāi)發(fā)了一款對(duì)腎衰竭腹膜透析患者進(jìn)行健康隨訪的軟件，在工作期間開(kāi)發(fā)了數(shù)字營(yíng)區(qū)、局域網(wǎng)考核等軟件。愛(ài)好算法，酷愛(ài)讀書(shū)。博客：https：//blog.csdn.net/metaphysis

圖書(shū)目錄

第 1章回溯法 1
1.1　八皇后問(wèn)題　1
1.2　搜索　10
1.2.1　單向搜索　10
1.2.2　雙向搜索　16
1.3　剪枝　17
1.3.1　正方形剖分　26
1.3.2　關(guān)燈問(wèn)題　27
1.4　15數(shù)碼問(wèn)題　29
1.5　小結(jié)　38
第　2章圖遍歷　39
2.1　基本概念　39
2.1.1　圖的屬性　39
2.1.2　歐拉公式　40
2.1.3　路與連通　40
2.2　圖的表示　41
2.2.1　鄰接矩陣　41
2.2.2　邊列表和前向星　41
2.2.3　鄰接表　42
2.2.4　鏈?zhǔn)角跋蛐恰?3
2.3　圖遍歷　44
2.3.1　廣度優(yōu)先遍歷　44
2.3.2　深度優(yōu)先遍歷　50
2.4　圖遍歷的應(yīng)用　53
2.4.1　圖的連通性　53
2.4.2　短路徑　54
2.4.3　長(zhǎng)簡(jiǎn)單路徑　56
2.4.4　圖的著色　57
2.4.5　近公共祖先　57
2.4.6　割頂　65
2.4.7　割邊　68
2.4.8　強(qiáng)連通分支　70
2.4.9　半連通分支　77
2.4.10　2-SAT　78
2.4.11　圖的直徑　83
2.4.12　樹(shù)的重心　84
2.5　拓?fù)渑判颉?5
2.6　小結(jié)　87
第3章　圖算法　89
3.1　基本概念　89
3.2　圖的回路　90
3.2.1　歐拉回　90
3.2.2　中國(guó)投遞員問(wèn)題　104
3.2.3　哈密頓回　105
3.2.4　旅行商問(wèn)題　107
3.3　小生成樹(shù)　107
3.3.1　Prim算法　107
3.3.2　Kruskal算法　109
3.3.3　小生成樹(shù)的擴(kuò)展問(wèn)題　111
3.3.4　度限制小生成樹(shù)　111
3.3.5　次小生成樹(shù)　114
3.4　短路徑問(wèn)題　118
3.4.1　Moore-Dijkstra算法　118
3.4.2　Bellman-Ford算法　126
3.4.3　Floyd-Warshall算法　130
3.4.4　傳遞閉包　132
3.4.5　小化的距離　134
3.4.6　差分約束系統(tǒng)　134
3.4.7　第K短路徑問(wèn)題　138
3.5　網(wǎng)絡(luò)流問(wèn)題　140
3.5.1　基本概念　141
3.5.2　Ford-Fulkerson方法　142
3.5.3　Edmonds-Karp算法　144
3.5.4　Dinic算法　149
3.5.5　ISAP算法　153
3.5.6　小截問(wèn)題　158
3.5.7　小費(fèi)用流問(wèn)題　159
3.6　邊獨(dú)立集與二部圖匹配　161
3.6.1　網(wǎng)絡(luò)流解法　162
3.6.2　Hungarian算法　164
3.6.3　Hopcroft-Karp算法　169
3.6.4　Gale-Shapley算法　171
3.6.5　Edmonds算法　172
3.7　二部圖加權(quán)完備匹配　176
3.7.1　網(wǎng)絡(luò)流解法　176
3.7.2　Kuhn-Munkres算法　177
3.8　點(diǎn)支配集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集　185
3.8.1　點(diǎn)支配集　185
3.8.2　點(diǎn)覆蓋集　185
3.8.3　點(diǎn)獨(dú)立集與團(tuán)　188
3.9　路徑覆蓋和邊覆蓋　188
3.9.1　小路徑覆蓋　188
3.9.2　小邊覆蓋　189
3.10　樹(shù)的相關(guān)問(wèn)題求解　189
3.10.1　小點(diǎn)支配　189
3.10.2　小點(diǎn)覆蓋　190
3.10.3　點(diǎn)獨(dú)立　191
3.11　小結(jié)　191
第4章　動(dòng)態(tài)規(guī)劃　193
4.1　背包問(wèn)題　193
4.1.1　01背包問(wèn)題　193
4.1.2　完全背包問(wèn)題　197
4.1.3　多重背包問(wèn)題　197
4.1.4　背包問(wèn)題擴(kuò)展　198
4.2　備忘　200
4.2.1　3n 1問(wèn)題　201
4.2.2　正交范圍查詢　203
4.2.3　正方形（長(zhǎng)方形）　203
4.2.4　整數(shù)劃分　206
4.2.5　博弈樹(shù)　206
4.2.6　備忘與遞推　210
4.3　松弛　217
4.3.1　Moore-Dijkstra算法　218
4.3.2　Bellman-Ford算法　220
4.3.3　Floyd-Warshall算法　220
4.4　集合型動(dòng)態(tài)規(guī)劃　222
4.5　區(qū)間型動(dòng)態(tài)規(guī)劃　229
4.5.1　矩陣鏈乘法　229
4.5.2　石子合并問(wèn)題　231
4.6　圖論型動(dòng)態(tài)規(guī)劃　238
4.6.1　路徑計(jì)數(shù)　241
4.6.2　樹(shù)形動(dòng)態(tài)規(guī)劃　243
4.6.3　旅行商問(wèn)題　246
4.6.4　雙調(diào)歐幾里得旅行商問(wèn)題　247
4.7　概率型動(dòng)態(tài)規(guī)劃　250
4.8　非典型動(dòng)態(tài)規(guī)劃　255
4.9　動(dòng)態(tài)規(guī)劃的優(yōu)化　257
4.9.1　空間優(yōu)化　257
4.9.2　狀態(tài)優(yōu)化　258
4.9.3　二進(jìn)制優(yōu)化　262
4.9.4　單調(diào)隊(duì)列優(yōu)化　262
4.9.5　斜率優(yōu)化　265
4.9.6　四邊形不等式優(yōu)化　268
4.10　子序列和子串問(wèn)題　271
4.10.1　短編輯距離　271
4.10.2　長(zhǎng)公共子序列　274
4.10.3　長(zhǎng)公共子串　276
4.10.4　長(zhǎng)遞增子序列　277
4.10.5　長(zhǎng)不重復(fù)子串　280
4.10.6　長(zhǎng)回文子串　281
4.10.7　連續(xù)子序列和（積）　285
4.11　貪心算法　287
4.11.1　部分背包問(wèn)題　288
4.11.2　紙幣找零問(wèn)題　289
4.11.3　硬幣兌換問(wèn)題　292
4.11.4　霍夫曼編碼　293
4.11.5　策略選擇　295
4.12　小結(jié)　296
第5章　網(wǎng)格　297
5.1　矩形網(wǎng)格　297
5.1.1　網(wǎng)格行走　297
5.1.2　Flood-Fill算法　299
5.1.3　國(guó)際象棋棋盤　302
5.1.4　騎士周游問(wèn)題　304
5.2　三角形網(wǎng)格　309
5.3　六邊形網(wǎng)格　312
5.4　經(jīng)度與緯度　312
5.5　小結(jié)　313
附錄A　如何使用UVa OJ　314
附錄B　ASCII表　317
附錄C　C 運(yùn)算符優(yōu)先級(jí)　318
附錄D　習(xí)題索引　319
參考資料　320