ACM程序設(shè)計競賽基礎(chǔ)教程（第2版）

定　價：￥39.00

作　者：	俞經(jīng)善，鞠成東著
出版社：	清華大學(xué)出版社
叢編項：	計算機科學(xué)與技術(shù)專業(yè)實踐系列教材
標(biāo)　簽：	暫缺

購買這本書可以去

ISBN：	9787302446071	出版時間：	2016-10-01	包裝：	平裝
開本：	16開	頁數(shù)：	285	字數(shù)：

內(nèi)容簡介

　　本書以循序漸進的方式對ACM程序設(shè)計競賽中所涉及的基本題型和知識點進行了綜合的介紹。全書共分10章，包括基礎(chǔ)知識講解、典型題目分析和算法設(shè)計，每道例題均給出了完整的源程序作為參考。內(nèi)容涵蓋了基礎(chǔ)算法、數(shù)據(jù)結(jié)構(gòu)、字符串、搜索、圖論、動態(tài)規(guī)劃、組合數(shù)學(xué)和初等數(shù)論等。本書內(nèi)容全面，針對性強，言簡意賅，講解透徹，通俗易懂，圖例豐富，所有源代碼均可進行評測。本書作為ACM程序設(shè)計競賽的培訓(xùn)教程，不僅為大學(xué)生提供了競賽入門的指導(dǎo)，而且對參賽學(xué)生拓展解題思路和提高訓(xùn)練水平也有很大的幫助。本書也可供喜愛程序設(shè)計的學(xué)生以及從事算法設(shè)計的技術(shù)人員學(xué)習(xí)參考。

作者簡介

　　俞經(jīng)善，哈爾濱工程大學(xué)教授，講授數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、算法設(shè)計與分析、計算機網(wǎng)絡(luò)、程序設(shè)計基礎(chǔ)等課程。從事ACM-ICPC競賽活動十余年，具有豐富的競賽培訓(xùn)經(jīng)驗，在各級ACM-ICPC賽事中取得好的成績，兩次率隊進入ACM-ICPC World Finals。鞠成東，哈爾濱工程大學(xué)副教授。講授算法設(shè)計與分析、程序語言設(shè)計基礎(chǔ)、信息安全和具體數(shù)學(xué)等課程。具有豐富的軟件開發(fā)和工程實踐經(jīng)驗，多年指導(dǎo)學(xué)生程序設(shè)計和工程實踐及ACM-ICPC競賽培訓(xùn)。參與編寫本書的人員為哈爾濱工程大學(xué)ACM/ICPC代表隊領(lǐng)隊和指導(dǎo)教師，以及ACM/ICPC代表隊隊員，在編寫過程中參考了大量的文獻，結(jié)合多年的參賽經(jīng)驗，對本書的內(nèi)容進行了撰寫，并對書中例題源程序代碼進行評測。

圖書目錄

第1章基礎(chǔ)算法1
1.1分治算法1
1.2遞歸算法8
1.3枚舉算法14
1.4貪心算法20第2章排序、查找算法29
2.1基本排序算法29
2.1.1插入排序29
2.1.2冒泡排序29
2.1.3快速排序30
2.1.4其他排序30
2.2基本查找算法31
2.2.1順序查找31
2.2.2折半查找31
2.3實例分析32
2.4小結(jié)57第3章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)58
3.1常用數(shù)據(jù)結(jié)構(gòu)簡介58
3.1.1線段樹簡介58
3.1.2并查集簡介58
3.1.3樹狀數(shù)組簡介58
3.2實例分析59第4章字符串80
4.1字符串匹配80
4.1.1樸素的字符串匹配算法80
4.1.2KMP算法81
4.1.3其他匹配算法81
4.2實例分析81
4.3小結(jié)97第5章搜索算法98
5.1基本搜索算法98
5.1.1遞歸與迭代98
5.1.2深度優(yōu)先搜索與廣度優(yōu)先搜索98
5.1.3回溯98
5.2搜索算法的一些優(yōu)化99
5.2.1剪枝函數(shù)99
5.2.2雙向廣度搜索99
5.3實例分析99
5.4小結(jié)121第6章圖論算法122
6.1最短路徑122
6.1.1Dijkstra算法122
6.1.2Floyd算法123
6.1.3BellmanFord算法123
6.2最小生成樹124
6.2.1Kruskal算法125
6.2.2Prim算法126
6.3最大匹配——匈牙利算法127
6.4最優(yōu)權(quán)匹配問題128
6.4.1理論基礎(chǔ)128
6.4.2基本思想129
6.4.3樣例代碼129
6.5割點、割邊以及連通分量131
6.5.1理論基礎(chǔ)131
6.5.2求割點132
6.5.3求強連通分量133
6.6網(wǎng)絡(luò)流135
6.6.1理論基礎(chǔ)135
6.6.2最大流問題135
6.6.3最小費用最大流問題137
6.7實例分析138
6.8小結(jié)166第7章動態(tài)規(guī)劃算法167
7.1基本思想169
7.2基本概念169
7.3基本原理170
7.3.1最優(yōu)化原理170
7.3.2無后效性170
7.4基本步驟170
7.5經(jīng)典例子171
7.6實例分析175
7.7小結(jié)200第8章計算幾何基礎(chǔ)201
8.1矢量201
8.1.1矢量的概念201
8.1.2矢量加減法201
8.1.3矢量叉積201
8.1.4矢量叉積的應(yīng)用201
8.2包含關(guān)系203
8.2.1判斷圖形是否包含在矩形中203
8.2.2判斷圖形是否包含在多邊形中203
8.2.3判斷圖形是否包含在圓中 206
8.3凸包206
8.3.1凸包的概念206
8.3.2凸包的求法206
8.4實例分析208第9章數(shù)論233
9.1基本數(shù)學(xué)算法233
9.1.1素數(shù)篩選233
9.1.2最大公約數(shù)233
9.1.3快速乘方234
9.2實例分析234附錄A綜合訓(xùn)練題264
A.1Lucky Bird264
A.2Josephus’Problem265
A.3Counter Strike267
A.4Gauss Elimination270
A.5The Math Problem271
A.6Mobile Phones272
A.7Japan275
A.8骨灰級玩家考證篇277
A.9括號匹配280
A.10食物鏈282