图灵程序设计丛书:挑战程序设计竞赛(第2版) - Softcover

Softcover

ISBN 10: 7115320101 ISBN 13: 9787115320100

Synopsis

《挑战程序设计竞赛（第2版）》对程序设计竞赛中的基础算法和经典问题进行了汇总，分为准备篇、初级篇、中级篇与高级篇4章。作者结合自己丰富的参赛经验，对严格筛选的110多道各类试题进行了由浅入深、由易及难的细致讲解，并介绍了许多实用技巧。每章后附有习题，供读者练习，巩固所学。世界程序设计高手的经验总结【ACM-ICPC全球总冠军】巫泽俊主译日本ACM-ICPC参赛者人手一册2.5.5最小生成树给定一个无向图，如果它的某个子图中任意两个顶点都互相连通并且是一棵树，那么这棵树就叫做生成树（SpanningTree）。如果边上有权值，那么使得边权和最小的生成树叫做最小生成树（MST，MinimumSpanningTree）。例如我们假设有这样一个图：把顶点看作村庄，边看作计划要修建的道路。为了在所有的村庄间通行，恰好修建村庄数目-1条道路时的情形就对应了一棵生成树。修建道路需要投入建设费，那么求解使得道路建设费用最小的生成树就是最小生成树问题。常见的求解最小生成树的算法有Kruskal算法和Prim算法。很显然，生成树是否存在和图是否连通是等价的，因此我们假定图是连通的。1.最小生成树问题1（PrIm算法）首先我们介绍Prim算法。Prim算法和Dijkstra算法十分相似，都是从某个顶点出发，不断添加边的算法。首先，我们假设有一棵只包含一个顶点v的树T。然后贪心地选取T和其他顶点之间相连的最小权值的边，并把它加到T中。不断进行这个操作，就可以得到一棵生成树了。接下来我们来证明通过这个方法得到的生成树就是最小生成树。第1章蓄势待发--准备篇1.1何谓程序设计竞赛1.2最负盛名的程序设计竞赛1.2.1世界规模的大赛--GoogleCodeJam（GCJ）1.2.2向高排名看齐！--TopCoder1.2.3历史最悠久的竞赛--ACM-ICPC1.2.4面向中学生的信息学奥林匹克竞赛--JOI-IOI1.2.5通过网络自动评测--OnlineJudge（OJ）1.3本书的使用方法1.3.1本书所涉及的内容1.3.2所用的编程语言1.3.3题目描述的处理1.3.4程序结构1.3.5练习题1.3.6读透本书后更上一层楼的练习方法1.4如何提交解答1.4.1POJ的提交方法1.4.2GCJ的提交方法1.5以高效的算法为目标1.5.1什么是复杂度1.5.2关于运行时间1.6轻松热身1.6.1先从简单题开始1.6.2POJ的题目Ants1.6.3难度增加的抽签问题第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.2一往直前！贪心法2.2.1硬币问题2.2.2区间问题2.2.3字典序最小问题2.2.4其他例题2.3记录结果再利用的"动态规划"2.3.1记忆化搜索与动态规划2.3.2进一步探讨递推关系2.3.3有关计数问题的DP2.4加工并存储数据的数据结构2.4.1树和二叉树2.4.2优先队列和堆2.4.3二叉搜索树2.4.4并查集2.5它们其实都是"图"2.5.1图是什么2.5.2图的表示2.5.3图的搜索2.5

Edition details

• Language: Chinese
• ISBN 10: 7115320101
• ISBN 13: 9787115320100
• Binding: Paperback