计算机算法与程序设计实践

出版时间：2010-5  出版社：清华大学出版社  作者：董东，周丙寅 编  页数：456  
Tag标签：无  

前言

　　教育部计算机科学与技术教学指导委员会在《高等学校计算机科学与技术专业发展战 略研究报告暨专业规范（试行）》提出“加强学生实践和动手能力的培养”。接着，在《高等学校 计算机科学与技术专业实践教学体系与规范》中提出计算机专业高级人才的基本学科能力 包括：计算思维能力、算法设计与分析能力、程序设计与实现能力和系统分析、开发和应用能 力。其中，计算思维能力主要包括形式化、模型化、抽象化能力和逻辑推演能力。　　给定一个问题，能够将其进行抽象，建立模型；然后，综合运用各种知识，设计出求解问 题的有效算法；最后，通过程序设计实现算法，以求解问题。这在当前计算学科教学环节中， 越来越受到重视。为了强化学生对学科基本知识、基本方法、问题求解基本思想的掌握，需要 通过实践教学，让学生亲身体验，在实践中理解并运用。通过实践，不仅可以培养运用各种知 识解决实际问题的能力，而且还可以引导学生对未知进行探索，培养创新能力。在我们的教 学实践中，通过设置“问题求解与程序设计”、“信息学竞赛”、“算法分析与设计”等课程，通过 鼓励和组织学生参加ACM国际大学生程序设计竞赛（ACM／ICPC），以图提高学生基本学 科能力和动手实践能力。　　AcM／ICPC是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛。竞赛充 分展示了大学生程序设计与问题求解能力，是一种行之有效的实践教学形式。作为一种全新 的发现和培养计算学科顶尖学生的方式，AcM／IcPC得到全世界各大学的积极响应。在 2008年第33届ACM／ICPc亚洲区预选赛中，168所高校的1190支队伍参加了杭州赛区的 网络预选赛；137所高校的803支队伍参加了合肥赛区的网络预选赛；138所高校的905支 队伍参加了北京赛区的网络预选赛；151所高校的838支队伍参加了成都赛区的网络预选 赛；152所高校的1145支队伍参加了哈尔滨赛区的网络预选赛。　　本书主要目的是服务于计算学科相关专业的实践教学环节，专注于问题求解。其特色在 于：面向实践、面向过程、面向实用。沿着“问题一建立模型一设计算法一程序设计一测试与 调试”的线索，综合应用各门课程知识。　　全书共分13章。第1章介绍算法与程序、算法复杂性分析及ACM／ICPC题目特点、解 题原则等内容；第2章至第13章分别介绍数据结构、字符串、模拟、高精度计算、递归与分 治、递推、贪心、动态规划、搜索、图论、数学和计算几何的基本知识，针对若干相应问题分析 和设计算法并编程求解，给出相关训练题集。

内容概要

　　《计算机算法与程序设计实践》专注于综合应用各种算法思想进行程序设计以实现问题求解，其特色在于：面向实践、面向过程、面向实用。在风格上追求简单明快，并力图展示问题求解过程，而不仅仅是给出结果。书中不仅分析题目、设计算法，还按照统一的程序设计风格编程实现算法。　　全书共分13章。第1章介绍算法与程序、算法复杂性分析及AcM／ICPC题目特点、解题原则等内容；第2章至第13章分别介绍数据结构、字符串、模拟、高精度计算、递归与分治、递推、贪心、动态规划、搜索、图论、数学和计算几何的基本知识，针对若干相应问题分析和设计算法并编程求解。

书籍目录

