【正文】 計算機科學與技術(shù)系 修訂版 ICPC培訓講義 算法與程序設計 I C P C 培訓講義 算法與程序設計 ? 計算機科學與技術(shù)系 合肥工業(yè)大學 2020 年 3 月 修訂版 ii 前 言 ACM／ ICPC 是由國際計算機學界著名的 ACM 學會主辦，世界上公認的規(guī)模最大、水平最高的國際大學生程序設計競賽，它充分地展示了大學生分析問題和解決問題的能力，這項比賽，歷來為國際知名大學所重視，競賽分區(qū)域預賽和國際決賽兩個階段進行，各賽區(qū)預賽的第一名獲參加決賽的資格 （ 第二名 視情況而定） 。 中國的上海賽區(qū)于 1995 年度試舉辦，我校未參賽 ，從 1996 年正式舉辦起，我校每年都參加，并多次取得了較好的成績，為了更好的組織今后的比賽，我們于 2020 年開始著手編寫了這本講義，并希望作為資料保存下去，每年都得以增加更多更新的內(nèi)容。 本書是由徐本柱主持，其中 初始 由 李曉泉 、 萬郁香 、 許嵩罡 、 周晉 、 龐博 、 曹力 和沈揚參與編寫的， 李曉泉 寫了 圖論及搜索 部分， 萬郁香 寫了 模擬類 部分， 許嵩罡 寫了 畫法幾何 部分， 周晉 寫了 密碼 部分，龐博 寫了 字符串處理 部分， 曹力 寫了 組合數(shù)學 部分， STL 簡介部分有許松罡和沈揚合寫?，F(xiàn)在大家使用的 后由 許嵩罡 負責整理并增加了動態(tài)規(guī)劃部分。 本次修訂版有 阮政、王洪剛和陳昊參與修訂，重寫了STL 和組合數(shù)學部分，并增加了算法優(yōu)化專題。 全書由徐本柱審校，由于時間匆忙，加上作者水平有限，錯誤難免，希望廣大同學批評指正。 徐本柱 2020 年 3 月 iii 目 錄 前 言 .......................................................................................................................................................... II 目 錄 ................................................................................................................................................. iii 第一章 STL 簡介 ........................................................................................................................................1 一、引 言 ..............................................................................................................................................1 二、 STL 組成結(jié)構(gòu) .....................................................................................................................................2 三、 STL 的應用 ..........................................................................................................................................3 第二章 搜 索 ...................................................................................................................................... 28 一、 寬度優(yōu)先搜索 BFS ......................................................................................................................... 28 二、最小生成樹的形成和求解 (PRIM AND KRUSKAL) ......................................................................... 34 1. 最小生成樹的形成 .............................................................................................................................. 34 2． Kruskal 算法和 Prim 算法 ............................................................................................................. 37 三、深度優(yōu)先搜索 DFS ......................................................................................................................... 44 ..................................................................................................................................................... 44 ........................................................................................................................ 48 3. 邊的分類 ........................................................................................................................................... 50 第三章 計算幾何學 .................................................................................................................................... 53 一、引 言 .............................................................................................................................................. 53 二、線段的性質(zhì)（ LINESEGMENT PROPERITIES） ................................................................................ 54 （ Cross Product） .................................................................................................................... 54 （ Determining Intersections） ................................................................................ 55 三、點集的性質(zhì) （ POINTSET PROPERITIES） ....................................................................................... 57 （ Finding the convex hull） ............................................................................................. 57 第四章 動態(tài)規(guī)劃 ........................................................................................................................................ 63 一、引言 —— 由一個問題引出的算法 ................................................................................................. 63 二、動態(tài)規(guī)劃的基本概念 ...................................................................................................................... 65 動態(tài)規(guī)劃的發(fā)展及研究內(nèi)容 ........................................................................................................ 65 多階段決策問題 ............................................................................................................................. 65 決策過程的分類 ............................................................................................................................. 66 三、動態(tài)規(guī)劃模型的基本要素 .............................................................................................................. 66 四、動態(tài)規(guī)劃的基本定理和基本方程 ................................................................................................. 68 五、動態(tài)規(guī)劃的適用條件 ...................................................................................................................... 69 最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)） ................................................................................................ 69 無后向性 ......................................................................................................................................... 70 子問題的重疊性 ............................................................................................................................. 70 六、動態(tài)規(guī)劃的基本思想 ...................................................................................................................... 71 七、動態(tài)規(guī)劃算法的基本步驟 .............................................................................................................. 72 八、 動態(tài)規(guī)劃的實例分析 ......................................