算法问题实战策略——2.2　解决问题的过程

首先介绍现今最流行的一个解决问题的算法，它因著名量子物理学家理查德•费曼（Richard Feynman）最早使用而得名。这个算法不仅功能强大，而且包含了解决问题所需的全部因素。费曼利用此算法解决了量子力学方面的诸多难题。 下面是费曼算法的详解。 1. 把问题写到黑板上； 2. 冥思苦想； 3. 把答案写到黑板上。 是的，费曼算法其实是一个（半个）玩笑 ，但该算法也有值得各位学习的部分。首先，算法把解决问题的过程分成了几个阶段。分阶段的想法看起来算不上什么高招，但正是通过分阶段能够判断何处有不足、何处有待改善。另外一个非常重要的内容是，该算法中“把问题写到黑板上”的阶段。要把问题写到黑板上，首先需阅读问题的内容，然后用自己熟悉的术语进行整理。此过程的重要性将在下一节进行说明。 那么，其他人会怎样分割解决问题的过程呢？解决问题领域的经典著作《怎样解题》（How to Solve It）把解题过程分为如下四个阶段。 1. 理解问题。 2. 制定解题计划。 3. 按照计划解决问题。 4. 回顾解题过程，思索是否有更好的解题方法。 此处把费曼算法中的冥思苦想阶段分成了制定计划阶段和执行阶段，而且增加了解题后思索是否有更好解题方法的步骤。下面结合这两种方法为程序设计竞赛编写一个六阶段的算法。 算法如代码2-1所示，虽然看起来非常不起眼，但每个阶段都很重要，缺一不可。下面了解一下各阶段都要做什么、注意些什么。 代码2-1　面向程序设计竞赛的六阶段解决问题算法 1. 阅读并理解问题； 2. 用熟悉的术语重新定义问题； 3. 制定解题计划； 4. 验证计划； 5. 通过程序实现解题； 6. 回顾解题过程，思索有没有更好的解题方法。 第一阶段：阅读并理解问题 解决问题算法的第一阶段是阅读并理解问题。很多人认为完成此阶段并不难，但决不能忽视其重要性。无论是第一次参加程序设计竞赛的初学者还是历届冠军，所有参赛者的共性错误就是审题不清。 程序设计竞赛要求参赛者在规定时间内尽可能快速解题，而参赛者往往粗略阅读题目和题后图片、输入输出示例，以推测题目的内容。这种欲速则不达的行为必将会让选手付出惨痛代价，所以我们必须详细阅读题目说明，理解其含义。另外，如果只理解题目的用意而未能理解细节制约条件的话，通常还是无法正确解答。因为程序设计竞赛不容许有半点失误，即使它们对整体功能影响甚微。 第二阶段：重新定义和抽象化 解决问题算法的第二个阶段是，利用自己熟悉的概念和术语重构问题。该阶段有助于直观理解问题要求，要求越复杂越能展现其重要性。 还有一个重要过程就是抽象化。所谓抽象化就是，借用我们已经熟知的数学/计算机科学的概念，表达现实世界概念的过程。因现实世界的概念过于复杂，为便于理解，在仅保留其本质的前提下，简化并表述为易于应用的形式。这种过程称为抽象化，它为我们提供了可以使用已知工具解决问题的机会。 重构问题的方式不同，程序设计的方法也会发生根本性的变化。难题可以变容易，简单的题目反而有可能变难。因此，抽象化实际上决定了程序设计的方向。选择哪个部分进行抽象、如何重新定义问题，这都是成为一个优秀程序员的必经过程。本书有很多这方面的好习题。 第三阶段：制定解题计划 解决问题算法的第三个阶段是制定解题计划，其中要包含用什么方法解决问题、选择什么样的算法和数据结构等。可以说，这个阶段是整个算法的核心。如果要解的题简单到可利用已知算法和数据结构就能解开的话，此过程会变得非常简单。但遇到不能马上勾画出解决方案的难题，此过程会变得相当棘手。 2.3节将详细介绍制定计划时的一些策略。 第四阶段：验证计划 并不是制定好计划就可以马上编写程序，开始实施前要经过验证过程。在此过程中，首先要证明设计的算法能否在所有情况下都正确执行，之后要确认执行时间和所占内存是否符合规定。 第4章和第5章会详细介绍各种算法的效率分析方法和正确性证明策略。 第五阶段：执行计划 经过这些复杂过程后，终于进入执行计划阶段，即开始编写程序代码。不管想出了多么精妙的算法，实现方法不正确或效率低下都会使整个程序无法正确运行。因此，要认清本阶段的重要性。 第3章会介绍执行计划阶段的注意事项和编写优秀程序的准则。 第六阶段：回顾 回顾阶段当下不会对解决问题有什么直接影响，但从长远来看，该阶段影响最大。此处的“回顾”就是回想解题过程并对其进行改善。 也许各位会想，既然都已经解完题了，回顾解题过程还能学到什么呢？要记住，单凭一次解题过程不可能完全掌握这个问题包含的所有知识。通过回顾过程可摸索出效率更高的算法、编写出更简洁的程序代码，或者寻找出更直观地应用算法的方法。本章介绍的解决问题的技术既没有要死记硬背的伪代码，也没有严格的论证，而是一种抽象的技术。因此，要练就这种技术就需不断回顾自己是如何使用的，并加以改善。 高效回顾的最好方法是，解题时把解题代码和解题过程中获得的经验记录成册，要记录解题的方法、着手解题的方式、寻找解法过程中的决定性领悟等。这看起来无关紧要，但实际操作后会发现，这些记录对提高自身能力有很大帮助。以后读起来可以温故知新，不仅回想起以前学过的内容，还能够将不同问题之间的共性模式化。 另外，出现错误时也要记录出错的原因。从过去的失误中学习是很难的，所以大多数人会反复犯下同一个错误。错题记录能了解自己经常失误的部分，最终减少这些失误。看着自己的记录越来越多，也算是学习中的一个乐趣吧！ 还有一个回顾的好办法——查看其他人为解决同一问题而编写的代码。即使使用了相同的算法，这些代码也不可能完全一致。虽然其他人写的代码理解起来比较难，但观察另外一种角度的解题方法，会有意想不到的收获。所以不要独自解决问题，参加学习小组（Group Study）或通过互联网和别人一起学习才能快速提升自身能力。学习当然要靠自己努力，但通过别人的建议或答案受到的启发会大幅提升学习效率。到TopCoder或algospot在线评分网站可以查看到别人提交的源代码，对学习大有裨益。 不会解题时 解决问题的算法不是万能的。虽然我们期望用一种方法能够解决所有问题，但每个人不知什么时候就会遇到不会解决的问题，这时候该怎么办呢？虽然常说解题前不要参照标准答案，但初学阶段抱着一个题不放也是不可取的。过了一定时间还是不能解题时，应该参照别人的源代码或答案。设定这样的原则并加以遵守，会对入门阶段的解题带来很大帮助。 需要注意的是，参照别人的源代码或答案后，一定要回想自己的解题过程。回顾自己是如何解题的，为什么没有想到解题的方法。第一次接触的技巧或方法很难学到轻车熟路的境界，但使用两三次后再遇到类似题目就会马上想起。 注意事项 当然，解题时并不一定要完全遵循以上几个阶段，“分阶段”方法毕竟只是为帮助各位思考而已。经验丰富的参赛者不会严格遵循这些步骤，但也不会完全忽略它们包含的内容，有经验后就会下意识地去遵循。