下载费用：10 元 &
第7章算法程序与计算系统之灵魂练习题答案解析 第 7 章 算法:程序与计算系统之灵魂1、算法就是一个有穷规则的集合，其中之规则规定了解决某一特定类型问题的一个运算序列。回答下列问题。(1)关于算法的特性，下列说法不正确的是_____。(A)算法必须有明确的结束条件，即算法应该能够结束，此即算法的有穷性；(B)算法的步骤必须要确切地定义，不能有歧义性，此即算法的确定性； (C)算法可以有零个或多个输入，也可以有零个或多个输出，此即算法的输入输出性；(D)算法中有待执行的运算和操作必须是相当基本的，可以由机器自动完成，进一步，算法应能在有限时间内完成，此即算法的能行性；(E)上述说法有不正确的；答案：C解释：本题考查对算法基本性质的理解 （C）算法的输出性：算法有一个或多个的输出/ 结果，即与输入有某个特定关系的量。因此（C ）选项错误。其余选项， （A） （B） （D）分别是对算法的有穷性，确定性和能行性的正确描述。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。(2)关于算法的命题，下列说法不正确的是_____。(A)算法规定了任务执行 /问题求解的一系列、有限的步骤。(B)算法所规定的计算/处理步骤是有限的，但算法实际执行的计算/处理步骤可以是无限的。(C)算法可以没有输入，但必须有输出。(D)算法的每一个步骤必须确切地定义，且其运算和操作必须相当基本，可以由机器自动完成。答案：B解释：本题考查对算法基本性质的理解 （B）违反了算法的有穷性：一个算法在执行有穷步规则之后必须结束。因此（B ）选项错误。其余选项， （A） （C） （D）分别是对算法的有穷性，输入输出性和确定性的正确描述。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。(3)关于算法与程序、计算机语言之间的关系，下列说法不正确的是_____。(A)算法是解决问题的步骤，某个问题可能有多个求解算法；(B)算法不能直接由计算机执行，必须将其转换为程序才能够由计算机执行；(C)算法只能由高级（计算机）语言实现，不能通过机器语言实现；(D)求解问题的多个算法不一定获得相同的解。答案：C解释：本题考查对算法基本性质的理解 （C）算法是解决问题的步骤，执行的语言是步骤书写的规范、语法规则、标准的集合是人和计算机都能理解的语言，不仅是高级语言。因此（C）选项错误。其余选项， （A）正确，解决问题的算法可以有多个。 （B）选项，程序是算法的实现方式，正确。 （D）选项，算法有优劣，对于同一个问题，获得的解可能不同。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。(4)算法是计算系统的灵魂，为什么？不正确的是_____。(A)计算系统是执行程序的系统，而程序是用计算机语言表达的算法；(B)一个问题的求解可以通过构造算法来解决， “是否会编程序”本质上章是“能否想出求解该问题的算法” ； (C)一个算法不仅可以解决一个具体问题，它可以在变换输入输出的情况下，求解一个问题系列；(D)问题求解都可以归结到算法的构造与设计，系统和算法的关系是：算法是龙，而系统是睛，画龙要点睛。(E)上述说法有不正确的；答案：D解释：本题考查算法、程序与系统之间的关系（D）选项，算法是计算系统的灵魂，因此系统和算法的关系是：系统是龙，算法是睛，好的算法能起到画龙点睛的效果。 （A ） （B） （C）选项描述正确。具体内容参考第七章视频之“算法与算法类问题的求解”以及第七章课件。2、哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径” 。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地， “边”为连接两块陆地的桥梁。这个抽象被称为“图” ，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答下列问题。//本题考查问题及其数学建模的作用(a) (b)(1)哥尼斯堡七桥问题的路径能够找到吗？ _____。(A)一定能够找到； (B)一定不能找到； (C)不确定能不能找到。答案：B解释：本题考查问题及其数学建模的作用选择（B） ，根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2（该题中应为0 个） 。该问题中将四个岛抽象成 4 个点，每条桥抽象成边，可知图中奇点个数是 4 个，因此不可能找到。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想” ，第七章课件或查阅欧拉回路相关资料。(2)对河流隔开的 m 块陆地上建造的 n 座桥梁，能否找到走遍这 n 座桥且只许走过每座桥一次最后又回到原出发点的路径呢？ _____。 (A)一定能够找到； (B)一定不能找到； (C)不确定能不能找到。答案：C解释：本题考查问题及其数学建模的作用选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2（该题中因为起点和终点是一个，所以奇点个数应为 0 个） 。该问题中将 m 个岛抽象成 m 个点，每条桥抽象成边，但图中奇点个数未知，因此不能做判断。具体内容参考第七章视频之“算法与算法类问题的求解，第七章课件或查阅欧拉回路相关资料。(3)对河流隔开的 m 块陆地上建造的 n 座桥梁，若要找到走遍这 n 座桥且只许走过每座桥一次最后又回到原出发点的路径，则需满足以下条件_____。(A)m 个顶点 n 条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点；(B)每个顶点的度应为偶数； (C)既需要满足(A)又需要满足(B) ；(D)上述条件还不够，还需满足更多条件。答案：C解释：本题考查问题及其数学建模的作用选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2（该题中因为起点和终点是一个，所以奇点个数应为 0 个） 。该问题中将 m 个岛抽象成 m 个点，每条桥抽象成边，因此应该选择 C。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想” ，第七章课件或查阅欧拉回路相关资料。(4)下面所示的图(c) ，能否找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？(c)(A)一定能够找到； (B)一定不能找到； (C)不确定能不能找到。答案：B解释：本题考查问题及其数学建模的作用选择（B）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2（该题中因为起点和终点是一个，所以奇点个数应为 0 个） 。图中奇点是 C 与 G，个数为 2，不符合要求，因此应该选择 B。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想” ，第七章课件或查阅欧拉回路相关资料。(5)参见图(c)，增加哪些边，使得能够找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？(A)BG 边； (B)AG 边； (C)CG 边； (D)AD 边； (E)DE 边。答案：C解释：本题考查问题及其数学建模的作用选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2（该题中因为起点和终点是一个，所以奇点个数应为 0 个） 。图中奇点是 C 与 G，个数为 2，不符合要求，因此在 CG 间增加一条边，将寄点数变成 0 可满足要求，因此应该选择 C。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想” ，第七章课件或查阅欧拉回路相关资料。(6-1)对河流隔开的 m 块陆地上建造的 n 座桥梁，若要找到走遍这 n 座桥且只许走过每座桥一次的路径，则需满足以下条件_____。(A)m 个顶点 n 条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点； (B)每个顶点的度应为偶数； (C)既需要满足(A)又需要满足(B) ；(D)不满足上述条件 (A)(B)(C)的图也能找出满足题目规定要求的路径；答案：D解释：本题考查问题及其数学建模的作用选择（D） ，此题未要求回到原地，即起点和终点可以不是一个，那么可以有 2 个奇数点作为起点和终点。根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2。不同时满足（A） （B） ，可以有 2 个顶点的度为奇数，也可以满足题目要求，因此应该选择 D。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想” ，第七章课件或查阅欧拉回路相关资料。(6-2)对河流隔开的 m 块陆地上建造的 n 座桥梁，若要找到走遍这 n 座桥且只许走过每座桥一次的路径，则需满足以下条件_____。(A)m 个顶点 n 条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点；(B)每个顶点的度应为偶数，或者，只有两个顶点的度为奇数而其他顶点的度均为偶数；(C)既需要满足(A)又需要满足(B) ；(D)不满足上述条件 (A)(B)(C)的图也能找出满足题目规定要求的路径；答案：C解释：本题考查问题及其数学建模的作用选择（C） ，此题未要求回到原地，即起点和终点可以不是一个，那么可以有 2 个奇数点作为起点和终点。根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2。因此应该选择 C。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想” ，第七章课件或查阅欧拉回路相关资料。(7)下面所示的图(d) 和图(e)，问能否找到走遍每一座桥，且每座桥仅走过一次的路径呢？ (d) (e)(A)图(d)和图(e)都一定不能找到；(B)图(d) 一定能够找到；图 (e)一定不能找到；(C)图(d) 一定不能找到；图 (e)一定能够找到；(D)图(d)和图(e)都一定能够找到；答案：C解释：本题考查问题及其数学建模的作用选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2。d 图有FGE 三个奇点，一定不能找到，而 e 图有 FG 两个奇点，一定能找到，因此应该选择 C。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想” ，第七章课件或查阅欧拉回路相关资料。(8)参见下图(f)，下列说法正确的是_____。(f)(A)对{A、B、 C、D、E、F 、 G}中的任意两个顶点 X 和 Y，都可以找到一条路径，从X 出发 走遍每一座桥，且每座桥仅走过一次，最后终止于 Y；(B)对两个顶点 A 和 B，可以找到一条路径，从 A 出发 走遍每一座桥，且每座桥仅走过一次，最后终止于 B；(C)对两个顶点 D 和 G，可以找到一条路径，从 D 出发 走遍每一座桥，且每座桥仅走过一次，最后终止于 G； (D)对{A、B、 C、D、E、F 、 G}中的任意两个顶点 X 和 Y，都找不到一条路径，从 X出发 走遍每一座桥，且每座桥仅走过一次，最后终止于 Y；答案：C解释：本题考查问题及其数学建模的作用选择（C）根据欧拉回路关系可知，要是一个图形可以一笔画，需要满足：1）图形必须是连通的；2）途中的“奇点” （相连的边的个数为奇数的点）个数是 0 或 2。该图奇点为 G 和 D，因此可以找到一条欧拉回路，并且只能以此两点作为起点和终点，因此应该选择 C。具体内容参考第七章视频之“数学建模与算法策略设计--算法思想” ，第七章课件或查阅欧拉回路相关资料。(9)哥尼斯堡七桥
文档加载中……请稍候！
下载文档到电脑，查找使用更方便
10 元 &&0人已下载
还剩页未读，继续阅读
<a href="UserManage/CopyrightAppeal.aspx?bid=" title="版权申诉" class="fLeft works-manage-item works-manage-report" target="_blank"
关&键&词： 7章 算法 程序 计算 系统 灵魂 练习题 答案 解析 DOCX
& 金锄头文库所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
本文标题：第7章算法程序与计算系统之灵魂练习题答案解析 链接地址：
当前资源信息
类型： 共享资源
格式： DOCX
大小： 868.67KB
上传时间：
&& 侵权内容
&& 违法内容
&& 其它类型
&|&川公网安备 12号&|&经营许可证（蜀ICP备号-1）(C) by Sichuan Goldhoe Inc. All Rights Reserved.2.3　解决问题的策略
本文所属图书&>&
本书收录程序设计竞赛经典试题，在解题过程中讲解各种算法设计技巧和数据结构，培养读者的解题能力。读者可亲自编写各章习题程序并获得评分，所有示例均附有解题过程及详细说明。本书是学习解题技巧时必不可少的&&
遇到简单的问题时，直接利用已知技术便可轻松解决问题。若是遇到难题，需试用各种手段去寻找答案。本节先介绍几个最常用的策略，之后再介绍应用这些策略的示例。本书习题中大量使用这些策略，希望各位解题过程时，留意着手解题的方法。
直观而的着手方式
解决问题的策略中，首先强调的是对问题和答案结构的直观感受。通过直觉能够估计出解决当前问题的算法应具备什么样的形态。了解了答案的整体轮廓，就等于成功了一半。
当然，如果所有问题都能够一看就知道该如何解答，也就没必要本书了。直觉可通过时间慢慢培养，通过解决看起来毫无头绪的问题，一点一点积累经验。
那么，该如何解决没有头绪的问题呢？或许可以坐在那儿，期待着灵感敲门。但也可选择更的方法，从零开始为解决问题逐渐打下基础，然后再循序渐进。
本节提出的几点疑问会提供一些着手方法，帮助各位面对超出自己能力的问题。这些方法可与问题解法直接联系，也可以提供解决问题必需的一些直观感受。当然，这些疑问不可能解决所有问题，但大多数情况下能够成为解决问题的好起点。
针对系统着手方法的一些疑问
下面是对解决问题非常有用的一些疑问。依照适用范围由大到小的顺序进行排列。
以前解过类似的题吗？
如果以前解过形式相近或相关的问题，就可以预想套用相似方法解题。建议各位准备参加程序设计竞赛时多做练习的用意也在于此。
当然，单纯地多解题并不能积累更多经验，而且竞赛中几乎不可能遇到与练习题一模一样的问题。因此，要想让解题过程完全变成经验，需全面理解其原理，并学会举一反三。
例如，假设已经解开了寻找铁路网上两个城市的最短路径问题。最短路径问题已经为大家所熟知，而且有很多解决此问题的标准算法，所以会很容易认为背完代码就能解开所有最短路径问题。那么，该如何解决如下的变形题呢？
同一座城市不访问第二次的前提下，寻找最长路径。
换乘火车的次数少于四次的前提下，寻找最短路径。
两个相距最远的站点，经过各个站点的最短路径。
两个相距最近的站点，经过各个站点的最长路径。
寻找距离最长的区间和距离最短的区间之差最小的路径。
这些问题中，有一些题可以直接应用最短路径问题来解决，还有一些则不能。要区分哪些可以直接应用、哪些不能，需完全理解最短距离算法的原理及执行过程。
即使问题的形式不一样，但解题目的一致，那么也属于变形题的范畴。例如，计算某个事件发生的概率或都有哪些可能性的问题，十有八九能利用动态规划法（参考 8.11节）解决。为了能够根据问题的目的选择适当的着手方式，各位应当掌握区分优化问题、计算可能性个数问题、搜索问题等的方法，并系统学习各算法适用何种情况。
本小节的疑问在各章节的习题解答中也发挥了重要作用。例如下列习题的解答。
合并最长递增子序列（joined longest increasing subsequence）（第8章练习题，习题ID：JLIS）
信号路由（第30章练习题，习题ID：ROUTING）
检查酒驾（第30章练习题，习题ID：DRUNKEN）
竞选承诺（第30章练习题，习题ID：PROMISE）
能否从简单的方法开始呢？
遇到以前没有解过的，或不适用类似问题解法的问题，该从哪儿着手呢？本书中很多习题从&能否用笨办法解决呢？&的疑问开始。也就是说，先不管时间和空间的约束，编写一个能解决问题的、最得手的算法。该策略的首要目的是防止把简单的解法复杂化。计算机的运算能力远远超过人类，人们觉得要耗费很长时间的运算过程，计算机可在很短的时间内完成。历经千辛万苦写出复杂的算法后，才感悟到&原来简单而慢速的算法就已足够满足解题时间要求&，此时会让人懊恼不已。
当然，简单的算法不可能解决所有问题。这种方法之所以有用，是因为高效率的算法通常是以简单的算法作为基础的。此时采取更有效率的数据结构和避免重复计算等措施对算法进行优化，直到算法的执行速度足够快时再应用解题。这种解决问题的方法不仅非常有效，而且思考过程跨度小，遇到难题值得一用。
即使通过渐进式改善都无法解决问题时，也要先考虑能否用简单的方法。这种想法有其重要意义。简单的方法能够定义算法效率，因为只有先了解一个简单算法的运行时间，才能比较出其他高级算法的效率到底提高了多少。
通过示例看看如何适用渐进式改善。把N（N&30）个糖果尽可能公平地分给3名儿童，得到糖果的总重量最重和最轻者的差距越小，说明分配越公平。每个糖果的单重是20以下的整数，求可能的最小差距。
最简单的解题方法是按照所有可能的分法逐一计算。可能的分法应该是3N种，最多可能的分法是205万亿种。这对人来说是一辈子也算不完的庞大数字，其实其中包含了许多重复的可能性。假定所有糖果的重量都有类似的简单输入，则可明白此时的情况。两名儿童互相交换重量相同的糖果，对结果不会产生任何影响。更重要的是，分法的公平性以得到的糖果总重衡量，而不是分到的个数。205万亿种可能的分法中，将每名儿童所得糖果总重量相同的可能性合为一种时(N &20)3=6003，最大值约为2亿种。
对此状态空间，可利用广度优先搜索法（Breadth-first search，第29章）求解，但计算量还是太大，因为两亿个数据很难全部读入内存。接下来的优化步骤要从极值入手。假如每个儿童分到的糖果总重量之差大于20，因单个糖果的最大重量是20，所以得到糖果最多的儿童送一个糖果给得到糖果最少的儿童，也不会发生总重量的排序变化。以此类推，总重量的差别会慢慢减少。还可以判断出，差别大于20的答案绝对不会是正确答案。总重量大于220的情况也可以忽略（因为此时肯定有个儿童得到的糖果重量小于200）。经过上述过程可以得出，符合条件的可能性为2203，约为1000万种。
优化到这里就可以开始解题了，但还有一个更快的方法。3名儿童中谁得到的最多或最少，对于答案是无关紧要的。比如，得到的糖果总重量为(180, 190, 200)还是(200, 190, 180)，答案都是20，那么就可以只考虑总重量由小变大的情况。不同3个数的排列方法共有6种，这么一来，可能的答案减少为1/6，约200万种。以上的优化方法没有什么特别的奥妙，却使计算量减少到了一亿分之一。
使用这种优化方法的示例还有四叉树问题（第7章练习题，题目ID：QUADTREE），本书最重要的算法设计范例之一的动态规划法（第8章）也属于这种类型。因此，有关动态规划法的习题也将应用相同方法求解。
能否把解题过程公式化？
渐进式着手方法并不是万能的。学习过程中会遇到很多意想不到的问题，遇到这些需要超强灵感才能解决的问题时，先利用简单的输入量（例如题目给出的示例输入量）手写解题。把自己的解题过程转化为公式后，常常能设计出解题的算法。即便不能，此解题过程也会让自己了解要设计的算法应该注意哪些因素。
手写解题方式对已经知道该如何解答的问题也同样有用，通过它，我们能够在编写程序代码前了解算法有没有被忽略的部分。虽然在竞赛中因为时间关系无法做到这一点，但编写完所有程序再利用示例输入量执行，经过长时间调试最终才发现算法有问题的时候，往往会让人感到十分沮丧。所以建议大家，越着急越要稳重。
下面是使用此方法的一些练习题。
Quantization（第8章练习题，题目ID：QUANTIZE）
逃狱的韩尼拔博士（第8章练习题，题目ID：NUMB3RS）
恢复实验数据（第9章练习题，题目ID：RESTORE）
制定参赛顺序（第10章练习题，题目ID：MATCHORDER）
魔法药水（第14章练习题，题目ID：POTION）
设置陷阱（第32章练习题，题目ID：TRAPCARD）
能否简化问题？
另一个解决问题的工具是，先解一个比较容易的简化版本。简化一个问题有很多种方法。例如，去掉问题的约束条件、减少计算的变量、多维问题降到一维问题等。简化问题的方法可对原问题的解法提供直观感受，或可以直接利用以解出原题。
下面举例说明。假设如图2-1所示的二维网格中有N个点，而且只能沿着横线或竖线移动。两点的距离是X坐标差和Y坐标差的和。例如，坐标为(7,1)的点和(2,3)的点间距是5+2=7。求到给出的N个点距离之和为最小的新点坐标。图2-1中，以&表示的点就是答案。
解决这个问题的最简单的方法是，先把问题简化成一维的形式。简化为在直线上寻找到给出的点的距离之和最小的点。答案比想象的要容易。设一个点X，左半部分点的个数多于右半部分，应该向左侧移动，反之则移向右侧。给定的点N如果是单数，中间的点就是最佳点；若是双数，中间两点的区间就是最佳区间。
那么，怎样把简化题的解法应用到原题呢？实际上，这两道题有直接关联。原题中，两点之间的距离可以分为横向和纵向分别移动了几个格。对于一个点来说，不管横向移动了多少，纵向的位移是不会发生变化的。因此，可以把题分为将给出点映射[ 映射（project）到X轴的含义是，将点(x,y)移动到X轴，使其坐标变为(x,0)。]到X轴的题1和映射到Y轴的题2。这两道题分别代表原题的横向移动量和纵向移动量。最后，两题答案之和就是原题答案。
如果我们遇到的都是这类问题，简化后的解法能直接关联到原题解法，那固然是件好事。但经常会遇到简化后的解法需再次扩展才能与原题解法相关的情况。
下面是使用此方法的一些练习题。
非对称铺设（第8章练习题，题目ID：ASYMTILING）
龙曲线（第9章练习题，题目ID：DRAGON）
加热便当（第10章练习题，题目ID：LUNCHBOX）
儿童节（第29章练习题，题目ID：CHILDRENDAY）
局域网（第31章练习题，题目ID：LAN）
能否画成图？
获得直观解法的另外一种方法就是画草图。与罗列数字相比，人的思维模式更容易接受直观的几何图形。即使问题的内容和几何学无关，几何图形也对解题有很大帮助。假设遇到关于两个整数的问题，可以把整数对画到二维的坐标系，或者在直线上标成一段区间。虽然这种着手方法并不是每次都有效，但很多情况下会提供解决问题的决定性的直观感受。下面是使用此方法的一些练习题。
合并字符串（第10章练习题，题目ID：STRJOIN）
是呆子？不是呆子？（第15章练习题，题目ID：NERDS）
是呆子？不是呆子？2（第22章练习题，题目ID：NERD2）
能否用公式表达？
目前为止，我们使用的方法都是把问题朝着利于获取直觉的方向展开的，其实把问题用公式的形式重新表达也是很有帮助的。公式的展开、消减等纯粹的数学操作会对解决问题带来莫大的好处。下面是利用此方法的练习题。
退选课程（第12章练习题，题目ID：WITHDRAWAL）
能分解问题吗？
还有一种解题方法是，把问题转变成简单的形式。其中代表性的方法是制约条件分解法。此方法把复杂的制约条件分解成若干个简单条件组成的集合形式。一般而言，与一个复杂的条件相比，若干个简单条件的问题更容易解决。
例如，N名选手参加400m赛跑，官方记录了每个选手的历史最好成绩和最差成绩，分别定义为best[]和worst[]。为方便解题，假定每个选手只能跑出这个区间段内的成绩。利用这些数据和假设，体育记者们刊登了M个如下形式的报道。
1.选手i肯定输给选手j。
2.选手i和选手j都有可能战胜对方。
先确认这些报道是否有误。例如，A总是输给B，B总是输给C。那么，&A和C都有可能战胜对方&的报道肯定是不成立的。设计算法，求在报道目录已经拟定的条件下，满足所有报道真实性的历史成绩集合。
如图2-2所示，把各选手的历史成绩记录(best[i], worst[i])标成一维直线上的区间。（应用了前面介绍的可视化方法。）此时，第一种形式的报道相当于选手i的成绩记录区间总是在选手j成绩记录区间的右侧。图2-2中，二号选手和一号选手属于这种情况。第二种形式的报道应该是什么样的呢？两个选手都有可能战胜对方，相当于两个选手的历史成绩记录有一个不为0的交集。图2-2中，零号选手和一号选手属于这种情况。
对于这个题，先把提出的要求公式化（应用了前面介绍的过程公式化的方法），然后将第二种形式的报道条件转换成第一种形式的报道条件。第一种形式的报道条件可以用公式worst[j]＜best[i]表示。假如这种条件有若干个，为求满足这些条件的变量，可以利用第28章介绍的相位校正算法。
接下来怎样转换第二种形式的报道条件呢？为使两个区间的交集不存在或大小为0，要么i区间在左侧（worst[i]&best[j]），要么j区间在左侧（worst[j]&best[i]）。这两个条件都不成立时，两个区间必存在大于0的交集。因此，可用如下公式表示第二种形式的条件。
!(worst[i]&best[j])&&!(worst[j]&best[i])
展开逻辑非（NOT）运算可得出以下公式。
(best[j]&worst[i])&&(best[i]&worst[j])
经过以上步骤，第二种条件分解成两个第一种条件。
对2N个best[]和worst[]变量进行相位校正（第28章）后，得到最后的答案。
能否倒序解决问题？
还有一个非常有用的方法是，把问题的内在顺序颠倒一下。应用此方法的典型示例是画鬼脚（又称画线抽签）。假设决定玩画鬼脚游戏，输了的人为大家买零食。先画好与参加人员数量相同个数的竖线，然后在竖线最下端分别写上&光吃不买、边跳草裙舞边吃零食、买零食、出1万韩元、出2万韩元、出50万韩元&等事项。正当大家要选择竖线另一侧的出发点时，有个人打了个嗝。借此大家分散注意力的机会，怎样先选择起始点，最终能选上&光吃不买&这一项呢？
玩过此游戏的人都能猜到这个题的答案，应该是从&光吃不买&这项开始逆向前进到起点。这比从所有起始点开始逐个走完后再选择要快得多。还有很多这种颠倒内在顺序就会变简单的问题。这说明，虽然寻找A到B的方法比较难，但寻找B到A的方法可能比较容易。
下面是利用此方法的练习题。
反转插入排序（第22章练习题，题目ID：INSERTION）
安装监控摄像头（第28章练习题，题目ID：GALLERY）
排序游戏（第29章练习题，题目ID：SORTGAME）
能否强制排序？
作为倒序法的扩展，没有顺序的问题可利用强制排序的方法。如图2-3所示，5&5大小的格子中，每个格子代表一盏灯。点击一次，此格子和上下左右相邻的格子中的灯会发生状态变化。亮着的会熄灭，熄灭的会点亮。图2-3(a)和(b)表示点击最中间的格子后发生的状态变化。点击次数最少的前提下，怎样才能点亮所有的灯呢？
为方便解题，我们需要先弄清两个问题。
点击顺序无关紧要：每个格子的状态取决于自身和相邻格子的点击次数。因此，无论以何种顺序点击，同一格子点击相同次数后，最终状态不变。
一个格子没必要点击两次以上：点击两次格子等于没有点击。上面提到和点击顺序无关，因此，两次点击相同的格子等于浪费了点击次数。
格子的数量为5&5，而且每个格子只有点击/不点击两种可能性。所以共有225种点击方式。全部尝试一下即可找出以最少点击次数点亮所有灯的方法，但有比这更好的思路。
该方法的关键是给问题加上强制条件，即总是以特定顺序点击格子。原题中点击顺序无关紧要，所以加上这个条件对结果不会产生任何影响。假设从最上面一行的最左侧格子开始依次判断是否点击，而且按这个顺序对每个格子只判断一次。第一行即使添加该强制条件也不会有变。到第二行开始要考虑已经点击完成的上一行的状态。如图2-3(c)所示，格子c要不要点击呢？点击c，格子a的灯会熄灭。按照我们判断点击的顺序，a格子的灯熄灭就再也没有点亮的机会了，所以不应该点击c格子。反之，不点击d就没有机会点亮b，所以必须点击d。以此类推，只要确定了第一行的状态，其余每一行的点击方式就能自行确定。第一行的状态共有25种，根据每个状态逐个计算就能得出答案。需要计算的状态从225减少到25，计算量减少到了百万分之一！
数数时强制排序法也非常有用。计算满足特定条件的答案个数时，一题多解的题目常常会出现重复计算的情况。为便于解题，通常先将解题过程强制排序。
下面是利用此方法的练习题。
盖游戏板（第6章练习题，题目ID：BOARDCOVER）
多联骨牌（第8章练习题，题目ID：POLY）
韦布巴津（第9章练习题，题目ID：ZIMBABWE）
可否只考虑特定形式的答案？
作为强制排序法的扩展，还有正规化（canonicalization）方法，它把形态不同而结果相同的答案归纳到一个集合，解题时只考虑各集合中具有代表性的个体。
移动图2-4中粗实线的圆A，能否覆盖所有虚线圆呢？如果可以，圆A的圆心应移动到何处才能完全覆盖虚线圆？解题时可适当移动圆A的圆心来寻找答案，这种逐个寻找的方法会导致计算量惊人地庞大。这道题的难点在于，A有无限个圆心坐标值。利用正规化可以只考虑有限个坐标值，这样就可在其中挑选正确的答案。
为了使用正规化方法，需找到一种将得到的任意答案都转换成特定形式的变换方法。覆盖圆问题中能够使用的变换过程参考图2-5。图(a)中，粗实线圆A覆盖了所有虚线圆，且没有交点。图(b)是向下移动圆A，直到与虚线圆有交点的状态。接下来在保持相交的情况下，把A按照逆时针方向旋转，直至出现第二个交点，如图(c)所示。图中，A依然覆盖了所有虚线圆，且已与两个虚线圆相交。
利用以上变换过程，可以把所有覆盖虚线圆的状态都转换为和两个以上虚线圆相交且能够覆盖的状态。换言之，只要答案存在，就肯定会存在与两个以上虚线圆相交并覆盖所有圆的状态。有了这些条件就可以组合出不同的虚线圆对，并能够求出与虚线圆对相交的实线圆位置。对于一对虚线圆和实线圆半径r，A的圆心最多能在两个位置[ 设两个圆的中心坐标和半径分别为(x1,y1)、(x2,y2)和r1、r2时，覆盖这两个圆且内接的A圆心位置是：以(x1,y1)为圆心、半径为r&#61485;r1的圆和(x2,y2)为圆心、半径为r&#61485;r2的圆的交点。]出现。最后，只要再判断这些圆心的相应位置中那些能覆盖所有虚线圆的A圆心位置，就可以得到最终的答案。
正规化方法虽然很有用，但每个问题的具体操作都不相同。只有具备大量的练习经验，才能领会真正的使用方法。
下面是利用此方法的练习题。
郊游（第6章练习题，题目ID：PICNIC）
有限单词接龙（第28章练习题，题目ID：WORDCHAIN）
您对本文章有什么意见或着疑问吗？请到您的关注和建议是我们前行的参考和动力&&
您的浏览器不支持嵌入式框架，或者当前配置为不显示嵌入式框架。
文章下载读书}