算法設(shè)計(jì)與分析：以ACM大學(xué)生程序設(shè)計(jì)競賽在線題庫為例（微課版）

第1章算法概述
1．1引言
1．1．1算法的描述
1．1．2算法的設(shè)計(jì)
1．2算法的復(fù)雜度
1．2．1時間復(fù)雜度
1．2．2空間復(fù)雜度
1．3大學(xué)生程序設(shè)計(jì)競賽概述
1．4程序設(shè)計(jì)在線測試題庫
第2章數(shù)據(jù)結(jié)構(gòu)和標(biāo)準(zhǔn)模板庫
2．1棧
2．2向量
2．3映射
2．4列表
2．5集合
2．6隊(duì)列
2．7優(yōu)先隊(duì)列
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
上機(jī)練習(xí)題
第3章遞歸與分治策略
3．1遞歸算法
3．1．1Fibonacci數(shù)列
3．1．2集合的全排列問題
3．1．3整數(shù)劃分問題
3．2分治策略
3．2．1分治策略的基本步驟
3．2．2分治策略的適用條件
3．2．3二分搜索算法
3．2．4循環(huán)賽日程表
3．2．5棋盤覆蓋問題
3．2．6選擇問題
3．2．7輸油管道問題
3．2．8半數(shù)集問題
3．2．9整數(shù)因子分解
3．2．10取余運(yùn)算
3．3ZOJ1633Big String
上機(jī)練習(xí)題
 
 
第4章動態(tài)規(guī)劃
4．1矩陣連乘積問題
4．1．1分析解的結(jié)構(gòu)
4．1．2建立遞歸關(guān)系
4．1．3計(jì)算值
4．1．4構(gòu)造解
4．2動態(tài)規(guī)劃算法的基本要素
4．2．1子結(jié)構(gòu)
4．2．2重疊子問題
4．2．3備忘錄方法
4．3長公共子序列
4．3．1長公共子序列的結(jié)構(gòu)
4．3．2子問題的遞歸結(jié)構(gòu)
4．3．3計(jì)算值
4．3．4構(gòu)造長公共子序列
4．4子段和
4．501背包問題
4．5．1遞歸關(guān)系分析
4．5．2算法實(shí)現(xiàn)
4．6長單調(diào)遞增子序列
4．7數(shù)字三角形問題
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
上機(jī)練習(xí)題
第5章貪心算法
5．1活動安排問題
5．2貪心算法的理論基礎(chǔ)
5．2．1貪心選擇性質(zhì)
5．2．2子結(jié)構(gòu)性質(zhì)
5．2．3貪心算法的求解過程
5．3背包問題
5．4裝載問題
5．5單源短路徑
5．6小生成樹
5．6．1小生成樹的性質(zhì)
5．6．2Prim算法
5．6．3Kruskal算法
5．7刪數(shù)問題
5．7．1問題的貪心選擇性質(zhì)
5．7．2問題的子結(jié)構(gòu)性質(zhì)
5．8多處服務(wù)次序問題
5．8．1問題的貪心選擇性質(zhì)
5．8．2問題的子結(jié)構(gòu)性質(zhì)
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
上機(jī)練習(xí)題
第6章回溯算法
6．1回溯算法的理論基礎(chǔ)
6．1．1問題的解空間
6．1．2回溯算法的基本思想
6．1．3子集樹與排列樹
6．2裝載問題
6．301背包問題
6．4圖的m著色問題
6．5n皇后問題
6．6旅行商問題
6．7流水作業(yè)調(diào)度問題
6．8子集和問題
6．9ZOJ1145Dreisam Equations
6．10ZOJ1157A Plug for UNIX
6．11ZOJ1166Anagram Checker
6．12ZOJ1213Lumber Cutting
上機(jī)練習(xí)題
第7章分支限界算法
7．1分支限界算法的基本理論
7．1．1分支限界算法策略
7．1．2分支結(jié)點(diǎn)的選擇
7．1．3提高分支限界算法的效率
7．1．4限界函數(shù)
7．2單源短路徑問題
7．3裝載問題
7．401背包問題
7．5旅行商問題
7．6ZOJ1136Multiple
7．7回溯算法與分支限界算法的比較
上機(jī)練習(xí)題
第8章圖的搜索算法
8．1圖的深度優(yōu)先搜索遍歷
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圖的廣度優(yōu)先搜索遍歷
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
上機(jī)練習(xí)題
第9章圖論
9．1網(wǎng)絡(luò)流問題
9．1．1流和割的概念
9．1．2剩余網(wǎng)絡(luò)和增廣路徑
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小費(fèi)用流——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算法
上機(jī)練習(xí)題
第10章數(shù)論
10．1擴(kuò)展歐幾里得算法
10．2PJU2115C Looooops
10．3歐拉函數(shù)
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問題
上機(jī)練習(xí)題
第11章組合數(shù)學(xué)
11．1母函數(shù)
11．1．1普通型母函數(shù)
11．1．2指數(shù)型母函數(shù)
11．1．3Stirling數(shù)
11．1．4Catalan數(shù)
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
上機(jī)練習(xí)題
參考文獻(xiàn)