程序設(shè)計(jì)中常用的解題策略-世界大學(xué)生程序設(shè)計(jì)競賽

內(nèi)容概要

　　《世界大學(xué)程序設(shè)計(jì)競賽（ACM/ICPC）高級教程（第2冊）：程序設(shè)計(jì)中常用的解題策略》是針對世界大學(xué)生程序設(shè)計(jì)競賽（ACM/ICPC）而編寫的第二本參考書。　　ACM/ICPC是大學(xué)生智力與計(jì)算機(jī)解題能力的競賽，是世界公認(rèn)的最具影響力的、規(guī)模最大的國際頂級賽事，被稱為大學(xué)生的信息學(xué)奧林匹克?！　〉谝粌灾饕榻B程序設(shè)計(jì)中解題的常用思維方式。《世界大學(xué)程序設(shè)計(jì)競賽（ACM/ICPC）高級教程（第2冊）：程序設(shè)計(jì)中常用的解題策略》是第一冊的繼續(xù)，只是換了一個(gè)角度，分4方面介紹解題策略：數(shù)據(jù)關(guān)系上的構(gòu)造策略；數(shù)據(jù)統(tǒng)計(jì)上的二分策略；動態(tài)規(guī)劃中的優(yōu)化策略；計(jì)算幾何題的應(yīng)對策略?！　　妒澜绱髮W(xué)程序設(shè)計(jì)競賽（ACM/ICPC）高級教程（第2冊）：程序設(shè)計(jì)中常用的解題策略》面向參加世界大學(xué)生程序設(shè)計(jì)競賽（ACM/ICPC）的高等院校學(xué)生，也可作為程序設(shè)計(jì)愛好者的參考用書。

作者簡介

吳文虎教授1955年—1961年分別就讀于清華大學(xué)電機(jī)工程系及自動控制系，現(xiàn)為計(jì)算機(jī)系教授、博士生導(dǎo)師，主要研究方向包括語音識別及語言理解、語音合成、語音信號數(shù)字處理等。吳教授學(xué)術(shù)水平精湛、教學(xué)水平高超、教學(xué)經(jīng)驗(yàn)豐富，多年來用對學(xué)生無私的愛詮釋了最好的師恩師德。他于1997年獲清華大學(xué)優(yōu)秀教學(xué)成果特等獎(jiǎng)，1998年獲“全國優(yōu)秀教師一等獎(jiǎng)”，1999年獲國家科技部(原國家科委)授予的“全國科學(xué)普及先進(jìn)個(gè)人獎(jiǎng)”，1999年榮獲“首都勞動獎(jiǎng)?wù)隆保?001年獲“全國師德先進(jìn)個(gè)人獎(jiǎng)”，2001年、2004年獲北京市高等教育教學(xué)優(yōu)秀成果一等獎(jiǎng)，2003年為本科生講授的“程序設(shè)計(jì)基礎(chǔ)”課程被列為教育部首批“國家級精品課”，2004年獲中國計(jì)算機(jī)學(xué)會頒發(fā)的“杰出貢獻(xiàn)獎(jiǎng)”，2006年獲北京市高等教育教學(xué)名師獎(jiǎng)；吳教授深受清華學(xué)子的愛戴，2003年獲清華大學(xué)教書育人獎(jiǎng)，2005年獲清華大學(xué)第八屆“良師益友”榮譽(yù)稱號，2008年被清華大學(xué)學(xué)生會評為第一屆“我最喜愛的教師”。    從1989年至今，吳教授作為總教練和領(lǐng)隊(duì)，曾15次帶領(lǐng)中國隊(duì)參加國際信息學(xué)奧林匹克競賽，中國隊(duì)累計(jì)獲金牌51塊，屆屆名列前茅，2002年獲信息學(xué)奧林匹克國際委員會頒發(fā)的“特別貢獻(xiàn)獎(jiǎng)”。1997年—2008年，吳教授連續(xù)13年指導(dǎo)清華大學(xué)的學(xué)生進(jìn)入ACM世界大學(xué)生程序設(shè)計(jì)大賽總決賽，多次獲金牌、銀牌，并于2009年被大賽組委會授予“杰出教練獎(jiǎng)”。

書籍目錄

