算法问题实战策略[试读]

1.1　引言 当今世界，“程序员”这么一个职业名称可分为很多类型，比如SI程序员、数据库程序员、网页设计程序员、游戏设计程序员，等等。这些程序员在不同的开发环境下，利用不同的程序语言和工具编写程序，解决各自面临的问题。那么，要成为跨领域的优秀程序员需要具备什么样的条件呢？ 程序设计就是解决问题 程序设计需要丰富的知识。可能程序员只是看起来在漫无目的地敲打键盘，其实他们脑海中对程序设计语言的特性、程序运行的硬件平台和操作系统、对所使用的库的注意事项等进行着综合性的思考。在满足程序运行可占用内存空间的要求和限定的运算时间内，尽可能编写简洁而可重复利用的代码。 了解这些限制条件和要求后找到... 查看全部[ 1.1　引言 ]

参加程序设计竞赛是培养解决问题能力的最佳途径。在目前各式各样的程序设计竞赛当中，本书选取设计要求较少、有运算时间限制、比拼快速设计能力的竞赛。此处的设计要求不同于实际开发中的要求，而是以“读入某个值，然后计算出某个值”的形式给出。 下面针对未接触过程序设计竞赛的读者举个简单的示例。 题目：摇滚音乐节（难度：低，题目ID：FESTIVAL） 要租用一个大的演出场地举办摇滚音乐节。这次音乐节将持续数日，每天有一支乐队举行演唱会。还未确定共邀请几个乐队，但已经与L个明星乐队交涉完毕，所以音乐节至少要举办L日。 要使用的演出场地每日租金各不相同，因此要妥当安排演出日程来节约成本。假设已经知道... 查看全部[ 1.2　程序设计竞赛 ]

本书结构 本书共由7个部分组成。为学好后半部分的内容，第一部分和第二部分主要介绍了一些背景知识，其中包括程序设计竞赛中解决问题的方法、编写代码和调试中的注意事项、算法的正确性证明以及效率分析等。不要以为此部分是基础性的内容而可以忽视，如果不能很好地理解这些基础知识，那么之后更深的内容就只能学到皮毛。本书的其他部分都将围绕着算法设计技巧和数据结构等程序设计竞赛解决问题的技术进行介绍。在这些部分将讲解各个算法诞生的背景以及设计过程，也包括能够直接解答或变换形式解答的练习题。 本书中，练习题和解题部分所占比重较大。请各位阅读练习题时不要一带而过，要尽力去解答这些习题。只有这样才能与书中正确解法相... 查看全部[ 1.3　阅读本书的方法 ]

国内外目前有很多程序设计竞赛。过去的竞赛参赛者大多为学生，但随着软件公司开始注重应聘者解决算法问题的能力 ，现在也出现了面向公众的程序设计竞赛。下面这些竞赛值得各位一试。 全国青少年信息学奥林匹克竞赛 关于NOI（National Olympiad in Informatics）：http://www.noi.cn/ ACM-ICPC（ACM大学生程序设计竞赛） ACM-ICPC是全球最大的计算机协会ACM（Association for Computing Machinery）每年专门面向大学生举办的程序设计竞赛。ACM-ICPC不同于其他的程序设计竞赛，3名参赛者组成一组，用一台计... 查看全部[ 1.4　值得参加的程序设计竞赛 ]

下面为准备参加程序设计竞赛的本书读者们提供一些建议。 尽可能多解题 参加程序设计竞赛需要学习的内容非常多。以本书为例，全书有32章之多，但其内容还不能完全涵盖竞赛的所有主题。海量的学习内容很容易让参赛者陷入“尽可能多读教科书和其他资料来补充基础知识”的误区。其实，多了解一个算法，还不如提高利用已掌握的知识来解题的能力。因为，程序设计竞赛最终也只是通过每个参赛者编写出来的代码进行评判，而不管参赛者掌握多少知识，写不出解题的代码就等于没有解题的能力。经验和能力只能通过解答实际题目来慢慢培养，所以初学者最好先按照表1-1学习最重要的内容后，尽可能多解题以积累自己的经验并提高解题能力。 使用... 查看全部[ 1.5　对赛前准备工作的一些建议 ]

