 |
-- 會員 / 註冊 --
|
 |
|
|
|
程序設計解題策略 ( 簡體 字) |
| 作者：吳永輝 王建德 編著 | 類別：1. -> 程式設計 -> 綜合 |
| 譯者： |
| 出版社：機械工業出版社 |  3dWoo書號： 41091
詢問書籍請說出此書號！【缺書】
NT售價： 395 元 |
| 出版日：3/1/2015 |
| 頁數：504 |
| 光碟數：0 |
|
站長推薦：   |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787111488316 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言：策和謀略，指一種總體的行為方針和行事方法，即一種可以實現目標的方案集合，而非糾纏于細枝末節的雕蟲小技。程序設計的解題策略指的是編程解題過程中所采取的一種基本方法，是對解題方法的綜合性、智能性和個性化的認識。尤其是當面對非標準、非模式化的問題時，就更需要發揮創造性思維，求索應對策略和解題藝術。正如古人所言“術謀之人以思謨為度，故能成策?之奇，而不識遵法之良”。
對于程序設計競賽選手的培養，教師應注重在兩個方面系統地訓練選手：?程序設計競賽的知識體系；?程序設計的解題策略。
對于程序設計競賽的知識體系，可以用“算法+數據結構=程序”這一著名公式來概括。為此，這兩年我們先后在機械工業出版社出版了兩本專著（《數據結構編程實驗》和《算法設計編程實驗》），其中《數據結構編程實驗》還由中國臺灣碁峰出版社以《提升程式設計的資料結構力：國際程式設計競賽之資料結構原理、題型、解題技巧與重點解析》為書名出版。
上述兩本書和本書一起，構成了對程序設計競賽選手進行“程序設計競賽的知識體系”和“程序設計的解題策略”系統訓練的一個完整系列，本系列也可以作為大學的程序設計實驗課程的系列教材。這三本書包含的知識結構和實驗選題沒有重復且互相聯系：前兩本書在系統講述程序設計競賽知識體系結構的同時，也涉及一些初淺的解題策略，但主要是從知識的角度談解題方法；而本書所講述的解題策略雖是在深入數據結構和算法設計知識的基礎上展開，但側重從行為特征的角度談解題方法。所以，這三本書的知識層次和論述角度有區別、有聯系、有遞進關系。
為了使讀者對編程解題的策略有一個全面了解，我們將這些年國際、國內程序設計競賽的經典例題進行分門別類，從七個大的方面討論解題策略。
（1）利用樹型數據關系解題的七種基本策略
利用劃分樹求解整數區間內第k大的值；利用最小生成樹原理和拓展形式（最小k度限制生成樹和次小生成樹）求解帶權無向連通圖中最佳邊權和的生成樹；利用一維線段樹計算和維護區間的最值（最大或最小值）和總量；利用兩種改進型的二叉查找樹——伸展樹和紅黑樹來優化動態集合的操作；利用動態樹計算和維護一個帶權森林；利用左偏樹實現優先隊列的合并；利用跳躍表實現樹的功能。
（2）利用圖型數據關系解題的五種基本策略
將圖論問題轉化成網絡流的計算；將一般圖轉換成二分圖，利用匹配算法提高計算效率；通過分層圖思想將干擾因素細化為若干狀態，通過層的連接將狀態聯系起來，最終找到算法；從信息原型中挖掘出平面圖特征，洞悉有向邊蘊含的偏序關系，清晰思路、簡化算法；從挖掘和利用圖論模型性質的三個思考角度出發，提出選擇圖論模型和優化算法的三種基本策略（“定義法”、“分析法”、“綜合法”）。
（3）數據關系上的構造的三種基本策略
選擇邏輯結構的兩個基本原則（利用“可直接使用”的信息和不記錄“無用”的信息）；選擇存儲結構的基本思路；科學組合多種數據結構的兩種基本方法（并聯和嵌套）。
（4）利用二分法進行數據統計的四種策略
一維或二維線段樹；動態統計子序列和的樹狀數組與用于RMQ問題的倍增數組；靜態二叉排序樹；虛二叉樹。
（5）動態規劃上的優化的四種策略
從三個角度（減少狀態總數、每個狀態決策數和每狀態轉移時間）討論動態規劃（DP）的優化策略；應對連通性問題的DP策略——基于狀態壓縮的插頭DP。
（6）應對計算幾何的五種基本策略
用于求解最遠、最近或第k近距離問題中的模擬退火算法；用于求解凸性函數極值問題的三分法；應用于復合屬性圖形計算的剖分優化思想；解決最大子矩形問題的極大化思想；在求解綜合性、擴展性幾何問題中合理組合基本幾何運算的方法。
（7）應對博弈類問題的四種基本策略
動態博弈的思想方法；三個基礎博弈（巴什博弈、威佐夫博弈和尼姆博弈）及其擴展形式；在組合游戲中使用SG函數；使用數學工具surreal number應對不平等的組合游戲。
我們以上述七個方面為基本構件，介紹了49種解題策略和重要算法，如下表所示：
序號解題策略和重要算法所在章節
1劃分樹 第1章 利用樹型數據關系的解題策略
2最優比率生成樹
3最小k度限制生成樹
4次小生成樹
5線段樹
6伸展樹
7紅黑樹
8動態樹
9左偏樹
10跳躍表
11Dinic算法 第2章 利用圖型數據關系的解題策略
12求容量有上下界的最大流問題
13計算最小費用最大流
14計算二分圖的最大匹配
15計算二分圖最佳匹配
16利用分層圖思想
17偏序集
18優化圖論模型的三種方法
19充分利用“可直接使用”的信息 第3章 數據關系上的構造策略
20不記錄“無用”的信息
21合理采用順序存儲結構
22必要時采用鏈式存儲結構
23數據結構的“并聯”
24數據結構的“嵌套”
25線段樹 第4章 數據統計上的二分策略
26樹狀數組
27倍增算法
28靜態二叉排序樹
29虛二叉樹
（續）序號解題策略和重要算法所在章節
30DP中減少狀態總數的基本策略 第5章 動態規劃上的優化策略
31DP中減少每個狀態決策數的基本策略
32DP中減少狀態轉移時間的基本策略
33基于狀態壓縮的插頭DP
34模擬退火算法
35三分法 第6章 計算幾何上的應對策略
36圓重合其他幾何圖形時的剖分策略
37三角剖分
38梯形剖分
39矩形切割思想
40利用極大化思想解決最大子矩形問題
41合理組合基本幾何運算
42利用動態博弈思想判斷輸贏 第7章 博弈類問題的應對策略
43巴什博弈
44威佐夫博弈
45尼姆博弈
46k倍動態減法游戲
47尼姆博弈的四種擴展形式
48SG函數
49使用surreal number應對組合游戲
這些策略和算法有的源于程序設計領域的經典成果，但更多的是源于復旦大學程序設計競賽隊的成員在長期編程實踐中積淀的策略經驗。我們對此進行了認真的整理和提煉，使之由默會知識變成明言知識。書中所述的每個解題策略和算法原理都有必要的分析和證明，定理證明大多采用初等數學的分析方法，公式推導盡可能做到淺顯和詳細，并給出了計算時間復雜度的詳細分析。為了幫助讀者理解，對其中一些復雜的解題策略和算法附加了圖示，使其過程更加具體、直觀和形象。
“程序設計解題策略”是一門“實踐出真知”的課程，需要大量引入案例教學，通過模擬或者重現現實生活中的一些場景，讓讀者置身于問題情境之中，通過思考、討論和上機編程來學習解題策略。為此，我們在浩如煙海的各類程序設計競賽試題中精選出100道試題作為實驗范例，啟發性地引出相應的解題策略，為讀者學習解題策略的相關知識創設豐富有趣的問題背景。每個實驗范例不僅有知識要點闡述和詳盡的試題解析，而且還給出了寫有詳細注釋的參考程序；每個常用的解題策略都以經典模型為支撐，每個定理概念都有詳盡的說明和推導，并使用大量圖表增加直觀性和可讀性。本書盡力將經典模型推廣到具有相同性質的一類問題，讓讀者熟悉一個經典模型就相當于掌握了解決一類問題的方法。有時還有意在經典模型外加入其他因素，引導讀者對被套用的經典模型進行適當修改，加入獨特的屬性，或者運用已知模型或方法來分析信息原型的屬性，在此基礎上創造出具有新意的模型或方法。為了讓讀者能夠檢驗自編程序的正確性和效率，每道題都注明了試題來源和在線測試網址。另外，可登錄華章網站（www.hzbook.com）下載所有試題的原版描述和大部分試題的測試數據等資料。
本書試題的在線測試地址主要有：
在線評測系統 簡稱 網址
北京大學在線評測系統 POJ http://poj.org/
浙江大學在線評測系統 ZOJ http://acm.zju.edu.cn/onlinejudge/
UVA在線評測系統 UVA http://uva.onlinejudge.org/
http://livearchive.onlinejudge.org/
Ural在線評測系統 Ural http://acm.timus.ru/
SGU在線評測系統 SGU http://acm.sgu.ru/
杭州電子科技大學在線評測系統 HDOJ http://acm.hdu.edu.cn/
編程解題離不開建模和解題方法，解題的成功取決于選擇正確的數學模型和解題方法，而數學模型和解題方法的正確性源于采用適宜的解題策略。建議讀者在學習各種解題策略時，注意以下三個方面的問題。
1）培養良好的認知結構。注重相關理論的學習，并通過不斷應用來強化理論知識，形成一個脈絡分明、縱橫交錯的知識網絡。同時注意把一些常用的解題技巧和變換方法放在記憶庫里，把同類問題“存儲在一起”，使知識條理化。
2）提高解題能力。平時要多看書和多解題，從書中和編程實踐中尋找再發現、再創造的契機。既要注意運算結果的正確性，也要注意知識產生的過程性（概念、法則被概括的過程，數據關系被抽象的過程，解題策略被探索的過程）。要細化書本知識，如同電視屏幕中體育大賽慢鏡頭式的分解，真正使自己學有所得。
3）注重解題策略的歸類分析。就某個方面的解題策略而言，其形成過程是可以邏輯化、模式化的。因此，要多考慮將解題策略歸類，可以選取一些具有代表性的例題，進行系統的、集中的分類解題策略訓練，形成一套局部范圍內的邏輯化、模式化的解題策略方案。
需要說明的是，張一博、舒天民、王禹、金陽華等同學精心編寫了所有程序，每道程序都通過了嚴格的測試驗證，多次修改、精益求精，特別是張一博和王禹同學還對本書的結構和內容提出了系統的、建設性的建議。這幾位同學為本書的出版付出了辛勤勞動，做出了不可或缺的貢獻，在此向他們表示由衷的感謝。另外，衷心感謝杭州電子科技大學劉春英老師為本書的部分試題在HDOJ上提供了在線測試平臺；衷心感謝中國臺灣的老師和同學在使用本書書稿過程中提出的寶貴意見和建議。
由于時間和水平所限，書中肯定夾雜了不少缺點和錯誤，表述不當和筆誤更是在所難免，熱切歡迎學術界同仁或讀者賜正。如果你在閱讀中發現了問題，請通過書信或電子郵件告訴我們，以便及時整理成勘誤表放在本書的網站上，供廣大讀者查詢更正。我們更期望讀者對本書提出建設性意見，以便再版時改進。我們的聯系方式如下。
通信地址：上海市邯鄲路220號復旦大學計算機科學技術學院 吳永輝
郵編：200433
Email:yhwu@fudan.edu.cn
吳永輝 王建德
2014年10月 |
內容簡介：用大量程序設計競賽的經典試題作為范例，結合程序設計的基礎知識，以問題驅動和啟發式引導為主要方式，從七個方面詳細介紹了49種解題策略和重要算法，培養讀者對問題的認知能力和編程解題的能力。本書還提供了試題的英文原版描述和大部分試題的測試數據等資料，詳細內容可從華章網站（www.hzbook.com）下載。
本書特點：
從國內外多年程序設計競賽中精選100道經典試題，啟發性地引出相應的解題策略，不僅有知識要點闡述、詳盡的試題解析、相應參考程序，還使用大量圖表增加直觀性和可讀性，方便讀者的學習和實踐。
提供了試題的原版描述、測試數據和解答程序作為參考，讀者可以通過學習培養良好的認知結構，提高編程解題能力。
書中的經典試題可用于程序設計相關課程的教學與實踐，還可用于輔導學生進行程序設計競賽的專項訓練。 |
目錄：前言
第1章 利用樹型數據關系的解題策略1
1.1 利用劃分樹求解整數區間內第k大的值1
1.1.1 離線構建整個查詢區間的劃分樹2
1.1.2 在劃分樹上查詢子區間〔l，r〕中第k大的數3
1.1.3 應用劃分樹解題4
1.2 利用最小生成樹及其擴展形式解題8
1.2.1 最小生成樹的思想和應用8
1.2.2 最優比率生成樹的思想和應用23
1.2.3 最小k度限制生成樹的思想和應用28
1.2.4 次小生成樹的思想和應用35
1.3 利用線段樹解決區間計算問題42
1.3.1 線段樹的基本概念42
1.3.2 線段樹的基本操作和拓展43
1.3.3 應用線段樹解題46
1.4 利用改進型的二叉查找樹優化動態集合的操作56
1.4.1 改進型1：伸展樹57
1.4.2 改進型2：紅黑樹60
1.4.3 應用改進型的二叉查找樹解題64
1.5 利用動態樹維護森林的連通性81
1.5.1 動態樹的問題背景81
1.5.2 Link-Cut Tree的定義82
1.5.3 Link-Cut Tree的基本操作和時間復雜度分析82
1.5.4 應用動態樹解題85
1.6 利用左偏樹實現優先隊列的合并95
1.6.1 左偏樹的定義和性質95
1.6.2 左偏樹的操作97
1.6.3 應用左偏樹解題103
1.7 利用跳躍表替代樹結構106
1.7.1 跳躍表的基本概念107
1.7.2 跳躍表的基本操作107
1.7.3 跳躍表的效率分析109
1.7.4 應用跳躍表解題111
本章小結126
第2章 利用圖型數據關系的解題策略128
2.1 利用網絡流算法解題128
2.1.1 網絡、流與割的概念128
2.1.2 利用Dinic算法計算最大流132
2.1.3 求容量有上下界的最大流問題145
2.1.4 計算最小費用最大流155
2.2 利用圖的匹配算法解題161
2.2.1 匹配的基本概念161
2.2.2 計算二分圖的最大匹配166
2.2.3 計算二分圖最佳匹配的KM算法167
2.2.4 利用一一對應的匹配性質轉化問題的實驗范例179
2.3 利用分層圖思想解題191
2.3.1 利用分層圖思想化未知為已知191
2.3.2 利用分層圖思想優化算法的實驗范例195
2.4 利用平面圖性質解題199
2.4.1 平面圖的基本概念199
2.4.2 平面圖的實驗范例200
2.4.3 偏序集的基本概念210
2.4.4 偏序集的實驗范例211
2.5 在充分挖掘和利用圖論模型性質的基礎上優化算法216
2.5.1 優化圖論模型的三種方法216
2.5.2 三種優化方法的實驗范例217
本章小結224
第3章 數據關系上的構造策略226
3.1 選擇數據邏輯結構的基本原則226
3.1.1 充分利用“可直接使用”的信息226
3.1.2 不記錄“無用”的信息230
3.2 選擇數據存儲結構的基本方法235
3.2.1 合理采用順序存儲結構235
3.2.2 必要時采用鏈式存儲結構239
3.3 科學組合多種數據結構245
3.3.1 數據結構的“并聯”246
3.3.2 數據結構的“嵌套”252
本章小結259
第4章 數據統計上的二分策略260
4.1 利用線段樹統計數據260
4.1.1 利用線段樹解決一維數據序列的統計問題260
4.1.2 利用線段樹解決二維數據區的統計問題264
4.2 基于數組統計方法268
4.2.1 利用樹狀數組解決動態統計子序列和問題269
4.2.2 采用倍增算法求解RMQ問題274
4.3 在靜態二叉排序樹上統計數據284
4.3.1 建立靜態二叉排序樹285
4.3.2 在靜態二叉排序樹上進行統計285
4.3.3 靜態二叉排序樹的應用287
4.4 在虛二叉樹上統計數據291
本章小結297
第5章 動態規劃上的優化策略298
5.1 減少狀態總數的基本策略298
5.1.1 改進狀態表示298
5.1.2 選擇適當的DP方向302
5.2 減少每個狀態決策數的基本策略307
5.2.1 利用最優決策的單調性307
5.2.2 剪枝優化315
5.2.3 合理組織狀態327
5.2.4 細化狀態轉移335
5.3 減少狀態轉移時間的基本策略340
5.3.1 減少決策時間340
5.3.2 減少計算遞推式的時間349
5.4 應對連通性問題的DP策略——基于狀態壓縮的插頭DP353
5.4.1 插頭DP的一般模式353
5.4.2 用于簡單路徑問題上的插頭DP361
5.4.3 用于棋盤染色問題上的插頭DP365
5.4.4 插頭DP中的剪枝優化373
本章小結380
第6章 計算幾何上的應對策略382
6.1 用于求解距離問題的模擬退火算法382
6.1.1 模擬退火算法的由來382
6.1.2 模擬退火算法的實現383
6.1.3 模擬退火算法的應用范例384
6.2 用于求解凸性函數極值問題的三分法393
6.2.1 三分法的基本思想393
6.2.2 三分法的應用范例394
6.3 使用剖分優化應對復合屬性的幾何圖形398
6.3.1 圓重合其他幾何圖形時的剖分策略398
6.3.2 使用三角剖分思想計算幾何圖形面積413
6.3.3 使用梯形剖分計算多邊形面積420
6.3.4 利用矩形切割思想進行幾何計算和數據統計425
6.4 利用極大化思想解決最大子矩形問題432
6.4.1 與極大化思想有關的概念432
6.4.2 尋找最大子矩形的兩種常用算法432
6.4.3 最大子矩形問題的推廣436
6.4.4 利用極大化思想解決最大子矩形問題的范例437
6.5 在求解綜合性、擴展性幾何問題中合理組合基本幾何運算444
6.5.1 在復雜的綜合性試題中合理組合基本幾何運算445
6.5.2 在空間幾何計算中合理組合基本幾何運算455
本章小結461
第7章 博弈類問題的應對策略462
7.1 利用動態博弈思想判斷輸贏462
7.2 基礎性博弈中的對抗策略467
7.2.1 巴什博弈468
7.2.2 威佐夫博弈469
7.2.3 尼姆博弈471
7.3 基礎性博弈擴展形式中的對抗策略477
7.3.1 巴什博弈的擴展——k倍動態減法游戲477
7.3.2 尼姆博弈的四種擴展形式481
7.4 使用SG函數應對一類組合游戲485
7.4.1 SG-組合游戲問題的特殊性質485
7.4.2 “翻硬幣”游戲487
7.4.3 多圖游戲491
7.5 使用數學工具surreal number應對不平等的組合游戲498
7.5.1 數學工具surreal number498
7.5.2 surreal number在組合游戲上的應用500
本章小結503 |
| 序： |
|
