算法分析与设计

作者简介

《算法分析与设计:以大学生程序设计竞赛为例》主要介绍经典的算法设计技术，内容包括数据结构和标准模板库STL、递归与分治策略、动态规划、贪心算法、回溯算法、分支限界算法和图的搜索算法。《算法分析与设计:以大学生程序设计竞赛为例》内容基本上涵盖了目前大学生程序设计竞赛所要掌握的算法。《算法分析与设计:以大学生程序设计竞赛为例》通过大量的问题剖析实例，并在浙江大学在线题库中精选了部分题目，详细地分析解题的方法，深入浅出地讲解所使用的算法。还把在浙江大学在线题库中精选的题目作为每章后面的习题，供读者练习，以巩固所学的算法。

《算法分析与设计:以大学生程序设计竞赛为例》可作为计算机科学与技术系、软件学院、数学系等专业本科及研究生课程的教材，特别适合有志于参加大学生程序设计竞赛的学生学习和训练。

书籍目录

第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.8 ZOJ1004AnagramsbyStack

2.9 ZOJ1094MatrixChainMultiplication

2.1 0ZOJ1011NTA

2.1 1ZOJ1062TreesMadetoOrder

2.1 2ZOJ1097CodetheTree

2.1 3ZOJ1156UnscramblingImages

2.1 4ZOJ1167TreesontheLevel

2.1 5ZOJ1016Parencodings

2.1 6ZOJ1944TreeRecovery

2.1 7ZOJ2104LettheBalloonRise

上机练习题

第3章 递归与分治策略

3.1 递归算法

3.1.1 Fibonacci数列

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.1 0取余运算

3.3 BigString

上机练习题

第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.5　01背包问题

4.5.1 递归关系分析

4.5.2 算法实现

4.6 最长单调递增子序列

4.7 数字三角形问题

4.8 ZOJ1013GreatEquipment

4.9 ZOJ1027HumanGeneFunctions

4.1 0ZOJ1074TotheMax

4.1 1ZOJ1093MonkeyandBanana

4.1 2ZOJ1100MondriaansDream

4.1 3ZOJ1102PhylogeneticTreesInherited

4.1 4ZOJ1107FatMouseandCheese

4.1 5ZOJ1108FatMousesSpeed

4.1 6ZOJ1132Railroad

4.1 7ZOJ1147FormattingText

4.1 8ZOJ1149Dividing

4.1 9ZOJ1163TheStaircases

4.2 0ZOJ1183SchedulingLectures

4.2 1ZOJ1196FastFood

4.2 2ZOJ1206WintheBonus

4.2 3ZOJ1227FreeCandies

4.2 4ZOJ1234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.2　Prim算法

5.6.3　Kruskal算法

5.7 删数问题

5.7.1 问题的贪心选择性质

5.7.2 问题的最优子结构性质

5.8 多处最优服务次序问题

5.8.1 问题的贪心选择性质

5.8.2 问题的最优子结构性质

5.9　ZOJ1012 Mainframe

5.10 ZOJ1025 WoodenSticks

5.11 ZOJ1029 MovingTables

5.12 ZOJ1076 GeneAssembly

5.13 ZOJ1161 GoneFishing

5.14 ZOJ1171 SortingthePhotos

5.15 ZOJ2109 FatMouse Trade

上机练习题

第6章 回溯算法

6.1 回溯算法的理论基础

6.1.1 问题的解空间

6.1.2 回溯法的基本思想

6.1.3 子集树与排列树

6.2 装载问题

6.3　01背包问题

6.4 图的m着色问题

6.5 n皇后问题

6.6 旅行商问题

6.7 流水作业调度问题

6.8 子集和问题

6.9 ZOJ1145DreisamEquations

6.1 0ZOJ1157APlugforUNIX

6.1 1ZOJ1166AnagramChecker

6.1 2ZOJ1213LumberCutting

上机练习题

第7章 分支限界算法

7.1 分支限界算法的基本理论

7.1.1 分支限界算法策略

7.1.2 分支结点的选择

7.1.3 提高分支限界算法的效率

7.1.4 限界函数

7.2 单源最短路径问题

7.3 装载问题

7.4　01背包问题

7.5 旅行商问题

7.6 ZOJ1136Multiple

7.7 回溯算法与分支限界算法的比较上机练习题

第8章 图的搜索算法

8.1 图的深度优先搜索遍历

8.2　ZOJ1002 FireNet

