本書從ACM-ICPC程序設(shè)計競賽等各種程序設(shè)計競賽的試題進行了分析和整理，并精選出典型試題進行分類解析，既可用于高校算法、程序設(shè)計課程的實驗和教學(xué)，也可以用于競賽選手的系統(tǒng)訓(xùn)練。
本書是“大學(xué)程序設(shè)計課程與競賽訓(xùn)練教材”系列著作中的第2部。我們編著這一系列著作的指導(dǎo)思想如下。
�。�1）程序設(shè)計競賽是“通過編程解決問題”的競賽。國際大學(xué)生程序設(shè)計競賽（International Collegiate Programming Contest，ICPC）和中學(xué)生國際信息學(xué)奧賽（International Olympiad in Informatics，IOI）在20世紀(jì)80年代中后期走向成熟，30多年來，累積了海量的試題。這些來自全球各地、凝聚了無數(shù)命題者的心血和智慧的試題，不僅可以用于程序設(shè)計競賽選手的訓(xùn)練，而且可以用于教學(xué)，以系統(tǒng)、全面地提高學(xué)生編程解決問題的能力。
�。�2）我們認(rèn)為，評價一個人的專業(yè)能力，要看這個人的兩個方面：1）知識體系，即他能用哪些知識去解決問題，或者說，他所真正掌握并能應(yīng)用的知識，而不僅僅是他學(xué)過的知識；2）思維方式，即他在面對問題（特別是不太標(biāo)準(zhǔn)化的問題）的時候，解決問題的策略是什么？對于程序設(shè)計競賽選手所要求的知識體系，可以概括為1984年圖靈獎得主Niklaus Wirth提出的著名公式“算法+數(shù)據(jù)結(jié)構(gòu)=程序”，這也是計算機學(xué)科知識體系的核心部分，因此本系列的前兩部著作分別是《數(shù)據(jù)結(jié)構(gòu)編程實驗》和《算法設(shè)計編程實驗》。對于需要采用某些策略進行求解的程序設(shè)計試題，比如，不采用常用的數(shù)據(jù)結(jié)構(gòu)或者需要優(yōu)化解題的算法，我們進行分析整理，編寫了本系列的第3部著作《程序設(shè)計解題策略》。
�。�3）從本質(zhì)上說，程序設(shè)計是技術(shù)，所以，首先牢記學(xué)習(xí)編程要不斷“Practice，Practice，Practice”！本系列選用程序設(shè)計競賽的大量試題，以案例教學(xué)的方式進行教學(xué)實驗并安排學(xué)生進行解題訓(xùn)練。其次，“Practice in a systematic way”。本系列的編寫基于傳統(tǒng)的教學(xué)大綱，以系統(tǒng)、全面地提高學(xué)生編程解決問題的能力為目標(biāo)，以程序設(shè)計競賽的試題及詳細的解析、帶注釋的程序作為實驗，在每一章的結(jié)束部分給出相關(guān)題庫及解題提示，并對大部分試題給出官方的測試數(shù)據(jù)。
2013年，我們在機械工業(yè)出版社出版了《算法設(shè)計編程實驗：大學(xué)程序設(shè)計課程與競賽訓(xùn)練教材》。2018年，我們在CRCPress出版了該書的英文版《Algorithm Design Practice： for Collegiate Programming Contest and Education》。此外，我們還在中國臺灣地區(qū)出版了繁體中文版。
吳永輝，博士，復(fù)旦大學(xué)計算機科學(xué)技術(shù)學(xué)院副教授，美國石溪大學(xué)訪問學(xué)者，ICPC亞洲程序設(shè)計競賽首訓(xùn)練委員會主席。他曾率隊在ICPC世界總決賽上獲得三枚獎牌，并應(yīng)邀在阿曼、孟加拉國、馬來西亞、美國的多所高校長期講學(xué)。
王建德，信息學(xué)奧林匹克競賽教練，國務(wù)院特殊津貼專家，中學(xué)特級教9幣。他所輔導(dǎo)的學(xué)生曾在國際信息學(xué)競賽（IOI）中獲得7金、3銀、2銅的優(yōu)異成績。他先后出版了24本關(guān)于程序設(shè)計和算法的學(xué)術(shù)專著。
前言
第1章 求解AdHoc類問題的編程實驗
1．1 機理分析法的實驗范例
1．2 統(tǒng)計分析法的實驗范例
1．3 相關(guān)題庫
第2章 模擬法的編程實驗
2．1 直敘式模擬的實驗范例
2．2 篩選法模擬的實驗范例
2．3 構(gòu)造法模擬的實驗范例
2．4 相關(guān)題庫
第3章 數(shù)論的編程實驗
3．1 素數(shù)運算的實驗范例
3．1．1 使用篩法生成素數(shù)
3．1．2 測試大素數(shù)
3．2 求解不定方程和同余的實驗范例
3．2．1 計算最大公約數(shù)和不定方程
3．2．2 計算同余方程和同余方程組
3．2．3 計算多項式同余方程
3．3 特殊的同余式的實驗范例
3．3．1 威爾遜定理和費馬小定理
3．3．2 偽素數(shù)
3．3．3 歐拉定理
3．4 積性函數(shù)的實驗范例
3．4．1 歐拉φ函數(shù)φ（n）
3．4．2 莫比鳥斯函數(shù)μ（n）
3．4．3 完全數(shù)和梅森素數(shù)
3．5 高斯素數(shù)的實驗范例
3．6 相關(guān)題庫
第4章 組合分析的編程實驗
4．1 生成排列的實驗范例
4．1．1 按字典序思想生成下一個排列
4．1．2 按字典序思想生成所有排列
4．2 排列組合計數(shù)的實驗范例
4．2．1 一般的排列組合計數(shù)公式
4．2．2 兩種特殊的排列組合計數(shù)公式
4．2．3 多重集的排列數(shù)和組合數(shù)
4．3 鴿籠原理與容斥原理的實驗范例
4．3．1 利用鴿籠原理求解存在性問題
4．3．2 容斥原理應(yīng)用實驗
4．3．3 Ramsey定理的應(yīng)用
4．4 Polya計數(shù)公式的實驗范例
4．5 生成函數(shù)與遞推關(guān)系的實驗范例
4．5．1 冪級數(shù)型生成函數(shù)
4．5．2 指數(shù)型生成函數(shù)
4．5．3 遞推關(guān)系
4．6 快速傅里葉變換的實驗范例
4．7 相關(guān)題庫
第5章 貪心法的編程實驗
5．1 體驗貪心法內(nèi)涵的實驗范例
5．1．1 貪心法的經(jīng)典問題
5．1．2 體驗貪心法內(nèi)涵
5．2 利用數(shù)據(jù)有序化進行貪心選擇的實驗范例
5．3 在綜合性的P類問題中使用貪心法的實驗范例
5．4 相關(guān)題庫
第6章 動態(tài)規(guī)劃方法的編程實驗
6．1 線性DP的實驗范例
6．1．1 初步體驗線性DP問題
6．1．2 子集和問題
6．1．3 最長公共子序列問題
6．1．4 最長遞增子序列問題
6．2．1 背包問題
6．2．1 基本的0-1背包問題
6．2．2 完全背包
6．2．3 多重背包
6．2．4 混合背包
6．2．5 二維背包
6．2．6 分組背包
6．2．7 有依賴的背包
6．3 樹形DP的實驗范例
6．4 狀態(tài)壓縮DP的實驗范例
6．5 單調(diào)優(yōu)化1D/1DDP的實驗范例
6．5．1 經(jīng)典模型1：利用決策代價函數(shù)w的單調(diào)性優(yōu)化
6．5．2 經(jīng)典模型2：利用決策區(qū)間下界的單調(diào)性優(yōu)化
6．5．3 經(jīng)典模型3：利用最優(yōu)決策點的凸性優(yōu)化
6．6 相關(guān)題庫
第7章 高級數(shù)據(jù)結(jié)構(gòu)的編程實驗
7．1 后綴數(shù)組的實驗范例
7．1．1 使用倍增算法計算名次數(shù)組和后綴數(shù)組
7．1．2 計算最長公共前綴
7．1．3 后綴數(shù)組的應(yīng)用
7．2 線段樹的實驗范例
7．2．1 線段樹的基本概念和基本操作
7．2．2 線段樹單點更新的維護
7．2．3 線段樹子區(qū)間更新的維護
7．3 處理特殊圖的實驗范例
7．3．1 計算歐拉圖
7．3．2 計算哈密頓圖
7．3．3 計算最大獨立集
7．3．4 計算割點、橋和雙連通分支
7．4 相關(guān)題庫
第8章 計算幾何的編程實驗
8．1 點線面運算的實驗范例
8．1．1 計算點積和叉積
8．1．2 計算線段交
8．1．3 利用歐拉公式計算多面體
8．2 利用掃描線算法計算矩形的并的面積的實驗范例
8．2．1 沿垂直方向計算矩形的并面積
8．2．2 沿水平方向計算矩形的并面積
8．3 計算半平面交的實驗范例
8．3．1 計算半平面交的聯(lián)機算法
8．3．2 利用極角計算半平面交的算法
8．4 計算凸包和旋轉(zhuǎn)卡殼的實驗范例
8．4．1 計算凸包
8．4．2 旋轉(zhuǎn)卡殼實驗
8．5 相關(guān)題庫
書單推薦
