算法設計與分析——以ACM大學生程序設計競賽在線題庫為例（微課版）

本書內容包括經典的算法設計技術，主要介紹數據結構和標準模板庫、遞歸與分治策略、動態規劃、貪心算法、回溯算法、分支限界算法、圖的搜索算法、圖論、數論和組合數學問題。本書包括大量的問題實例，並在北京大學、浙江大學和杭州電子科技大學在線題庫中精選原題，詳細地分析解題的方法，深入淺出地講解用到的算法，章後的上機練習題也選自在線題庫中的典型題目，供讀者練習，以鞏固所學算法。本書內容基本上涵蓋了目前大學生程序設計競賽所要掌握的算法。 本書結構清晰、內容豐富，適合作為電腦科學與技術、軟件工程以及相關學科算法課程的教材或參考書，特別適合有志於參加信息學競賽和ACM大學生程序設計競賽的讀者學習和訓練。

趙端陽，教授，1987年中國礦業大學碩士研究生畢業，留校工作兩年，1989-1999，杭州市杭州船舶工業學校任教，1999年併入浙江工業大學。從1987年起，一直從事計算機專業課程的教學。 2002.9～2003.7，到英國Plymouth大學網絡研究組，作為高級訪問學者從事網絡安全的研究。
作者在工作期間一直從事算法設計與分析的研究，從2005年起就一直指導學生參加大學生程序設計競賽，並每年都獲得浙江省大學生程序設計競賽的銀牌和銅牌，2017年度，獲得ACM大學生程序設計競賽青島和南寧賽區的銅牌，和東亞賽區的銅牌。
編寫《算法分析與設計—以大學生程序設計競賽為例》教程，清華大學出版社，2012年3月出版，2015年改版；編寫《ACM大學生程序設計競賽題解（1）》和《ACM大學生程序設計競賽題解（2）》，電子工業出版社，2010年7月出版。從2007年起承擔本科《算法分析與設計》課程的教學，本課程2013年評為浙江工業大學精品課程，2013年，獲得浙江省課堂教學改革SPOC立項。
2015年版《算法設計與分析—以ACM大學生程序設計競賽在線題庫為例》獲得浙江省“十二五優秀教材”，浙江省“十三五”新形態教材立項。

第1章算法概述
1．1引言
1．1．1算法的描述
1．1．2算法的設計
1．2算法的複雜度
1．2．1時間複雜度
1．2．2空間複雜度
1．3大學生程序設計競賽概述
1．4程序設計在線題庫

第2章數據結構和標準模板庫
2．1棧
2．2向量
2．3映射
2．4列表
2．5集合
2．6隊列
2．7優先隊列
2．8ZOJ1004Anagrams by Stack
2．9ZOJ1094Matrix Chain Multiplication
2．10ZOJ1011NTA
2．11ZOJ1062Trees Made to Order
2．12ZOJ1097Code the Tree
2．13ZOJ1156Unscrambling Images
2．14ZOJ1167Trees on the Level
2．15ZOJ1016Parencodings
2．16ZOJ1944Tree Recovery
2．17ZOJ2104Let the Balloon Rise
上機練習題

第3章遞歸與分治策略
3．1遞歸算法
3．1．1Fibonacci數列
3．1．2集合的全排列問題
3．1．3整數劃分問題
3．2分治策略
3．2．1分治策略的基本步驟
3．2．2分治策略的適用條件
3．2．3二分搜索算法
3．2．4循環賽日程表
3．2．5棋盤覆蓋問題
3．2．6選擇問題
3．2．7輸油管道問題
3．2．8半數集問題
3．2．9整數因子分解
3．2．10取餘運算
3．3ZOJ1633Big String
上機練習題

第4章動態規劃
4．1矩陣連乘積問題
4．1．1分析最優解的結構
4．1．2建立遞歸關係
4．1．3計算最優值
4．1．4構造最優解
4．2動態規划算法的基本要素
4．2．1最優子結構
4．2．2重疊子問題
4．2．3備忘錄方法
4．3最長公共子序列
4．3．1最長公共子序列的結構
4．3．2子問題的遞歸結構
4．3．3計算最優值
4．3．4構造最長公共子序列
4．4最大子段和
4．501背包問題
4．5．1遞歸關係分析
4．5．2算法實現
4．6最長單調遞增子序列
4．7數字三角形問題
4．8ZOJ1027Human Gene Functions
4．9ZOJ1074To the Max
4．10ZOJ1093Monkey and Banana
4．11ZOJ1107FatMouse and Cheese
4．12ZOJ1108FatMouses Speed
4．13ZOJ1147Formatting Text
4．14ZOJ1149Dividing
4．15ZOJ1163The Staircases
4．16ZOJ1183Scheduling Lectures
4．17ZOJ1196Fast Food
4．18ZOJ1206Win the Bonus
4．19ZOJ1227Free Candies
4．20ZOJ1234Chopsticks
上機練習題