功能更强、更有用的参考资料是互联网和搜索引擎。与“教科书万能”的时代不同，现在有了维基百科（http://wikipedia.org）等网站，没有课本也能好好学习。不管是本书内容还是其他主题，都能轻而易举地搜索到相关资料。 “知道自己不知道”的时候，搜索和互联网还是非常有用的。但迷茫于不知道该学什么，或者不确定该以怎样的顺序学习时，还是用教科书比较稳妥。下面列出了供程序设计竞赛备考人员参考的翻译书籍。  《算法导论》（Introduction to Algorithms）：本书选用四位作者名字的首字母命名，因而又被称为CLRS，是很多国际著名大学的算法课教材，可称得上是算法与数据结构的权... 查看全部[ 1.6　续读 ]

2.1　引言 第1章中提到过，程序设计竞赛是培养解决问题能力的理想环境。但并不能通过死记硬背算法去拼命解题而培养出来。解决问题的能力不同于程序设计和算法，它没有实体性的定义可循，而是一种抽象概念。因此，只靠单纯的反复练习很难培养。大多数读者小学开始就已经学解算术题，但那只是针对给出题目的解题方法。因此，实际上很多人最终只是停留在机械式解题过程中的体会和盲目的尝试中。 要成为解决问题的高手，需要更高层次的磨练。这种磨练的目标是练就解题的技术，而不是解题本身。要认清自己解决问题的方式，了解其不足，领会哪些部分需要改善。这个过程与学习高尔夫的击球类似。任何人都会挥杆击球，尝试若干次偶尔也会进洞。... 查看全部[ 2.1　引言 ]

首先介绍现今最流行的一个解决问题的算法，它因著名量子物理学家理查德•费曼（Richard Feynman）最早使用而得名。这个算法不仅功能强大，而且包含了解决问题所需的全部因素。费曼利用此算法解决了量子力学方面的诸多难题。 下面是费曼算法的详解。 1. 把问题写到黑板上； 2. 冥思苦想； 3. 把答案写到黑板上。 是的，费曼算法其实是一个（半个）玩笑 ，但该算法也有值得各位学习的部分。首先，算法把解决问题的过程分成了几个阶段。分阶段的想法看起来算不上什么高招，但正是通过分阶段能够判断何处有不足、何处有待改善。另外一个非常重要的内容是，该算法中“把问题写到黑板上”的阶段。要把... 查看全部[ 2.2　解决问题的过程 ]

遇到简单的问题时，直接利用已知技术便可轻松解决问题。若是遇到难题，需试用各种手段去寻找答案。本节先介绍几个最常用的策略，之后再介绍应用这些策略的示例。本书习题中大量使用这些策略，希望各位阅读解题过程时，留意着手解题的方法。 直观而系统的着手方式 解决问题的策略中，首先强调的是对问题和答案结构的直观感受。通过直觉能够估计出解决当前问题的算法应具备什么样的形态。了解了答案的整体轮廓，就等于成功了一半。 当然，如果所有问题都能够一看就知道该如何解答，也就没必要阅读本书了。直觉可通过时间慢慢培养，通过解决看起来毫无头绪的问题，一点一点积累经验。 那么，该如何解决没有头绪的问题呢？或许可以坐在... 查看全部[ 2.3　解决问题的策略 ]

作为解决问题领域的经典书籍，《如何求解问题：现代启发式方法》（How to Solve It: Modern Heuristics）列出了许多解决问题的策略，也介绍了许多初次遇到的问题的解法。... 查看全部[ 2.4　续读 ]

15.1　引言 与点、线、多边形、圆形等各种几何图形相关的算法称为计算几何（computational geometry）算法。计算几何已成为3D图形、CAD、机器人等多种领域的基础，在计算机学科中占据了重要地位。程序设计竞赛中也常常出现有关计算几何的问题。 计算几何包含了很多内容，涉及面非常广。不过，程序设计竞赛中出现的题目大多集中于基础性的问题。解决这种问题时需要的并不是宏大的算法或设计范式，而是把本科线性代数或高中几何学的内容转换成代码。因此，本章重点在于如何将基础数学理论转换成既简洁又无异常的代码形式。 计算几何是涉及二维平面和三维立体图形的一门学问，而程序设计竞赛的问题主要是二... 查看全部[ 15.1　引言 ]