第1章 基本知识1.1 算法与程序1.2 算法复杂性分析1.3 ACM／ICPC问题求解1.3.1 竞赛的特点1.3.2 常见问题类型1.3.3 解题的几点原则1.3.4 解题的几点权衡第2章 数据结构2.1 知识概述2.1.1 线性表2.1.2 栈2.1.3 队列2.1.4 集合2.1.5 树2.1.6 图2.1.7 查找2.1.8 排序2.2 例题解析2.2.1 TheMostFrequentNumbei2.2.2 BooleanExpressions2.2.3 PrinterQueue2.2.4 IsItATree2.2.5 FindingNemo2.2.6 TOYS2.2.7 Babelfish2.2.8 TheSuspects2.2.9 Atlantis2.2.10 Stars2.2.11 WordPuzzles2.3 训练集第3章 字符串操作3.1 知识概述3.2 例题解析3.2.1 VerticalHistogram3.2.2 InstruensFabulam3.2.3 English-NumberTranslatot3.2.4 References3.3 训练集第4章 模拟4.1 知识概述4.2 例题解析4.2.1 ALessSimpleTaskinWindows4.2.2 TheSameGame4.2.3 Robocode4.2.4 TempusetmobiliusTimeandmotion4.3 训练集第5章 高精度计算5.1 知识概述5.2 例题解析5.2.1 ContinuousFractions5.2.2 Exponentiation5.2.3 Heritage5.3 训练集第6章 递归与分治6.1 知识概述6.2 例题解析6.2.1 RedandBlack6.2.2 FractaI6.2.3 SticksProblem6.3 训练集第7章 递推7.1 知识概述7.2 例题解析7.2.1 Tiling7.2.2 WorldCupNoise7.2.3 ComputerTransformation7.2.4 ParallelExpectations7.3 训练集第8章 贪心8.1 知识概述8.2 例题解析8.2.1 RadarInstallation8.2.2 GoneFishing8.2.3 Supermarket8.3 训练集第9章 动态规划9.1 知识概述9.2 例题解析9.2.1 Bridgingsignals9.2.2 HumanGeneFunctions9.2.3 WashingClothes9.2.4 TotheMax9.2.5 AppleTree9.2.6 Coloredstones9.3 训练集第10章 搜索10.1 枚举10.1.1 知识概述10.1.2 例题解析10.1.3 训练集10.2 广度优先搜索10.2.1 知识概述10.2.2 例题解析10.2.3 训练集10.3 深度优先搜索10.3.1 知识概述10.3.2 例题解析10.3.3 训练集10.4 启发式搜索10.4.1 知识概述10.4.2 例题解析10.4.3 训练集第11章 图论11.1 知识概述11.2 例题解析11.2.1 StockbrokerGrapevine11.2.2 PicnicPlanning11.2.3 SortingItAllOut11.2.4 SPF11.2.5 PowerNetwork11.2.6 PurifyingMachine11.2.7 PlayonWords11.2.8 ChannelAllocation11.3 训练集第12章 数学12.1 知识概述12.2 例题解析12.2.1 PrimeDistance12.2.2 SumofFactorials12.2.3 Biorhythms12.2.4 IDCodes12.2.5 GameofConnections12.2.6 NecklaceofBeads12.2.7 BacktoMotherShip12.2.8 RandomWalk12.2.9 CalendarGame12.3 训练集第13章 计算几何13.1 知识概述13.2 例题解析13.2.1 TheDoors13.2.2 ThatNiceEulerCircuit13.2.3 ARoundPeginaGroundHole13.2.4 Splitconvexpolygon13.2.5 Area13.2.6 ArtGallery13.2.7 SurroundtheTrees13.2.8 VivaConfetti13.2.9 CenterofSymmetry13.3 训练集附录A ACM／ICPC简介附录B OnlineJudge简介附录C 程序编码风格附录D 例题来源参考文献

章节摘录

　　12.计算几何　　指主要使用计算几何相关知识设计算法求解的题目。包括位置关系相关问题（如点与多边形的位置关系、线段与线段的位置关系和多边形与多边形的位置关系等）、周长与面积问题（如多边形并或交的周长与面积等）、凸包问题（如平面点集的凸包）、多边形的可见核问题和三角剖分问题等。　　13.特殊问题　　指需要创造新算法进行求解的题目。这类题目一般难度较大。　　1.3.3 解题的几点原则　　制定一些合理原则，并遵照这些原则求解问题，可以大大提高解题效率。下面，介绍几点基本原则。　　1.评估题目难易程度　　给定题目，应养成首先对题目难易程度进行评估的习惯，切忌看到一个感觉顺手的题目就马上开始编程求解。这个习惯在竞赛中尤为重要，因为竞赛的总时间是一定的，根据竞赛排名规则，最好的策略就是先做最简单的题目，并用最短的时间、最少的提交次数正确求解。这样，才能有利于良好心态的保持，才能争取更多有效时间求解其余题目。　　2.警惕思维定势　　作一些思维方面的准备是非常有必要的，但务必尽量保持清醒灵活的头脑，切忌思维定势。对于一个题目，要严格按照步骤分析设计算法，使其在给定时空限制下求解问题，并考虑是否有更简捷的算法。切忌想到一个貌似可行的方法就急着编程求解，这在大多数情况下将导致错误的结果。