程式设计中常用的解题策略 _生活百科

文章插图
程式设计中常用的解题策略【程式设计中常用的解题策略】《程式设计中常用的解题策略》是2009年10月人民邮电出版社出版的图书，作者是王建德。本书既可以作为大专院校计算机专业算法类课程的教材，亦可以作为大学和中学的程式设计竞赛活动的培训教程，还可以作为计算机软体研发的参考资料。
基本介绍书名：程式设计中常用的解题策略
作者：王建德
ISBN：9787115202406
定价：49.00元
出版社：人民邮电出版社
出版时间：2009年10月
开本：16开
内容简介《程式设计中常用的解题策略》按照题型和知识点分类，以数据关係上的构造策略、数据统计上的二分策略、动态规划上的最佳化策略、计算几何问题上的应对策略这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章数据统计上的二分策略4.1 利用线段树统计数据4.1.1 解决一维数据序列的统计问题4.1.2 解决二维数据区的统计问题4.2 一种解决动态统计的静态方法4.2.1 讨论一维序列的求和问题4.2.2 二维序列的求和问题4.3 在静态二叉排序树上统计数据4.3.1 建立静态二叉排序树4.3.2 在静态二叉排序树上进行统计4.3.3 静态二叉排序树的套用4.4 在虚二叉树上统计数据小结第5章动态规划上的最佳化策略5.1 减少状态总数的基本策略5.1.1 改进状态表示5.1.2 选择适当的规划方向5.2 减少每个状态决策数的基本策略5.2.1 利用最优决策的单调性5.2.2 最佳化决策量5.2.3 合理组织状态5.2.4 细化状态转移5.3 减少状态转移时间的基本策略5.3.1 减少决策时间5.3.2 减少计算递推式的时间小结第6章计算几何上的应对策略6.1 应对纯粹计算题的策略探讨6.1.1 利用多维线段树解决矩形或长方体几何的计算问题6.1.2 利用矩形切割思想进行几何计算和数据统计6.1.3 利用极大化思想解决最大子矩形问题6.1.4 利用半平面交的算法计算凸多边形6.2 应对存在性问题的策略探讨6.2.1 直接通过几何计算求解6.2.2 转换几何模型求解6.3 应对最佳值问题的策略探讨6.3.1 採用高效的几何模型6.3.2 採用极限法6.3.3 採用逼近最佳解的近似算法小结……