第5章貪心算法
5．1活動安排問題
5．2貪心算法的理論基礎
5．2．1貪心選擇性質
5．2．2最優子結構性質
5．2．3貪心算法的求解過程
5．3背包問題
5．4最優裝載問題
5．5單源最短路徑
5．6最小生成樹
5．6．1最小生成樹的性質
5．6．2Prim算法
5．6．3Kruskal算法
5．7刪數問題
5．7．1問題的貪心選擇性質
5．7．2問題的最優子結構性質
5．8多處最優服務次序問題
5．8．1問題的貪心選擇性質
5．8．2問題的最優子結構性質
5．9ZOJ1012Mainframe
5．10ZOJ1025Wooden Sticks
5．11ZOJ1029Moving Tables
5．12ZOJ1076Gene Assembly
5．13ZOJ1161Gone Fishing
5．14ZOJ1171Sorting the Photos
5．15ZOJ2109FatMouse Trade
上機練習題

第6章回溯算法
6．1回溯算法的理論基礎
6．1．1問題的解空間
6．1．2回溯算法的基本思想
6．1．3子集樹與排列樹
6．2裝載問題
6．301背包問題
6．4圖的m著色問題
6．5n皇后問題
6．6旅行商問題
6．7流水作業調度問題
6．8子集和問題
6．9ZOJ1145Dreisam Equations
6．10ZOJ1157A Plug for UNIX
6．11ZOJ1166Anagram Checker
6．12ZOJ1213Lumber Cutting
上機練習題

第7章分支限界算法
7．1分支限界算法的基本理論
7．1．1分支限界算法策略
7．1．2分支結點的選擇
7．1．3提高分支限界算法的效率
7．1．4限界函數
7．2單源最短路徑問題
7．3裝載問題
7．401背包問題
7．5旅行商問題
7．6ZOJ1136Multiple
7．7回溯算法與分支限界算法的比較
上機練習題

第8章圖的搜索算法
8．1圖的深度優先搜索遍歷
8．2ZOJ1002Fire Net
8．3ZOJ1008Gnome Tetravex
8．4ZOJ1047Image Perimeters
8．5ZOJ1084Channel Allocation
8．6ZOJ1142Maze
8．7ZOJ1190Optimal Programs
8．8ZOJ1191The Die Is Cast
8．9ZOJ1204Additive equations
8．10ZOJ1245Triangles
8．11ZOJ2100Seeding
8．12圖的廣度優先搜索遍歷
8．13ZOJ1079Robotic Jigsaw
8．14ZOJ1085Alien Security
8．15ZOJ1103Hike on a Graph
8．16ZOJ1148The Game
8．17ZOJ1217Eight
8．18ZOJ1091Knight Moves
上機練習題

第9章圖論
9．1網絡流問題
9．1．1流和割的概念
9．1．2剩餘網絡和增廣路徑
9．1．3FordFulkerson算法
9．1．4EdmondsKarp算法
9．1．5ZOJ1734Power Network——EdmondsKarp算法
9．1．6ISAP算法
9．1．7ZOJ1734Power Network——ISAP算法
9．1．8Dinic算法
9．1．9ZOJ1734Power Network——Dinic算法
9．1．10最小費用流——SPFA算法
9．1．11ZOJ2404Going Home——SPFA算法
9．2二分圖匹配問題
9．2．1匹配問題
9．2．2二分圖最大匹配——匈牙利算法
9．2．3ZOJ1137Girls and Boys
9．2．4ZOJ1140Courses——匈牙利算法
9．2．5PJU1247The Perfect Stall——匈牙利算法
9．2．6HopcroftKarp算法
9．2．7ZOJ1140Courses——HopcroftKarp算法
9．2．8PJU1274The Perfect Stall——HopcroftKarp算法
9．2．9二分圖最佳匹配——Kuhn Munkres算法
9．2．10ZOJ2404Going Home——Kuhn Munkres算法
上機練習題

第10章數論
10．1擴展歐幾里得算法
10．2PJU2115C Looooops
10．3歐拉函數
10．4ZOJ1906Relatives
10．5PJU2480Longges problem
10．6PJU3696The Luckiest number
10．7中國剩餘定理
10．8ZOJ1160Biorhythms
10．9一元線性同餘方程組
10．10PJU2891Strange Way to Express Integers
10．11HDU1573X問題
上機練習題

第11章組合數學
11．1母函數
11．1．1普通型母函數
11．1．2指數型母函數
11．1．3Stirling數
11．1．4Catalan數
11．2HDU2082找單詞
11．3HDU1521排列組合
11．4HDU2065“紅色病毒”問題
11．5HDU3625Examining the Rooms
11．6POJ2084Game of Connection
11．7容斥原理與鴿巢原理
11．7．1容斥原理
11．7．2錯排問題
11．7．3鴿巢原理
11．8HDU2048“恭喜你，中獎了！”
11．9POJ2356Find a multiple
11．10ZOJ2836Number Puzzle
上機練習題

參考文獻