●章計算機問題求解概述
1.1問題與問題實例
1.2計算機問題求解周期
1.3算法與程序
1.4算法復雜性分析
1.4.1空間復雜性
1.4.2時間復雜性
習題1
第2章程序設計語言與數據結構
2.1程序設計語言的“盲點”
2.1.1long不夠長
2.1.2double不夠準
2.1.3遞歸不夠快
2.2基本數據結構
2.2.1線性表
2.2.2棧和隊列
2.2.3樹和二叉樹
2.2.4優先隊列和堆
2.2.5圖
2.2.6並查集
2.3標準模板庫
2.3.1模板的基本概念
2.3.2標準模板庫概述
2.3.3標準模板庫應用
習題2
第3章枚舉算法
3.1枚舉的基本思想
3.2模糊數字
3.3真假銀幣
3.4m錢n雞
3.5數字配對
3.6繩子切割
3.7石頭距離
習題3
第4章遞歸與分治
4.1遞歸程序
4.2分治法的基本原理
4.3合並排序
4.4逆序對問題
4.5快速排序
4.6最接近點對問題
4.7指數運算
4.8二分查找
習題4
第5章動態規劃
5.1動態規劃的基本思想
5.1.1動態規劃的基本要素
5.1.2動態規劃的求解步驟
5.2矩陣連乘
5.3最優二叉搜索樹
5.4多段圖最短路徑
5.5最長公共子序列
5.60-1背包問題
5.7優選上升子序列
習題5
第6章貪心算法
6.1貪心算法的基本要素
6.2活動安排問題
6.3小數背包問題
6.4最優前綴碼
6.5單源最短路徑
6.6最小生成樹
6.6.1Prim算法
6.6.2Kruskal算法
習題6
第7章搜索技術
7.1問題的狀態空間表示
7.2深度優先搜索
7.3廣度優先搜索
7.4回溯算法
7.4.1回溯算法的基本原理和框架程序
7.4.2裝載問題的回溯算法
7.4.3圓排列問題
7.5分支限界
7.5.1分支限界法的基本原理
7.5.2裝載問題的分支限界法
7.6啟發式搜索
7.6.1啟發式搜索基本原理
7.6.2裝載問題的啟發式搜索
習題7
附錄A復雜度分析的數學基礎
附錄B常用C語言和STL函數
附錄C程序設計競賽和OnlineJudge介紹
附錄D教學資源
參考文獻
內容簡介
在信息時代,計算思維是解決復雜工程問題的重要思維方式,計算機則是求解問題的重要工具。本書以計算機經典問題求解為導向,通用算法思維和編程能力培養為目標,引入ACM靠前大學生程序設計競賽素,組織教材的理論教學和編程實踐兩方面的內容。本書主要內容包括計算機問題求解的經典算法模型和設計範式,包括計算機問題求解中常用的數據結構、枚舉算法、遞歸與分治策略、動態規劃、貪心算法和搜索技術。除了強調經典的問題原型和算法原理,本書兼顧編程實踐能力,力圖使得學生面對復雜問題時既能“想到”還能“做到”。