挑战程序设计竞赛第二版豆瓣在线阅读-挑战程序设计竞赛第二版PDF电子书下载带目录

挑战程序设计竞赛第二版豆瓣在线阅读-挑战程序设计竞赛第二版PDF电子书下载带目录

编辑点评:

《挑战程序设计竞赛(第2版)》对程序设计竞赛中的基础算法和经典问题进行了汇总,分为准备篇、初级篇、中级篇与高级篇4章。作者结合自己丰富的参赛经验,对严格筛选的110 多道各类试题进行了由浅入深、由易及难的细致讲解,并介绍了许多实用技巧

挑战程序设计竞赛第二版PDF电子书下载

前言

如今,形形色色的程序设计竞赛层出不穷,听说过Google Code Jam、TopCoder、ACM-ICPC的读者恐怕不在少数。本书要介绍的正是这类以在规定时间内、又快又准地解决尽可能多的题目为目标的程序设计竞赛。 

程序设计竞赛内涵丰富,即便是经验老道的程序员,要想在比赛中取得好成绩也绝非易事。要在程序设计竞赛中取胜,不仅需要运用灵活的想象和丰富的知识得出正确的算法,还需要一气呵成地实现并调试通过。 

另一方面,程序设计竞赛对新手而言亦非遥不可及。为了让更多的参赛选手体会到比赛的乐趣,大多数比赛都会准备若干面向初学者的题目。另外,即便未能在比赛中取得好成绩,通过比赛,也能够使自己的能力得到有效的锻炼。最重要的是,大家能够享受到激烈的比赛带来的乐趣。 

本书的作者们参加过众多程序设计竞赛,在平时的练习和学习中,也获得了各种各样的知识与技巧,本书将这些知识技巧总结成册,主要介绍算法及其在相关问题中的应用。本书依照由易及难的顺序对问题进行讲解,章节的编排也参考了主题的难易程度及其相互的联系,内容较多的主题则按难易程度划分为多个子主题分别介绍。各个主题由算法介绍和例题讲解穿插而成。 

只要是具有编程基础知识的读者,均适合阅读本书。书中的源代码均用C++实现,不过只用到了其基本功能,所以即便读者不熟悉C++也不影响阅读。 

世界规模的大赛-Google Code Jam(GCJ)

它是Google公司几乎每年都会举办的世界规模的程序设计竞赛,参赛者要在2-3小时内解决大约4道题。一旦从在线(Online)进行的几轮预选中胜出,就能够参加现场(Onsite)总决赛。该赛事的特点是,每道题都备有Small和Large两组输入数据。即便是难度系数较大的问题,只要输入规模足够小,依然可以简单地求解,这一形式深受广大参赛者的喜欢。另外,GCJ并不在服务器上自动执行程序,而是要求将源代码和本地执行的结果一同提交。

作者简介

★秋叶拓哉 

Google Code Jam 2010 第9名 

ACM-ICPC World Finals 2012 第11名 

TopCoder Open 2012 Algorithm 第4名 

昵称iwi 

★岩田阳一 

Google Code Jam 2009 第3名 

TopCoder Open 2010 Marathon 冠军 

IPSC 2010 个人组 冠军 

昵称wata 

★北川宜稔 

ACM-ICPC World Finals 2010第16名 

昵称kita_masa 

译者简介: 

★巫泽俊 

ACM-ICPC World Finals 2009 第6名 

ACM-ICPC World Finals 2011 冠军 

Google Code Jam 2012 第7名 

昵称watashi和rejudge 

★庄俊元 

ACM-ICPC Asia Phuket Regional 2011 冠军 

2012年跻身ACM-ICPC World Finals以及百度Astar总决赛 

昵称navi和navimoe 

★李津羽 

浙江大学2011级计算机系博士生 

在浙大CAD&CG实验室从事科研工作

精彩书摘

2.5.5 最小生成树 

给定一个无向图,如果它的某个子图中任意两个顶点都互相连通并且是一棵树,那么这棵树就叫做生成树(Spanning Tree)。如果边上有权值,那么使得边权和最小的生成树叫做最小生成树(MST,Minimum Spanning Tree)。 

例如我们假设有这样一个图:把顶点看作村庄,边看作计划要修建的道路。为了在所有的村庄间通行,恰好修建村庄数目—1条道路时的情形就对应了一棵生成树。修建道路需要投入建设费,那么求解使得道路建设费用最小的生成树就是最小生成树问题。 

常见的求解最小生成树的算法有Kruskal算法和Prim算法。很显然,生成树是否存在和图是否连通是等价的,因此我们假定图是连通的。 

1.最小生成树问题1(PrIm算法) 

首先我们介绍Prim算法。Prim算法和Dijkstra算法十分相似,都是从某个顶点出发,不断添加边的算法。 

首先,我们假设有一棵只包含一个顶点v的树T。然后贪心地选取T和其他顶点之间相连的最小权值的边,并把它加到T中。不断进行这个操作,就可以得到一棵生成树了。接下来我们来证明通过这个方法得到的生成树就是最小生成树。

挑战程序设计竞赛第二版PDF电子书下载截图

挑战程序设计竞赛第二版豆瓣在线阅读-挑战程序设计竞赛第二版PDF电子书下载带目录插图(1)挑战程序设计竞赛第二版豆瓣在线阅读-挑战程序设计竞赛第二版PDF电子书下载带目录插图(2)挑战程序设计竞赛第二版豆瓣在线阅读-挑战程序设计竞赛第二版PDF电子书下载带目录插图(3)挑战程序设计竞赛第二版豆瓣在线阅读-挑战程序设计竞赛第二版PDF电子书下载带目录插图(4)挑战程序设计竞赛第二版豆瓣在线阅读-挑战程序设计竞赛第二版PDF电子书下载带目录插图(5)

评分及评论

无用户评分

来评个分数吧

  • 5 分
    0
  • 4 分
    0
  • 3 分
    0
  • 2 分
    0
  • 1 分
    0

Comments