首先定义编写计算几何代码时必须用到的概念，并观察其实现方法。 向量的实现 二维平面上的两个不同点的相对位置该如何表示呢？对于这个问题，应当先求出两点之间的距离，然后求出从一个点到另外一个点的方向。求出方向和距离后，就能准确表示出两点之间的相对位置。这种既有大小又有方向的距离就是向量（vector），向量是数学、物理学、工学等领域中广泛应用的概念，也是计算几何的最基础的工具。 向量最直观的表示方法是带有箭头的线段。向量由方向和长度两个因素组成，所以箭头的起点并不重要。即使改变了起点，向量也不会发生改变。因此，可以把向量的起点定义为坐标空间的原点，那么就可以把向量表示成箭头的终点位置(x,... 查看全部[ 15.2　计算几何的工具 ]

直线与直线相交 确认两条直线是否相交并求出交点的问题在几何题中很常见。求两条直线交点的数学问题并不难，不过，要编写出没有异常的代码就比较困难了。解出x坐标后代入方程求出y坐标的程序，会无法应对水平线和垂直线等特殊的情况。因此，无论用何种方法编写程序，都要考虑到特殊情况。 表示相交直线的最好方法是，将直线表示成一个点和方向向量，即a+p•b的形式。那么，解方程a+p•b=c+q•d就能求出a+p•b和c+q•d的交点。将方程按照各坐标的形式表示出来，就能得到如下两个联立方程式。 求解p就能得到如下等式。 此时，分母为0的唯一情况是，两个向量a和b相互平行，此时当然不会存在交点。简... 查看全部[ 15.3　相交、距离、面积 ]

东赫在玩一种新出的弹球游戏，这种弹球游戏会在一个很大的游戏台中放置几个障碍物，然后让玩家抛进小球，撞击障碍物最多的人获胜。小球和障碍物都是正圆，小球撞击障碍物后的入射角和反射角相同。障碍物已固定到游戏台上，不可移动。下图表示东赫依序抛进的小球撞击各障碍物后，弹出游戏台的路线。 给出障碍物的大小和位置，以及小球的位置和方向时，编写程序计算小球撞击的障碍物的序号。小球的半径是1，且只做直线运动。 时间及内存使用限制 程序必须在1秒内完成运算，使用内存不得超过64MB。 输入 第一行输入测试用例的个数C（C≤50）。各测试用例的第一行输入5个整数x、y、dx、dy、N。x、y（0≤x、... 查看全部[ 15.4　练习题：弹球模拟（题目 ID：PINBALL，难度：高） ]

若是用方程式解决此问题，将会变得非常复杂，利用向量就简单得多了。 简化问题 首先介绍简化问题的方法。题目中，小球是半径为1的圆形。将小球简化成点，并把所有障碍物的半径加1，这样就能把相同的球作为点求解。虽然这种简化并不能让题目更简单，但是小球的运动轨迹可以变成一条直线，对解题也比较有利。 状态表现与模拟 接下来正式考虑如何模拟。此题需要模拟出二维平面上小球的运动轨迹。为了预测出小球的运动轨迹，需要知道小球的当前位置和方向。可以用表示当前位置的位置向量和表示方向的单位向量表示这两种信息。那么，就可以先找出下一个将要撞击的障碍物并输出其序号，然后更改小球的位置和方向信息。这种操作要重复至无... 查看全部[ 15.5　解题：弹球模拟 ]

以计算几何方式表现现实世界时，多边形（polygon）是必不可少的因素。因此，有关多边形的问题也经常出现在程序设计竞赛中。 多边形的种类 首先简单介绍本节将要用到的名词。  凸多边形（convex polygon）指的是每个内角都在180度以内的多边形。例如，正方形就是凸多边形。凸多边形具有几个非常有用的性质，所以会经常应用于解题过程。例如，两个凸多边形的交集也是凸多边形，连接凸多边形内部任意两点的线段绝不会与凸多边形的边相交。  反之，内角超过180度的多边形就是凹多边形（concave polygon）。  简单多边形（simple polygon）是边不相交的多边形。 ... 查看全部[ 15.6　多边形 ]

人们历经磨难，终于找到了著名海盗Guybrush Threepwood藏匿宝箱的金银岛。虽然已经知道Guybrush肯定把宝箱藏在了此岛，但具体的藏匿位置仍然不得而知。快要翻遍整个小岛时，发现了地图上未能标出的写有宝箱埋藏位置的纸条。纸条对宝箱的位置进行了详细说明，不过，因为写得过于繁琐，而且有多处字迹已经无法辨认，无法获知准确信息。经过认真研究，人们最终还是把寻宝范围缩小了一些。 如图所示，小岛由具有N个顶点的多边形构成。藏宝位置的范围是，以两个点(x1, y1)和（x2, y2)为对角顶点、4条边与x轴和y轴相互平行的矩形内部。现在想调查该矩形内部的陆地部分，试编写程序计算此部分面积。... 查看全部[ 15.7　练习题：金银岛（题目 ID：TREASURE，难度：高） ]

