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

"趙端陽,研究領域：程序設計與算法、信息安全研究成果：主持浙江省高等教育課堂教學改革研究項目《C++程序設計》和《算法分析與設計》，教材《算法設計與分析—以ACM大學生程序設計競賽在線題庫為例》被評為浙江省“十二五”優秀教材，本教材獲得浙江省普通高校“十三五”首批新形態教材項目的支持。擔任大學生程序設計競賽教練15年，指導學生獲得多個省級競賽銀牌和亞洲區域賽銅牌。"

 

目錄

第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.10ZOJ1097Code the Tree

 

2.11ZOJ1156Unscrambling Images

 

2.12ZOJ1167Trees on the Level

 

2.13ZOJ1016Parencodings

 

2.14ZOJ1944Tree Recovery

 

2.15ZOJ2104Let the Balloon Rise

 

上機練習題

 

 

 

 

 

 

 

第3章遞歸與分治策略

 

3.1遞歸算法

 

3.1.1斐波那契數列

 

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.3ZOJ1633Big String

 

3.4洛谷P1182 數列分段 Section Ⅱ

 

3.5洛谷P1824 進擊的奶牛

 

3.6洛谷P1873砍樹

 

3.7洛谷P1908逆序對

 

上機練習題

 

第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.10ZOJ1107FatMouse and Cheese

 

4.11ZOJ1108FatMouses Speed

 

4.12ZOJ1163The Staircases

 

4.13ZOJ1196Fast Food

 

4.14ZOJ1234Chopsticks

 

4.15ZOJ3211 Dream City

 

4.16ZOJ3956 Course Selection System

 

4.17洛谷P2758編輯距離

 

4.18洛谷P1130紅牌

 

4.19洛谷P1063能量項鏈

 

4.20洛谷P2016 戰略遊戲

 

4.21洛谷P1352 沒有上司的舞會

 

4.22洛谷P1122 最大子樹和

 

4.23洛谷P2014 選課

 

4.24洛谷P2015二叉蘋果樹

 

上機練習題

 

第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.8ZOJ1012Mainframe

 

5.9ZOJ1025Wooden Sticks

 

5.10ZOJ1076Gene Assembly

 

5.11ZOJ2109FatMouse Trade

 

5.12洛谷P1717 釣魚

 

5.13洛谷P1230智力大沖浪

 

5.14洛谷U167571信使

 

5.15HDU1863 暢通工程

 

5.16洛谷P2330 繁忙的都市

 

上機練習題

 

第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.9ZOJ1457Prime Ring

 

6.10ZOJ2110Tempter of the Bone

 

6.11ZOJ2734Exchange Cards

 

6.12洛谷P1378 油滴擴展

 

6.13經典題——工作分配問題

 

6.14洛谷P1692 部落衛隊

 

上機練習題

 

第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

 

上機練習題

 

第8章圖的搜索算法

 

8.1圖的深度優先搜索遍歷

 

8.2ZOJ1002Fire Net

 

8.3ZOJ1047Image Perimeters

 

8.4ZOJ1191The Die Is Cast

 

8.5ZOJ1204Additive equations

 

8.6ZOJ2100Seeding

 

8.7洛谷P1162填塗顏色

 

8.8洛谷P1363幻象迷宮

 

8.9洛谷P1605 迷宮

 

8.10洛谷P2895 Meteor Shower S

 

8.11POJ1164 The Castle

 

8.12圖的廣度優先搜索遍歷

 

8.13ZOJ1148The Game

 

8.14ZOJ1091Knight Moves

 

8.15經典算法題——迷宮的最短路徑

 

8.16洛谷P1983 車站分級

 

8.17洛谷P2802 回家

 

8.18洛谷P4554小明的遊戲

 

8.19ZJU1649 Rescue

 

上機練習題

 

第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

 

上機練習題

 

參考文獻