目 錄

第1章 計(jì)算機(jī)問(wèn)題求解概述 1
1.1 問(wèn)題與問(wèn)題實(shí)例 1
1.2 計(jì)算機(jī)問(wèn)題求解周期 2
1.3 算法與程序 5
1.4　算法復(fù)雜性分析 5
1.4.1　空間復(fù)雜性 6
1.4.2 時(shí)間復(fù)雜性 7
習(xí)題1 15
第2章 程序設(shè)計(jì)語(yǔ)言與數(shù)據(jù)結(jié)構(gòu) 16
2.1 程序設(shè)計(jì)語(yǔ)言的“盲點(diǎn)” 16
2.1.1 long不夠長(zhǎng) 17
2.1.2 double不夠準(zhǔn) 19
2.1.3 遞歸不夠快 25
2.2 基本數(shù)據(jù)結(jié)構(gòu) 26
2.2.1 線性表 26
2.2.2 棧和隊(duì)列 30
2.2.3 樹和二叉樹 36
2.2.4 優(yōu)先隊(duì)列和堆 44
2.2.5 圖 45
2.2.6 并查集 47
2.3 標(biāo)準(zhǔn)模板庫(kù) 49
2.3.1 模板的基本概念 49
2.3.2 標(biāo)準(zhǔn)模板庫(kù)概述 51
2.3.3 標(biāo)準(zhǔn)模板庫(kù)應(yīng)用 52
習(xí)題2 63
第3章 枚舉算法 69
3.1 枚舉的基本思想 69
3.2 模糊數(shù)字 70
3.3 真假銀幣 72
3.4 m錢n雞 75
3.5 數(shù)字配對(duì) 77
3.6 繩子切割 79
3.7 石頭距離 81
習(xí)題3 84
第4章 遞歸與分治 90
4.1 遞歸程序 90
4.2 分治法的基本原理 94
4.3 合并排序 96
4.4 逆序?qū)��?wèn)題 100
4.5 快速排序 102
4.6 最接近點(diǎn)對(duì)問(wèn)題 106
4.7 指數(shù)運(yùn)算 111
4.8 二分查找 113
習(xí)題4 114
第5章 動(dòng)態(tài)規(guī)劃 122
5.1 動(dòng)態(tài)規(guī)劃的基本思想 122
5.1.1 動(dòng)態(tài)規(guī)劃的基本要素 124
5.1.2 動(dòng)態(tài)規(guī)劃的求解步驟 125
5.2 矩陣連乘 126
5.3 最優(yōu)二叉搜索樹 131
5.4 多段圖最短路徑 136
5.5 最長(zhǎng)公共子序列 140
5.6 0-1背包問(wèn)題 143
5.7 最大上升子序列 146
習(xí)題5 149
第6章 貪心算法 155
6.1 貪心算法的基本要素 155
6.2 活動(dòng)安排問(wèn)題 157
6.3 小數(shù)背包問(wèn)題 161
6.4 最優(yōu)前綴碼 164
6.5 單源最短路徑 169
6.6 最小生成樹 174
6.6.1 Prim算法 175
6.6.2 Kruskal算法 178
習(xí)題6 182
第7章 搜索技術(shù) 187
7.1 問(wèn)題的狀態(tài)空間表示 187
7.2 深度優(yōu)先搜索 189
7.3 廣度優(yōu)先搜索 191
7.4 回溯算法 193
7.4.1 回溯算法的基本原理和框架程序 193
7.4.2 裝載問(wèn)題的回溯算法 199
7.4.3 圓排列問(wèn)題 203
7.5 分支限界 206
7.5.1 分支限界法的基本原理 206
7.5.2 裝載問(wèn)題的分支限界法 208
7.6 啟發(fā)式搜索 211
7.6.1 啟發(fā)式搜索基本原理 211
7.6.2 裝載問(wèn)題的啟發(fā)式搜索 215
習(xí)題7 217
附錄A 復(fù)雜度分析的數(shù)學(xué)基礎(chǔ) 225
附錄B 常用C語(yǔ)言和STL函數(shù) 235
附錄C 程序設(shè)計(jì)競(jìng)賽和OnlineJudge介紹 241
附錄D 教學(xué)資源 244
參考文獻(xiàn) 245