算法合集之《信息学竞赛中的思维方法》.docVIP

信息学竞赛中的思维方法 广东省韶关一中 陈彧 【关键字】信息学 思维方法 【摘要】本文将借鉴一些数学思维理论，探讨思维方法在信息学竞赛中的地位和作用，并介绍信息学竞赛中的几种思维方法，包括：试验猜想及归纳、模型化、分类及分治、类比。其中将引用大量的例题进行思维过程的分析，大部分的例题是1999年NOI、IOI试题，具有广泛的代表性。最后总结本文讨论的目的及启迪 【引论】 “奥林匹克是思维的体操”。同其它学科竞赛一样，信息学竞赛是在丰富的知识、一定的实践能力的基础上，思维与思维的竞赛。优秀的选手往往具有快速、敏捷的思维。因此，在我们不断探讨方法、总结经验的同时，有必要尝试探索系统的思维方法，以达到启迪思路的目的。注意思维方法并不是解题方法，我们重在对思考问题的过程的讨论，而不是对解决问题的算法的总结。 在对思维方法的具体讨论之前，让我们来看看数学家G·波利亚在1944年提出的“怎样解题表”[1]： …… 你以前见过它吗？你是否见过相同的问题而形式稍有不同？ 你是否知道与此有关的问题？你是否知道一个可能用的上的定理？ 看看未知数！试想出一个具有相同未知数的或相似未知数的熟悉的问题。 这里由一个与你现在的问题有关，且早已解决的问题。 你能不能利用它？你能利用它的结果吗？你能利用它的方法吗？为了能利用它，你是否应该引入某些辅助元素？ 你能不能重新叙述这个问题？你能不能用不同的方法重新叙述它？ 回到定义去。 如果你不能解决所提出的问题，可先解决一个与此有关的问题。你能不能想出一个更容易着手的有关问题？一个更普遍的问题？一个更特殊的问题？一个类比的问题？你能否解决这个问题的一部分？……如果需要的话，你能不能改变未知数或数据，或者二者都改变，以使新未知数和新数据彼此更接近？ …… 尽管这张表是为解决数学问题而设计的，但是它给我们的启迪是多么深刻！信息学与数学的联系是何等的紧密，而数学思维又是一门成熟的理论，它给我们的探讨带来宝贵的启示。 【正文】 思维方法是多种多样、因人而异的。本文将选取其中最具代表性的几种。首先，我们试按传统的“纵向”、“横向”标准，将本文要讨论的信息学竞赛思维的几种一般方法划分为： 纵向：试验猜想及归纳、模型化（化归）。 横向：分类及分治、类比。 其中模型化及类比是这里重点介绍的思维方法，当然此外我们也会多少涉及一些其它的思维方法，如递归、筛选、最优策略、逆向思维等等也都是我们常见、熟悉的，但因篇幅所限而略去。 试验、猜想及归纳 我们每个人的知识构成不同，解决问题的经验不同，思维的品质不同，甚至性格各异，面对陌生的问题时，产生的直觉、“灵感”就五花八门、各种各样。在分析问题时，我们会往往不止一次地做猜测：“会不会是这样”、“这不就是某某问题吗”。这些就是在个人知识、经验、智力的作用下的一种猜想思维。有时，当问题过于复杂，“老鼠拉龟”——无从下手，无法联系自己的知识时，我们往往希望“尽己所能，先解决规模更小的问题，找找问题是否存在规律吧”。这种“缩小规模”、“找规律”的想法就是试验思维。试验和猜想经常是结合在一起的。不要认为这些思维是“不正规”、不是“名门正道”的，相反，它体现的是人的思维的火花的跳跃的美。归纳的过程是对试验猜想的总结或证明。归纳通常是严格的。不过，竞赛是紧张、紧迫的，在竞赛中的严格的归纳是不简单的、少见的。 来看一个猜想的例子，IOI’99第一题《小花店》（详见[例题7]），经验丰富的选手也许未到题目看完就猜测解题的方法是动态规划，这个猜想的形成诱导他快速地完成题目分析，从而最终确定算法。这个猜想来源于扎实的基本功、广泛的实践和丰富的经验：选手对动态规划的实践较多，思考时可以自然的与做过的例题类比而做出猜想。所以猜想决不是“瞎猜”。 另一种猜想来源于试验。这里有一个最“经典”的例子： [例题1] m,n∈N,1=m,n=k=109,且(n2-mn-m2)2=1，输入k，求m,n使m2+n2最大。(NOI’95) 从数据的规模可“猜想”本题一定蕴含着更为简单的数学关系，但是题目的数学关系不明显，数学分析的难度太大。而用简单的两重循环枚举可以很方便的算出小数据的情况。 K 1 2 3,4 5,6,7 8,9,10,11,12 13… M 1 2 3 5 8 13… N 1 1 2 3 5 8… 通过这些试验，我们猜想符合条件的m,n成Fibonacci数列。实际上： n2-mn-m2= -(m2+mn-n2) = -[(m+n)2-mn-2n2] = -[(m+n)2- n(m+n) -n2] 更多的猜想来自类比。总之，猜想是一种合情的推理，它有利于对思路的正确诱导。[2] 模型化 ——“你能不能重新叙述这个问题？你能不能用不同的方法重新叙述它？” 客观世界是纷繁复杂