程序設(shè)計(jì)中常用的解題策略

內(nèi)容概要

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

作者簡(jiǎn)介

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

書(shū)籍目錄

第1章　利用樹(shù)型結(jié)構(gòu)解題的策略  1.1　解決樹(shù)的最大/最小劃分問(wèn)題的一般方法    1.1.1　解法1——二分查找最大的下界    1.1.2　解法2——向下移動(dòng)“割”    1.1.3　在兩種解法的基礎(chǔ)上進(jìn)一步優(yōu)化  1.2　利用最小生成樹(shù)及其擴(kuò)展形式解題    1.2.1  利用最小生成樹(shù)解題    1.2.2　最小k度限制生成樹(shù)的思想和應(yīng)用    1.2.3  次小生成樹(shù)的思想和應(yīng)用  1.3　利用線段樹(shù)解決區(qū)間計(jì)算問(wèn)題    1.3.1　線段樹(shù)的基本概念    1.3.2　線段樹(shù)的基本操作    1.3.3　應(yīng)用線段樹(shù)解題  1.4　利用伸展樹(shù)優(yōu)化動(dòng)態(tài)集合的操作    1.4.1　伸展樹(shù)的基本操作    1.4.2　伸展樹(shù)的效率分析    1.4.3　應(yīng)用伸展樹(shù)解題  1.5　利用左偏樹(shù)實(shí)現(xiàn)優(yōu)先隊(duì)列的合并    1.5.1　左偏樹(shù)的定義和性質(zhì)    1.5.2　左偏樹(shù)的操作    1.5.3　應(yīng)用左偏樹(shù)解題  1.6　利用“跳躍表”替代樹(shù)結(jié)構(gòu)    1.6.1　跳躍表的概況    1.6.2　跳躍表的基本操作    1.6.3　跳躍表的效率分析    1.6.4　應(yīng)用跳躍表解題  小結(jié)第2章　利用圖形（網(wǎng)狀）結(jié)構(gòu)解題的策略  2.1　利用網(wǎng)絡(luò)流算法解題    2.1.1  網(wǎng)絡(luò)與流的概念    2.1.2　在增廣路徑的基礎(chǔ)上計(jì)算最大流    2.1.3　利用最大流最小割切定理解題    2.1.4　求容量有上下界的最大流問(wèn)題    2.1.5　計(jì)算帶費(fèi)用的流量問(wèn)題  2.2　利用圖的匹配算法解題    2.2.1  匹配的基本概念    2.2.2　計(jì)算二分圖的匹配    2.2.3  利用一一對(duì)應(yīng)的匹配性質(zhì)轉(zhuǎn)化問(wèn)題  2.3　利用“分層圖思想”解題    2.3.1　利用“分層圖思想”化未知為已知    2.3.2　利用分層圖思想優(yōu)化算法  2.4　利用平面圖性質(zhì)解題    2.4.1  平面圖的基本概念    2.4.2　平面圖的應(yīng)用實(shí)例    2.4.3　偏序集的基本概念    2.4.4　偏序集的應(yīng)用實(shí)例  2.5　在充分挖掘和利用圖論模型性質(zhì)的基礎(chǔ)上優(yōu)化算法  小結(jié)第3章　數(shù)據(jù)關(guān)系上的構(gòu)造策略  3.1　選擇數(shù)據(jù)的邏輯結(jié)構(gòu)的基本原則    3.1.1　充分利用“可直接使用”的信息    3.1.2　不記錄“無(wú)用”信息  3.2　選擇數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)的基本方法    3.2.1　合理采用順序存儲(chǔ)結(jié)構(gòu)    3.2.2　必要時(shí)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)  3.3　科學(xué)組合多種數(shù)據(jù)結(jié)構(gòu)    3.3.1　數(shù)據(jù)結(jié)構(gòu)的“并聯(lián)”    3.3.2　數(shù)據(jù)結(jié)構(gòu)的“嵌套”　小結(jié)第4章　數(shù)據(jù)統(tǒng)計(jì)上的二分策略　……第5章　動(dòng)態(tài)規(guī)劃上的優(yōu)化策略第6章　計(jì)算幾何上的應(yīng)對(duì)策略

章節(jié)摘錄

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

編輯推薦

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

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    程序設(shè)計(jì)中常用的解題策略 PDF格式下載

---