程序设计中常用的解题策略

出版时间：2009-10  出版社：人民邮电出版社  作者：王建德,吴永辉  页数：363  字数：578000  
Tag标签：无  

内容概要

本书按照题型和知识点分类，以数据关系上的构造策略、数据统计上的二分策略、动态规划上的优化策略、计算几何问题上的应对策略这4个方面为基本构件，介绍了几十种解题策略和重要算法；同时，深入浅出地分析和证明了对每种解题策略和算法的原理，采用“一题多解”、“多向求解”的方式解析了70余道例题，并结合应用例证阐释了编程中常用的一些思维方式和解题策略，以拓宽读者的思路，教会读者应该怎样应用算法知识解题，应该怎样选择有效的算法。    本书既可以作为大专院校计算机专业算法类课程的教材，亦可以作为大学和中学的程序设计竞赛活动的培训教程，还可以作为计算机软件研发的参考资料。

作者简介

王建德，国务院特殊津贴专家、上海师范大学特聘教授、控江中学特级教师。他辅导学生在国际奥林匹克信息学竞赛（IOI）中获8金、2银、2铜，先后出版了《新编实用算法分析与程序设计》、《程序设计中常用的计算思维方式》等23本广受好评的图书，这些图书长期以来是国内各类程序

书籍目录

第1章　利用树型结构解题的策略  1.1　解决树的最大/最小划分问题的一般方法    1.1.1　解法1——二分查找最大的下界    1.1.2　解法2——向下移动“割”    1.1.3　在两种解法的基础上进一步优化  1.2　利用最小生成树及其扩展形式解题    1.2.1  利用最小生成树解题    1.2.2　最小k度限制生成树的思想和应用    1.2.3  次小生成树的思想和应用  1.3　利用线段树解决区间计算问题    1.3.1　线段树的基本概念    1.3.2　线段树的基本操作    1.3.3　应用线段树解题  1.4　利用伸展树优化动态集合的操作    1.4.1　伸展树的基本操作    1.4.2　伸展树的效率分析    1.4.3　应用伸展树解题  1.5　利用左偏树实现优先队列的合并    1.5.1　左偏树的定义和性质    1.5.2　左偏树的操作    1.5.3　应用左偏树解题  1.6　利用“跳跃表”替代树结构    1.6.1　跳跃表的概况    1.6.2　跳跃表的基本操作    1.6.3　跳跃表的效率分析    1.6.4　应用跳跃表解题  小结第2章　利用图形（网状）结构解题的策略  2.1　利用网络流算法解题    2.1.1  网络与流的概念    2.1.2　在增广路径的基础上计算最大流    2.1.3　利用最大流最小割切定理解题    2.1.4　求容量有上下界的最大流问题    2.1.5　计算带费用的流量问题  2.2　利用图的匹配算法解题    2.2.1  匹配的基本概念    2.2.2　计算二分图的匹配    2.2.3  利用一一对应的匹配性质转化问题  2.3　利用“分层图思想”解题    2.3.1　利用“分层图思想”化未知为已知    2.3.2　利用分层图思想优化算法  2.4　利用平面图性质解题    2.4.1  平面图的基本概念    2.4.2　平面图的应用实例    2.4.3　偏序集的基本概念    2.4.4　偏序集的应用实例  2.5　在充分挖掘和利用图论模型性质的基础上优化算法  小结第3章　数据关系上的构造策略  3.1　选择数据的逻辑结构的基本原则    3.1.1　充分利用“可直接使用”的信息    3.1.2　不记录“无用”信息  3.2　选择数据的存储结构的基本方法    3.2.1　合理采用顺序存储结构    3.2.2　必要时采用链式存储结构  3.3　科学组合多种数据结构    3.3.1　数据结构的“并联”    3.3.2　数据结构的“嵌套”　小结第4章　数据统计上的二分策略　……第5章　动态规划上的优化策略第6章　计算几何上的应对策略

章节摘录

插图：第2章　利用图形（网状）结构解题的策略图是对实际问题的一种抽象方式，即用顶点、边和权来描述事物和事物之间的关系。实际上，第1章所述的树是图的一种特例，即一种限定前件数为1且不允许有同路的连通图。本章中，我们取消了这种限制，在更宽泛的意义上讨论事物间的联系。建立图论模型，就是要从问题的原型中抽取对我们有用的信息和要素，使要素间的内在联系体现在点、边、权的关系上，使纷杂的信息变得有序、直观、清晰。本章将介绍。些利用网络流算法、匹配算法、分层图思想、平面图性质和平面图的偏序集模型解题的基本策略，并在此基础上着重讨论选择图论模型的重要意义和优化算法的方法。2.1 利用网络流算法解题网络流算法是一种高效实用的算法，相对于其他图论算法来说，模型更加复杂，编程复杂度也更高。但是网络流算法综合了图论中的其他一些算法（如宽度优先搜索、最短路径等），能够有效地解决一些看似NP的问题，因而适用范围很广。

编辑推荐

《程序设计中常用的解题策略》对近年来程序设计教育和竞赛培训活动涌现出的许多有价值的解题方法，进行了理性、概括性和综合性的总结。从思维方式和行为特征的角度阐释了求解各种类型试题的应对策略。全书不仅充分阐释了各种解题策略的理论依据，而且还提供了大量经典的应用范例。帮助读者学会选择适宜的解题方法，掌握正确的解题策略。《程序设计中常用的解题策略》既是大学计算机专业算法分析课程的优秀参考书，又是大中学程序设计竞赛不可错过的培训教材。《程序设计中常用的解题策略》特色：·《程序设计中常用的解题策略》以数据关系上的构造策略、数据统计上的二分策略、动态规划上的优化策略和计算几何问题上的应对策略为4个基本构件，介绍了40余种解题策略和重要算法。·各章节之间有紧密的内在联系，但彼此又相对独立。·对每种解题策略和算法原理进行了必要的分析和证明。定理证明大多采用初等数学的分析方法.公式推导尽可能做到浅显和详细，对其中一些复杂的解题策略和算法附加了清晰的图示，并给出了计算时间的详细分析。·40余种解题策略都有具体的应用例证。70余道例题采用“一题多解”、“多向求解”的方式解析。并给出了由贴近自然语言、结构清晰、移植性强的类程序设计语言表述的程序题解。计算机程序设计竞赛权威指导书

用户评论 (总计5条)

•   学竞赛的
  感觉帮助很大
•   这本书每个专题讲的相当透彻，视野独到，是NOI、IOI、ACM选手不错的选择
•   有点深。
•   但是好像又不是用C写的吧？？？？？？
•   挺好的。适合在算法上入了门，希望进一步提高的选手……