第7章 利用樹狀結(jié)構(gòu)解題的策略 7.1 解決樹的最大一最小劃分問題的一般方法 7.2 利用最小生成樹及其擴(kuò)展形式解題 7.2.1 利用最小生成樹解題 7.2.2最小k度限制生成樹的思想和應(yīng)用 7.2.3 次小生成樹的思想和應(yīng)用 7.3 利用線段樹解決區(qū)間計(jì)算問題 7.3.1線段樹的基本概念 7.3.2線段樹的基本操作 7.3.3應(yīng)用線段樹解題 7.4利用伸展樹優(yōu)化動態(tài)集合的操作 7.4.1伸展樹的基本操作 7.4.2伸展樹的效率分析 7.4.3應(yīng)用伸展樹解題 7.5 利用左偏樹實(shí)現(xiàn)優(yōu)先隊(duì)列的合并 7.5.1左偏樹的定義和性質(zhì) 7.5.2左偏樹的操作 7.5.3應(yīng)用左偏樹解題 7.6利用“跳躍表”替代樹結(jié)構(gòu) 7.6.1跳躍表的概況 7.6.2跳躍表的基本操作 7.6.3 跳躍表的效率分析 7.6.4應(yīng)用跳躍表解題 小結(jié) 第8章 利用圖形（網(wǎng)狀）結(jié)構(gòu)解題的策略 8.1 利用網(wǎng)絡(luò)流算法解題 8.1.1 網(wǎng)絡(luò)與流的概念 8.1.2最大流算法的核心——增廣路徑 8.1.3通過求最大流計(jì)算最小割切 8.1.4求容量有上下界的最大流問題 8.1.5 網(wǎng)絡(luò)流的應(yīng)用 8.2利用圖的匹配算法解題 8.2.1匹配的基本概念 8.2.2計(jì)算二分圖匹配的方法 8.2.3 利用一一對應(yīng)的匹配性質(zhì)轉(zhuǎn)化問題 8.2.4優(yōu)化匹配算法 8.3利用“分層圖思想”解題 8.3.1 利用“分層圖思想”構(gòu)建圖論模型 8.3.2 利用“分層圖思想”優(yōu)化算法 8.4利用平面圖性質(zhì)解題 8.4.1平面圖的概念 8.4.2平面圖的應(yīng)用實(shí)例 8.5 正確選擇圖論模型，優(yōu)化圖的運(yùn)算 8.5.1 正確選擇圖論模型 8.5.2在充分挖掘和利用圖論模型性質(zhì)的基礎(chǔ)上優(yōu)化算法 小結(jié) 第9章 數(shù)據(jù)關(guān)系上的構(gòu)造策略 9.1 選擇數(shù)據(jù)邏輯結(jié)構(gòu)的基本原則 9.1.1 充分利用“可直接使用”的信息 9.1.2不記錄“無用”信息 9.2選擇數(shù)據(jù)存儲結(jié)構(gòu)的基本方法 9.2.1 合理采用順序存儲結(jié)構(gòu) 9.2.2必要時(shí)采用鏈?zhǔn)酱鎯Y(jié)構(gòu) 9.3 科學(xué)組合多種數(shù)據(jù)結(jié)構(gòu) 小結(jié) 第10章 數(shù)據(jù)統(tǒng)計(jì)上的二分策略 10.1 利用線段樹統(tǒng)計(jì)數(shù)據(jù) 10.2一種解決動態(tài)統(tǒng)計(jì)的靜態(tài)方法 10.2.1 討論一維序列的求和問題 10.2.2將一維序列的求和問題推廣至二維 10.3 在靜態(tài)二叉排序樹上統(tǒng)計(jì)數(shù)據(jù) 10.3.1 建立靜態(tài)二叉排序樹 10.3.2在靜態(tài)二叉排序樹上進(jìn)行統(tǒng)計(jì) 10.3.3 靜態(tài)二叉排序樹的應(yīng)用 10.4在虛二叉樹上統(tǒng)計(jì)數(shù)據(jù) 小結(jié) 第11章 動態(tài)規(guī)劃上的優(yōu)化策略 11.1 減少狀態(tài)總數(shù)的基本策略 11.1.1改進(jìn)狀態(tài)表示 11.1.2選擇適當(dāng)?shù)囊?guī)劃方向 11.2減少每個(gè)狀態(tài)決策數(shù)的基本策略 11.2.1 利用最優(yōu)決策的單調(diào)性 11.2.2優(yōu)化決策量 11.2.3合理組織狀態(tài) 11.2.4細(xì)化狀態(tài)轉(zhuǎn)移 11.3 減少狀態(tài)轉(zhuǎn)移時(shí)間的基本策略 11.3.1減少決策時(shí)間 11.3.2減少計(jì)算遞推式的時(shí)間 小結(jié) 第12章 計(jì)算幾何上的應(yīng)對策略 12.1應(yīng)對純粹計(jì)算題的策略探討 12.1.1 利用二重二叉樹計(jì)算長方體的體積并 12.1.2 利用多維線段樹和矩形切割思想解決平面統(tǒng)計(jì)或空間統(tǒng)計(jì)問題 12.1.3利用極大化思想解決最大子矩形問題 12.1.4利用半平面交的算法計(jì)算凸多邊形 12.2應(yīng)對存在性問題的策略探討 12.2.1 直接通過幾何計(jì)算求解 12.2.2轉(zhuǎn)換幾何模型求解 12.3 應(yīng)對最佳值問題的策略探討 12.3.1 采用高效的幾何模型 12.3.2采用極限法 12.3.3采用逼近最佳解的近似算法 小結(jié)

