程序設計中常用的解題策略

內容概要

本書按照題型和知識點分類，以數(shù)據(jù)關系上的構造策略、數(shù)據(jù)統(tǒng)計上的二分策略、動態(tài)規(guī)劃上的優(yōu)化策略、計算幾何問題上的應對策略這4個方面為基本構件，介紹了幾十種解題策略和重要算法；同時，深入淺出地分析和證明了對每種解題策略和算法的原理，采用“一題多解”、“多向求解”的方式解析了70余道例題，并結合應用例證闡釋了編程中常用的一些思維方式和解題策略，以拓寬讀者的思路，教會讀者應該怎樣應用算法知識解題，應該怎樣選擇有效的算法。    本書既可以作為大專院校計算機專業(yè)算法類課程的教材，亦可以作為大學和中學的程序設計競賽活動的培訓教程，還可以作為計算機軟件研發(fā)的參考資料。

作者簡介

王建德，國務院特殊津貼專家、上海師范大學特聘教授、控江中學特級教師。他輔導學生在國際奧林匹克信息學競賽（IOI）中獲8金、2銀、2銅，先后出版了《新編實用算法分析與程序設計》、《程序設計中常用的計算思維方式》等23本廣受好評的圖書，這些圖書長期以來是國內各類程序

書籍目錄

第1章　利用樹型結構解題的策略  1.1　解決樹的最大/最小劃分問題的一般方法    1.1.1　解法1——二分查找最大的下界    1.1.2　解法2——向下移動“割”    1.1.3　在兩種解法的基礎上進一步優(yōu)化  1.2　利用最小生成樹及其擴展形式解題    1.2.1  利用最小生成樹解題    1.2.2　最小k度限制生成樹的思想和應用    1.2.3  次小生成樹的思想和應用  1.3　利用線段樹解決區(qū)間計算問題    1.3.1　線段樹的基本概念    1.3.2　線段樹的基本操作    1.3.3　應用線段樹解題  1.4　利用伸展樹優(yōu)化動態(tài)集合的操作    1.4.1　伸展樹的基本操作    1.4.2　伸展樹的效率分析    1.4.3　應用伸展樹解題  1.5　利用左偏樹實現(xiàn)優(yōu)先隊列的合并    1.5.1　左偏樹的定義和性質    1.5.2　左偏樹的操作    1.5.3　應用左偏樹解題  1.6　利用“跳躍表”替代樹結構    1.6.1　跳躍表的概況    1.6.2　跳躍表的基本操作    1.6.3　跳躍表的效率分析    1.6.4　應用跳躍表解題  小結第2章　利用圖形（網(wǎng)狀）結構解題的策略  2.1　利用網(wǎng)絡流算法解題    2.1.1  網(wǎng)絡與流的概念    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　利用分層圖思想優(yōu)化算法  2.4　利用平面圖性質解題    2.4.1  平面圖的基本概念    2.4.2　平面圖的應用實例    2.4.3　偏序集的基本概念    2.4.4　偏序集的應用實例  2.5　在充分挖掘和利用圖論模型性質的基礎上優(yōu)化算法  小結第3章　數(shù)據(jù)關系上的構造策略  3.1　選擇數(shù)據(jù)的邏輯結構的基本原則    3.1.1　充分利用“可直接使用”的信息    3.1.2　不記錄“無用”信息  3.2　選擇數(shù)據(jù)的存儲結構的基本方法    3.2.1　合理采用順序存儲結構    3.2.2　必要時采用鏈式存儲結構  3.3　科學組合多種數(shù)據(jù)結構    3.3.1　數(shù)據(jù)結構的“并聯(lián)”    3.3.2　數(shù)據(jù)結構的“嵌套”　小結第4章　數(shù)據(jù)統(tǒng)計上的二分策略　……第5章　動態(tài)規(guī)劃上的優(yōu)化策略第6章　計算幾何上的應對策略

章節(jié)摘錄

插圖：第2章　利用圖形（網(wǎng)狀）結構解題的策略圖是對實際問題的一種抽象方式，即用頂點、邊和權來描述事物和事物之間的關系。實際上，第1章所述的樹是圖的一種特例，即一種限定前件數(shù)為1且不允許有同路的連通圖。本章中，我們取消了這種限制，在更寬泛的意義上討論事物間的聯(lián)系。建立圖論模型，就是要從問題的原型中抽取對我們有用的信息和要素，使要素間的內在聯(lián)系體現(xiàn)在點、邊、權的關系上，使紛雜的信息變得有序、直觀、清晰。本章將介紹。些利用網(wǎng)絡流算法、匹配算法、分層圖思想、平面圖性質和平面圖的偏序集模型解題的基本策略，并在此基礎上著重討論選擇圖論模型的重要意義和優(yōu)化算法的方法。2.1 利用網(wǎng)絡流算法解題網(wǎng)絡流算法是一種高效實用的算法，相對于其他圖論算法來說，模型更加復雜，編程復雜度也更高。但是網(wǎng)絡流算法綜合了圖論中的其他一些算法（如寬度優(yōu)先搜索、最短路徑等），能夠有效地解決一些看似NP的問題，因而適用范圍很廣。

編輯推薦

《程序設計中常用的解題策略》對近年來程序設計教育和競賽培訓活動涌現(xiàn)出的許多有價值的解題方法，進行了理性、概括性和綜合性的總結。從思維方式和行為特征的角度闡釋了求解各種類型試題的應對策略。全書不僅充分闡釋了各種解題策略的理論依據(jù)，而且還提供了大量經(jīng)典的應用范例。幫助讀者學會選擇適宜的解題方法，掌握正確的解題策略?！冻绦蛟O計中常用的解題策略》既是大學計算機專業(yè)算法分析課程的優(yōu)秀參考書，又是大中學程序設計競賽不可錯過的培訓教材。《程序設計中常用的解題策略》特色：·《程序設計中常用的解題策略》以數(shù)據(jù)關系上的構造策略、數(shù)據(jù)統(tǒng)計上的二分策略、動態(tài)規(guī)劃上的優(yōu)化策略和計算幾何問題上的應對策略為4個基本構件，介紹了40余種解題策略和重要算法?！じ髡鹿?jié)之間有緊密的內在聯(lián)系，但彼此又相對獨立?！γ糠N解題策略和算法原理進行了必要的分析和證明。定理證明大多采用初等數(shù)學的分析方法.公式推導盡可能做到淺顯和詳細，對其中一些復雜的解題策略和算法附加了清晰的圖示，并給出了計算時間的詳細分析。·40余種解題策略都有具體的應用例證。70余道例題采用“一題多解”、“多向求解”的方式解析。并給出了由貼近自然語言、結構清晰、移植性強的類程序設計語言表述的程序題解。計算機程序設計競賽權威指導書

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    程序設計中常用的解題策略 PDF格式下載

---