多边形的交集 解决此问题的最直观的方法是，先求出两个简单多边形的交集，然后求交集面积。两个多边形都是凸多边形时，最容易求出多边形的交集，因为两个凸多边形的交集也是凸多边形。不过此题中，小岛的轮廓是任意简单多边形，所以此性质并不成立。所幸第二个多边形是矩形，所以是凸多边形，问题也就变得简单了。 图15-10　利用半平面的交集生成凸多边形 我们要利用的凸多边形重要特性之一是，可以通过多个半平面（half plane）的交集求出凸多边形。将凸多边形的各边按照逆时针方向遍历，并求出包含各边的直线左侧半平面。那么，这些半平面的交集就等于当前凸多边形。图15-10表示包含一个凸多边形4边的几条直... 查看全部[ 15.8　解题：金银岛 ]

一年一度的algospot程序设计竞赛日益临近，今年的竞赛非常火爆，报名人数超过了1万人。不过，参加评判的志愿者只有5人，所以不能让所有报名者全部参赛。因此，组织方决定，只让“真正的编程呆子（nerd）”参加竞赛。 根据宗万的新理论，某人的呆子指数可以用如下两种数值的线性结合定义。 F=A×鞋子尺码+B×每分钟打字速度 此指数越高，越接近呆子；反之，则不是呆子的概率越高。据此定义标准值T。如果报名者的呆子指数超过T，将允许参赛。 不过，这种理论真的可信吗？为了确认，我们向我们已经了解是否是呆子的人收集了一些信息。最终资料由鞋子尺码、每分钟的打字速度，以及此人是否是呆子等信息组成。那么... 查看全部[ 15.9　练习题：是呆子？不是呆子？（题目ID：NERDS，难度：中） ]

变换成几何问题 此题看似完全不是几何题，其实，巧妙变换即可。实行变换的第一个线索是，每人有两项调查资料，因此，把每人的鞋子尺码和每分钟的打字速度分别视为x、y坐标，就能把输入的数据表示成N个点。图15-13(a)是第一个示例的图形，图中的○表示呆子，×表示不是呆子的人。每个人的信息已表示成图表形式，接下来把区分呆子和不是呆子的人的公式也表示成图表形式。对于是呆子的人，如下公式将成立。 A•x+B•y≥T 图15-13　把“是呆子？不是呆子？”问题的输入值表示成二维平面上的点 将此公式表示成图表后，将会是半平面。也就是说，以一条直线为基准，一侧是呆子，另一侧不是呆子。因此，图中能够找... 查看全部[ 15.10　解题：是呆子？不是呆子？ ]

很多计算几何问题都可以利用本章介绍的相关代码组合解决，不过，只解决固定模式的问题并不是几何问题的全部内容。很多情况下需要组合这些代码，以编写出更复杂的算法。此时，几何算法的设计范式将有助于编写出更高效的算法。本节将介绍两种比较著名的范式，并通过示例讲解如何利用这些范式提高解题效率。 平面扫描 平面扫描（plane sweeping）或线扫描（line sweeping）范式是设计计算几何算法的最著名的范式之一。利用了平面扫描的算法会沿着水平或垂直方向“扫过”给定平面以解决问题。虽然看似很简单，但能够利用这种方法解决的问题特别多。 矩形合集的面积 给出几个各边均与x轴和y轴相互平行的矩... 查看全部[ 15.11　计算几何算法设计范式 ]

计算几何在程序设计竞赛中比较臭名昭著的原因是，其本质上存在较多异常情况。 退化图形 设计几何算法时的常见失误是，只考虑图像的“一般位置”（general position）。一般位置指的是图形相对位置的一般情况。与其对应的异常情况称为退化（degenerate）图形，如下所示。  同一直线上的3个以上的点  相互平行或重叠的直线/线段  面积为0的多边形  多边形的边相互重叠的情况 本章介绍的代码中也考虑过这种特殊情况。确认线段相交问题中，考虑过线段平行时是重叠还是共享1个点。求凸包时，考虑过相对于当前点，最左侧的向量存在两个以上的情况（3个点处在同一直线上的情况）。 ... 查看全部[ 15.12　常见失误与注意事项 ]

 拥有大量计算几何习题及解法的网站（http://softsurfer.com/）提供了本章算法的详细说明和C++代码。  针对平面扫描问题的TopCoder教程（http://links.algospot.com/linesweep）介绍了能够用平面扫描方法解决的题目及简单解法。  介绍旋转卡尺设计范式的网站（http://links.algospot.com/rotcal）提供了能够利用旋转卡尺法解决的大量习题及简单说明。... 查看全部[ 15.13　续读 ]