章節(jié)摘錄

版權(quán)頁：   插圖：   以上介紹了解決樹的最大一最小劃分問題的兩種解法，它們通過不同的方式思考問題，從而得到了不同的算法：解法1主要應(yīng)用了問題轉(zhuǎn)化的思想，將原問題轉(zhuǎn)化為容易解決的問題，在給定下界時(shí)如何劃分最多子樹，如果可以解決這個(gè)問題，再通過二分查找下界求得原問題的解。這種算法的目光聚焦在結(jié)點(diǎn)的權(quán)值上，實(shí)現(xiàn)簡單，時(shí)間效率也不錯(cuò)；而解法2則從另一個(gè)角度看問題，將目光集中在分割子樹的“割”上面，從而得到了一個(gè)復(fù)雜度不依賴于結(jié)點(diǎn)權(quán)值范圍的算法，其中起關(guān)鍵作用的是劃分問的“上方”關(guān)系，這種關(guān)系實(shí)際上是一種“序”的思想。利用“序”簡化問題、建立高效模型是程序設(shè)計(jì)中一種典型的優(yōu)化方法。 雖然有了劃分樹的兩種解法，但我們并不滿足，還希望能夠?qū)⑺惴〝U(kuò)展一下，使它的適用范圍更加廣泛。 優(yōu)化方法1：擴(kuò)展權(quán)函數(shù) 首先來看一下權(quán)函數(shù)方面，由“每棵子樹的權(quán)被定義為子樹中所有結(jié)點(diǎn)的權(quán)之和”想到，對于一些其他的權(quán)函數(shù)，例如一棵子樹中結(jié)點(diǎn)權(quán)的最大值、子樹的直徑（子樹結(jié)點(diǎn)問路徑長度的最大值）等，這個(gè)算法是不是依然適用呢？我們發(fā)現(xiàn)，在解法2的證明過程中，只有②和③的證明用到了子樹的權(quán)函數(shù)，而通過更加深入觀察發(fā)現(xiàn)，證明中只是利用了權(quán)函數(shù)的一個(gè)性質(zhì)： 權(quán)函數(shù)的性質(zhì)：若T是T的任意一棵子樹，則必然有W（T）≥W（T），其中W（T）表示樹T中結(jié)點(diǎn)的權(quán)值和。 也就是說，只要權(quán)函數(shù)滿足這個(gè)條件，這個(gè)證明就是正確的，這個(gè)算法也就是可行的。于是，對于滿足特定條件的一類問題都找到了一種通用的解法，這也顯示出該算法很強(qiáng)的可擴(kuò)展性。 有了對權(quán)函數(shù)的擴(kuò)展，接下來便想到了對問題的擴(kuò)展。例如，將樹劃分為k棵子樹，使得子樹的最大值最小，或是最大值與最小值的差最小等問題，我們是不是也可以用原算法求解呢？事實(shí)證明，單純地照搬是行不通的，因?yàn)樗惴ㄓ凶陨淼奶攸c(diǎn)，不可能適用于所有問題，但解決問題的思路卻是可以借鑒的。在解決與這一類型有關(guān)的問題時(shí)，或許可以改變移動的規(guī)則，或修改一下“上方”的定義，從而設(shè)計(jì)出符合題目特點(diǎn)的算法，這些問題可引起讀者思考。 優(yōu)化方法2：用解法1優(yōu)化解法2 在解法2中，初始狀態(tài)是將k—1個(gè)割放在與根相連的唯一一條邊上得到的，這樣做的好處是一定可以保證它在某個(gè)最優(yōu)劃分的上方。可是由這個(gè)初始狀態(tài)移動到最優(yōu)狀態(tài)往往需要很多步的移動，那么有沒有更好的初始狀態(tài)呢？我們想到了解法1，如果把下界設(shè)為樹中節(jié)點(diǎn)的權(quán)和/k—1，則劃分出來的子樹數(shù)一定不超過k—1，我們將剩余的割都放在與根相連的那條邊上?？梢宰C明，這個(gè)劃分狀態(tài)一定是在某個(gè)最優(yōu)劃分的上方的，而由它達(dá)到最優(yōu)狀態(tài)所需要移動的步數(shù)卻減少了。于是，只需要一個(gè)線性的預(yù)處理，便得到了一種更好的初始狀態(tài)。這樣，解法l和解法2便巧妙地結(jié)合在一起了。

編輯推薦

《世界大學(xué)生程序設(shè)計(jì)競賽(ACM/ICPC)高級教程(第2冊):程序設(shè)計(jì)中常用的解題策略》面向參加世界大學(xué)生程序設(shè)計(jì)競賽（ACM/ICPC）的高等院校學(xué)生，也可以作為程序設(shè)計(jì)愛好者的參考用書。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    程序設(shè)計(jì)中常用的解題策略-世界大學(xué)生程序設(shè)計(jì)競賽 PDF格式下載

---