《程式設計中常用的解題策略》是2009年10月人民郵電出版社出版的圖書，作者是王建德。本書既可以作為大專院校計算機專業算法類課程的教材，亦可以作為大學和中學的程式設計競賽活動的培訓教程，還可以作為計算機軟體研發的參考資料。
基本介紹
內容簡介,作者簡介,圖書目錄,
內容簡介
《程式設計中常用的解題策略》按照題型和知識點分類，以數據關係上的構造策略、數據統計上的二分策略、動態規劃上的最佳化策略、計算幾何問題上的應對策略這4個方面為基本構件，介紹了幾十種解題策略和重要算法；同時，深入淺出地分析和證明了對每種解題策略和算法的原理，採用“一題多解”、“多向求解”的方式解析了70餘道例題，並結合套用例證闡釋了編程中常用的一些思維方式和解題策略，以拓寬讀者的思路，教會讀者應該怎樣套用算法知識解題，應該怎樣選擇有效的算法。
作者簡介
王建德，國務院特殊津貼專家、上海師範大學特聘教授、控江中學特級教師。他輔導學生在國際奧林匹克信息學競賽（IOI）中獲8金、2銀、2銅，先後出版了《新編實用算法分析與程式設計》、《程式設計中常用的計算思維方式》等23本廣受好評的圖書，這些圖書長期以來是國內各類程式設計競賽的必備教程。
圖書目錄
第1章 利用樹型結構解題的策略
1.1 解決樹的最大/最小劃分問題的一般方法
1.1.1 解法1——二分查找最大的下界
1.1.2 解法2——向下移動“割”
1.1.3 在兩種解法的基礎上進一步最佳化
1.2 利用最小生成樹及其擴展形式解題
1.2.1 利用最小生成樹解題
1.2.2 最小k度限制生成樹的思想和套用
1.2.3 次小生成樹的思想和套用
1.3 利用線段樹解決區間計算問題
1.3.1 線段樹的基本概念
1.3.2 線段樹的基本操作
1.3.3 套用線段樹解題
1.4 利用伸展樹最佳化動態集合的操作
1.4.1 伸展樹的基本操作
1.4.2 伸展樹的效率分析
1.4.3 套用伸展樹解題
1.5 利用左偏樹實現優先佇列的合併
1.5.1 左偏樹的定義和性質
1.5.2 左偏樹的操作
1.5.3 套用左偏樹解題
1.6 利用“跳躍表”替代樹結構
1.6.1 跳躍表的概況
1.6.2 跳躍表的基本操作
1.6.3 跳躍表的效率分析
1.6.4 套用跳躍表解題
小結
第2章 利用圖形(網狀)結構解題的策略
2.1 利用網路流算法解題
2.1.1 網路與流的概念
2.1.2 在增廣路徑的基礎上計算最大流
2.1.3 利用最大流最小割切定理解題
2.1.4 求容量有上下界的最大流問題
2.1.5 計算帶費用的流量問題
2.2 利用圖的匹配算法解題
2.2.1 匹配的基本概念
2.2.2 計算二分圖的匹配
2.2.3 利用一一對應的匹配性質轉化問題
2.3 利用“分層圖思想”解題
2.3.1 利用“分層圖思想”化未知為已知
2.3.2 利用分層圖思想最佳化算法
2.4 利用平面圖性質解題
2.4.1 平面圖的基本概念
2.4.2 平面圖的套用實例
2.4.3 偏序集的基本概念
2.4.4 偏序集的套用實例
2.5 在充分挖掘和利用圖論模型性質的基礎上最佳化算法
小結
第3章 數據關係上的構造策略
3.1 選擇數據的邏輯結構的基本原則
3.1.1 充分利用“可直接使用”的信息
3.1.2 不記錄“無用”信息
3.2 選擇數據的存儲結構的基本方法
3.2.1 合理採用順序存儲結構
3.2.2 必要時採用鏈式存儲結構
3.3 科學組合多種數據結構
3.3.1 數據結構的“並聯”
3.3.2 數據結構的“嵌套”
小結
第4章 數據統計上的二分策略
4.1 利用線段樹統計數據
4.1.1 解決一維數據序列的統計問題
4.1.2 解決二維數據區的統計問題
4.2 一種解決動態統計的靜態方法
4.2.1 討論一維序列的求和問題
4.2.2 二維序列的求和問題
4.3 在靜態二叉排序樹上統計數據
4.3.1 建立靜態二叉排序樹
4.3.2 在靜態二叉排序樹上進行統計
4.3.3 靜態二叉排序樹的套用
4.4 在虛二叉樹上統計數據
小結
第5章 動態規劃上的最佳化策略
5.1 減少狀態總數的基本策略
5.1.1 改進狀態表示
5.1.2 選擇適當的規劃方向
5.2 減少每個狀態決策數的基本策略
5.2.1 利用最優決策的單調性
5.2.2 最佳化決策量
5.2.3 合理組織狀態
5.2.4 細化狀態轉移
5.3 減少狀態轉移時間的基本策略
5.3.1 減少決策時間
5.3.2 減少計算遞推式的時間
小結
第6章 計算幾何上的應對策略
6.1 應對純粹計算題的策略探討
6.1.1 利用多維線段樹解決矩形或長方體幾何的計算問題
6.1.2 利用矩形切割思想進行幾何計算和數據統計
6.1.3 利用極大化思想解決最大子矩形問題
6.1.4 利用半平面交的算法計算凸多邊形
6.2 應對存在性問題的策略探討
6.2.1 直接通過幾何計算求解
6.2.2 轉換幾何模型求解
6.3 應對最佳值問題的策略探討
6.3.1 採用高效的幾何模型
6.3.2 採用極限法
6.3.3 採用逼近最佳解的近似算法
小結
……