8.3　ZOJ1008 GnomeTetravex

8.4　ZOJ1047 ImagePerimeters

8.5　ZOJ1084 ChannelAllocation

8.6　ZOJ1142 Maze

8.7　ZOJ1190 OptimalPrograms

8.8　ZOJ1191 TheDieIsCast

8.9 ZOJ1204 AdditiveEquations

8.1 0 ZOJ1245 Triangles

8.11　ZOJ2100 Seeding

8.12 图的广度优先搜索遍历

8.13 ZOJ1055 Oh,ThoseAchinFeet

8.14 ZOJ1079 RoboticJigsaw

8.15 ZOJ1085 AlienSecurity

8.16 ZOJ1103 HikeonaGraph

8.17 ZOJ1148 TheGame

8.18 ZOJ1217 Eight

8.19 ZOJ1091 KnightMoves

上机练习题

参考文献

编辑推荐

《算法分析与设计:以大学生程序设计竞赛为例》内容主要介绍经典的算法设计技术，包括数据结构和标准模板库STL等。教学门标明确，注重理论与实践的结合。教学方法灵活，培养学生自主学习的能力。教学内容先进，反映了计算机学科的最新发展。教学模式完善，提供配套的教学资源解决方案。

前言

　　“算法分析与设计”是一门理论性与实践性结合很强的课程。在信息技术高速发展的今天，计算机技术已经应用到了很多科学领域。从理论上来说，算法研究已经被公认为是计算机科学的基石。David Harel在他的《算法学： 计算精髓》一书中说道： “算法不仅是计算机科学的一个分支，它更是计算机科学的核心。可以毫不夸张地说，它和绝大多数的科学、商业和技术都是相关的。”　　近年来，针对大学生的各种类型的程序设计竞赛开展得越来越多，比较常见的有ACM?ICPC、TopCoder、百度之星、Google挑战赛、有道难题等。其中ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，ACM?ICPC），是历史最悠久、规模最大的竞赛。竞赛题目涉及的知识面广，难度大； 主要强调算法的高效性，不仅要解决一个指定的命题，而且必须要以最佳的方式解决指定的命题； 涉及知识与大学计算机专业本科以及研究生如程序设计、离散数学、数据结构、人工智能、算法分析与设计等相关课程直接关联，对数学要求很高。　　在ACM国际大学生程序设计竞赛中，在线裁判系统是开展竞赛的核心，它是一个在线的程序与算法设计的练习和竞赛平台。系统可以提供大量的关于程序和算法设计的题目供学生练习或竞赛，学生可以使用自己熟悉的语言提交相关题目的程序代码，系统编译提交代码，如果没有错误，则生成可执行文件。利用系统的测试用例来测试，如果输出结果正确，则返回程序消耗的内存空间和时间。对于竞赛题目，系统可以从程序正确性、运行总时间、消耗内存空间、返回结果等方面来考查学生提交的代码。系统可以实现在指定的时间段举行竞赛的功能，根据学生解题数目和时间进行排名，也可以批量导出学生代码进行分析。　　基于程序设计竞赛的教学模式的优势： 　　（1） 提供了一个开放的、自主学习的实验环境，在线评测系统通过网络使用，学生可以随时随地地提交程序代码，并可在丰富的程序与算法设计题库中寻找适合自己的题目，训练程序设计能力。　　（2） 有效地训练了学生程序设计能力，培养创新型IT人才。本课程的学习难点在于如何将常见的算法策略应用到实际的应用环境中。通过在线评测系统的实践训练，让学生熟练掌握常见的算法设计策略，训练学生的创新思维，加深学生对各种算法设计策略的认识，使学生理解算法的意义及精髓，达到学以致用。　　（3） 形成了良好的学习氛围，加强了学生之间的交流。使用在线评测系统进行课程考核并举办程序与算法设计竞赛，学生以团队方式参与，可以形成良好的校园竞争和交流的学习氛围； 使学生有了在课余时间自主进行本学科知识钻研的机会和环境； 也让学生体验团队协作的重要性，为软件项目团队化的合作要求做好准备。　　算法分析与设计是面向设计的核心课程，主要通过介绍常见的算法设计策略及复杂性分析方法，培养学生分析问题和解决问题的能力，为开发高效的软件系统及参加相关领域的研究工作奠定坚实的基础。该课程理论与实践并重，内容具有综合性、广泛性和系统性，是一门集应用性、创造性及实践性为一体的综合性极强的课程。　　目前，该课程的教学方法还是以传统的讲解为主，通常只是将经典算法在已有的数学模型和数据结构上解释给学生； 在实践环节只是盲目地验证算法，而对该算法的运行效率、测试数据规模以及实际的应用场景则很少考虑。学生的学习则主要以理解和记忆的继承式学习为主，虽然记住了大量的算法理论，但没有“理解”和“消化”，不能灵活运用算法； 在实践环节学生代码抄袭严重，很难达到训练的效果。在这种教学模式下，学生缺乏问题抽象能力，在遇到实际问题时无从下手，思维创新能力和实践能力难以得到有效的提高，很难培养出高水平的程序员。　　本书利用程序设计竞赛模式和在线评测系统的特点，结合课程特点和实际教学，弥补课程教学中存在的不足，以此探讨算法分析与设计的课程教学改革，培养高水平的编程人才。　　本书共分为8章。　　第1章算法概述： 主要是算法的基本概念、算法的复杂性、大学生程序设计竞赛概述和程序设计在线题库的基本情况。　　第2章数据结构和标准模板库STL： 主要介绍栈（Stack）、向量（Vector）、映射（Map）、列表（List）、集合（Set）、队列（Queue）和优先队列（Priority Queue），并应用这些STL解题： ZOJ1004?Anagrams by Stack，ZOJ1094?Matrix Chain Multiplication，ZOJ1062?Trees Made to Order和ZOJ1944?Tree Recovery等。　　第3章递归与分治策略： 主要介绍递归算法和分治策略。典型例题有循环赛日程表、棋盘覆盖问题、选择问题和整数因子分解等。　　第4章动态规划： 主要介绍动态规划算法的基本要素。典型例题有矩阵连乘积、最长公共子序列、最大子段和、0?1背包问题和最长单调递增子序列等，并求解ZOJ1013?Great Equipment、Human Gene Functions、To the Max、FatMouse and Cheese和Railroad等问题。　　第5章贪心算法： 主要介绍贪心算法的理论基础。典型例题有活动安排问题、背包问题、最优装载问题、单源最短路径和最小生成树等，并求解ZOJ1012?Mainframe、ZOJ1025?Wooden Sticks、ZOJ1076?Gene Assembly和ZOJ2109?FatMouse? Trade等问题。　　第6章回溯算法： 主要介绍回溯算法的理论基础。典型例题有装载问题、0?1背包问题、图的m着色问题、n皇后问题、旅行商问题和流水作业调度问题等，并求解ZOJ1145?Dreisam Equations、ZOJ1157?A Plug for UNIX和ZOJ1166?Anagram Checker等问题。　　第7章分支限界算法： 主要介绍分支限界算法的基本理论，并对回溯算法与分支限界算法进行比较。典型例题有单源最短路径问题、装载问题、0?1背包问题和旅行商问题，并求解ZOJ1136?Multiple。　　第8章图的搜索算法： 主要介绍图的深度和广度优先搜索遍历算法。求解ZOJ1002?Fire Net、ZOJ1142?Maze、ZOJ1245?Triangles、ZOJ1079? Robotic Jigsaw、ZOJ1217?Eight和ZOJ1091?Knight Moves等问题。　　袁鹤、冯志林、吴艳、金献珍、金海溶和曹平老师参加了本书的编写工作。

章节摘录

版权页：插图：5.可行性在有限时间内完成计算过程。算法1.1用一个正整数来除另一个正整数，判断一个整数是否为0以及整数赋值等，这些运算都是可行的。因为整数可以用有限的方式表示，所以至少存在一种方法来完成一个整数除以另一个整数的运算。必须注意到，在实际应用中，有限性的限制是不够的。一个实用的算法，不仅要求步骤有限，同时要求运行这些步骤所花费的时间是人们可以接受的。如果一个算法需要执行数万亿亿计数的运算步骤，从理论上说，它是有限的，最终可以结束。但是，以当代计算机每秒数亿次的运算速度，也必须运行数百年以上，这是人们所无法接受的，因而它是不实用的算法。1.1.2 算法的设计算法设计的整个过程，可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。计算机科学家尼克劳斯·沃思曾著过一本著名的书《数据结构+算法一程序》，可见算法在计算机科学界与计算机应用界的地位。同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择适用算法和改进算法。一个算法的评价主要从时间复杂性和空间复杂性来考虑。算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法和并行算法。算法大致分为以下三类。

图书封面

---

 算法分析与设计下载

---