猜想及其应用猜想及其应用【摘要摘要】猜想是重要的解题策略，对培养人的综合思维能力大有好处。猜想是重要的解题策略，对培养人的综合思维能力大有好处。本文第一部分介绍了猜想的基本要求和实现步骤，提出了两种重本文第一部分介绍了猜想的基本要求和实现步骤，提出了两种重要的得到猜想的方法：类比和归纳。要的得到猜想的方法：类比和归纳。第二、三部分分别介绍了类比、归纳的基本性质、定义，以及解第二、三部分分别介绍了类比、归纳的基本性质、定义，以及解题的一般步骤。每一部分都通过若干道题目实际说明猜想在信息学题的一般步骤。每一部分都通过若干道题目实际说明猜想在信息学竞赛中的应用竞赛中的应用最后总结全文，对猜想的方法、定义、分类、重要性等做了全面最后总结全文，对猜想的方法、定义、分类、重要性等做了全面阐述。阐述。【关键字关键字】猜想猜想 类比类比 归纳归纳【正文正文】一、引言猜想，是解决问题最基本、最重要的方法，是完成从已知世界到未知世界 探索的有力工具。在信息学竞赛中，随着试题的隐蔽性越来越高， “猜想”这一 研究手段也扮演着越来越重要的角色。猜想不是胡猜乱想，必须综合分析条件作出“言之成理”的推测，然后在 猜测的引导下进行“持之有据”的论证。因此猜想绝不仅仅是运气或者投机， 正如一个小学生很难提出费马大猜想（现在已经证明了） ，不经过深入的观察、 分析我们也不可能提出任何有价值的猜想。 进行猜想的基本步骤是：由此可见，猜想是在深入分析问题的基础上，不懈探索、反复修正的过程。 决不可能一蹴而就。 “提出猜想”是整个过程的核心。得到猜想的方法主要有类比和归纳。二、类比猜想所谓类比，就是由两个对象的某些相同或相似的性质，推断它们在其他性 质上也有可能相同或相似的一种推理形式。 形式性的表示为： 事物 A 具有性质 a, b, c, d，事物 B 具有与之相应的类似性质 a, b, c，从而 猜想 B 也有与 d 对应的类似性质 d。 类比是一种主观的不充分的似真推理主观的不充分的似真推理，因此，要确认由类比而得的猜想的 正确性，还须经过严格的逻辑论证。2.1 与熟悉的问题类比与熟悉的问题类比若问题 A（熟悉）已经解决，问题 B（陌生）在形式、结构或性质方面与 A 类似，那么可以猜想：解决 B 的方法类似于解决 A 的方法。形象的表示为：与熟悉的问题进行类比的基本步骤是： 1、分析。分析问题的特征，抽象出模型。 2、联想。与熟悉的，拥有类似特征、模型的问题类比。 3、比较。确定类比对象后将两者比较，分析异同。 4、猜想。根据已知问题猜想新问题的解决方法。【引例】巨人与鬼 问题描述 平面上有 n 个巨人和 n 个鬼（1 AB，OC + OD CD AD + BC AB + CD 新的匹配方案与老的匹配方案相比， “匹配边的长度总和”减小了。故而， 每一个包含相交边的完备匹配都能够转换成为“匹配边长度总和”更小的一个 完备匹配换句话说， “匹配边长度总和”最小的完备匹配一定不包含相交边！将原来的二分图完备匹配模型转换成二分图最佳匹配模型：每条边的权值 设为它两端顶点的欧几里德距离。 问题解决了。小结 本题二分图中的顶点具有特殊性：每个顶点都对应于平面上的一点。因此， 顶点与顶点之间不仅有逻辑关系，还有几何直观几何直观关系。正是由于充分利用了OABCDABCD“几何直观”这一隐蔽关系才使得算法模型豁然开朗。【例 1】青蛙的烦恼 问题描述 池塘里有 n 片荷叶（1的 两侧。不失一般性，设从 i 出发经过若干步到左侧的顶点 B，再到右侧的顶点 C，如下图所示：我们可以做这样的变换：变换后，从 1 到 D 的距离显然比变换前的距离要短；故变换前的方案必然 不是最优方案。所以从 1 出发，第一步只能到 2 或者 n。 同理，如果第一步到了 2，则第二步只能到 n 或者 3；如果第一步到了 n， 则第二步只能到 n-1 或者 2因此最后的最优方案中肯定不存在相交边。猜想 2 是成立的! 接下来的任务就好办了。根据证明容易知道，从 1 出发，第一步只能到 2 或者 n。如果第一步到 2，则问题转化为“以 2 为起点，遍历2.n中的顶点一 次且仅一次” ；如果第一步是到 n，则问题转化为“以 n 为起点，遍历2.n中 的顶点一次且仅一次” 。C1AB实线表示一步到达；虚线 表示多步到达1AB实线表示一步到达；虚线 表示多步到达1AB实线表示一步到达；虚线 表示多步到达CC转化后的子问题与原问题结构相同，只是规模缩小，故可采用动态规划。 设 fs, L, 0表示从 s 出发，遍历s.s+L-1中的顶点一次且仅一次的最 短距离；fs, L, 1表示从 s+L-1 出发，遍历s.s+L-1中的顶点一次且仅一 次的最短距离。则： fs, L, 0 = mindis(s,s+1) + f(s + 1, L-1, 0),dis(s,s+L-1) + f(s + 1, L-1, 1) fs, L, 1 = mindis(s+L-1, s+L-2) + f(s, L1, 1)dis(s+L-1, s) + f(s, L-1, 0) fs, 1, 0 = 0, fs, 1, 1 = 0 其中 dis(a, b)表示第 i 个顶点和第 j 个顶点之间的欧几里德距离。 算法的时间复杂度是 O(n2)。题目小结 【例 1】是一道比较难的题目。解题的突破口在于与【引例】的类比几 何直观上的类似，触发了一个大胆的猜想，分析了最优路线的特性，为动态规 划创造了条件。甚至猜想的证明方法，都和【引例】分析的一些思想密切相关。 这与两个问题本质、特点的类似不无关系。本节小结 与熟悉的问题类比的前提是对事物深入、透彻的分析。只有分析出事物的 本质特性，才有可能将那些为纷繁复杂的具体要素所掩盖的相似模型联系起来， 才有可能根据模型的具体情况提出合情合理的猜想。 同时观察、联想是实现类比的基础。通过观察，得到问题的本质模型；通 过联想，将模型同熟悉的、类似的问题联系起来，提出猜想。2.2 与特殊的问题类比与特殊的问题类比特殊化类比是又一类常用的类比方式。它将问题中的某些条件特殊化、极 端化、边界化，通过对极端情况下的问题的分析，试图找出解题的规律；然后 将其与原问题类比，提出猜想。可以形象的表示为：特殊类比的一般步骤： 1、观察。观察题目条件的特征。 2、特殊化。将一些条件的位置、数量、状态等特殊化。 3、分析特殊问题。问题 A特殊化问题 B算法 B猜想算法 A4、类比。将特殊问题与原问题作比较。 5、猜想。根据特殊化问题与原问题的联系和不同，以特殊问题的解决方案 为蓝本，猜想原问题的解法。【例 2】圆圈点问题 问题描述 平面上有 n 个点（3 ACB，则 X 在圆 ABC 内；如果AXB 0 时。 显然必须先令编号小于 fn, m的青蛙跳到荷叶、石礅上暂留；然后令编号 为 fn, m的青蛙跳到 D；最后再让荷叶、石礅上的 fn,m- 1 只青蛙跳到 D 上。 所以要使得过河的青蛙最多，必须让尽量多的青蛙跳到荷叶、石礅上去。 首先考虑使编号为 n 的石礅上站尽量多的青蛙。可以利用其他的 n-1 个石 礅和 m 片荷叶，所以首先能有 fn-1,m只青蛙跳到编号为 n 的石礅上。 同理最多可令 fn-2,m只青蛙跳到编号为 n-1 的石礅上，最多可令 f0, m只青蛙跳到编号为 1 的石礅上。 故而 fn,m=fn-1,m+fn-2,m+f0,m+m+1。 可以看到，这里的参数 m 不起作用。令 gn = fn, m，则： gi = g0 + g1 + + gi-1 + m + 1 g0 = m + 1 求：gn 稍加分析可知：fn, m = gn = (m + 1) * 2n。 猜想正确。本题小结 这是 NOI2000 第二试第二题，有一定难度，不用归纳猜想很难做出来；即 便做出来，也要花费相当惊人的时间。 需要注意的是：归纳而得的猜想不一定正确，必需严格的证明。证明的方 法大多是数学归纳法。这是由归纳猜想本身的特性决定的。【例 4】排列问题 问题描述 在整数 1，2，N 的排列中，有些排列满足下面一个性质 A：该排列中 除了最后一个整数以外的每一个整数后面都跟有（不必直接紧跟）一个同它相 差为 1 的整数。例如：N = 4，排列 1432 是具有性质 A 的，而 2431 则不满足。 设有一个 N 个数的排列，已知其中 P(P =1）是若干连续整 数，这些整数构成集合s.t。那么倒数第 x+1 位上的数 vn-x+1必然等于 p- 1 或者 p+1（ps.t） 。显然 vn-x+1s.t=s-1.t或者s.t+1，还 是若干连续整数。根据“证明” ，我们进一步猜想： 猜想猜想 2 2 如果一个排列的后如果一个排列的后 k k 位（位（1=k=n1=k=n）是若干连续整数组成的集合，则）是若干连续整数组成的集合，则 这个排列符合题目要求。这个排列符合题目要求。证明 约定该序列的第 i 位用 vi表示。设vn, vn-1, , vn-k+1 =s.t。因为vn-1,vn-k+1也是若干连续整数的集合，所以 vn = s 或 t。 如果 vn = s，那么必有：s+1 vn-1,vn-k+1 如果 vn = t，那么必有：t-1 vn-1,vn-k+1 即这是一个满足要求的序列。因此问题转化为：求后 k 位（1=k=n）是若干连续整数组成的集合的排列 总数（由 1，2，N 组成） 。 接下来的工作就好办了。根据两个猜想，我们很容易想到动态规划。设 gs, r表示满足下面条件的序列 C 的总数： C 由集合s.s+r-1中的数组成，且后 k 位（1=k=r）是若干连续整数组 成的集合。如果原问题中倒数第 i 个位置上的数已经确定为 x（1=i=r） ，那 么 C 的倒数第 i 个位置上的数也要是 x。 则：gs+1,r-1 如果倒数第 r 位确定为 sgs,r-1 如果倒数第 r 位确定为 s+r-1 gs, r = gs,r-1+gs+1,r-1 如果倒数第 r 位不确定0其他情况 gs, 1 = 1 求：g1, n 算法时间复杂度为 O(n2)。本题小结 此题是湖南省队集训试题，具有相当难度的题目。主要是因为给定的条件 比较复杂，很不便于转化利用。因此在考场上，诱使大多数选手使用搜索。 （当 时只有两名选手使用了速度较快的动态规划） 本题的突破口在于两个“惊世骇俗”的猜想的提出。通过这两个猜想，将 很难直接利用的条件转化到我们便于使用的熟悉形势，为后面使用动态规划， 打开了通路。 然而从“列出简单数据”“提出猜想”还是有一段相当的距离。没有丰 富的经验积累、解题灵感、观察能力、概括能力、联想能力是很难发现什么有 价值的结论的。3.3 归纳小结归纳小结本节介绍了归纳法的基本分类、方法，以及在信息学中的应用实例。 归纳是除类比以外，得到猜想的一个重要方法。它的基本思想是从特殊 一般，从简单复杂，从小规模大规模。也是一种“化归”的思想。 另外值得注意的是，归纳不一定是直接归纳猜想出问题的结果。可能像 【例 4】那样，根据归纳而得的猜想不一定与最后的结果直接挂钩；但猜想的结论却对解题思路、解题方向的发展有重大帮助。 进行归纳猜想时要注意发散思维，充分想象往任何可能的方向去想、 去靠。不要让转瞬即逝的灵感溜走。四、总结其实我们解题时都在不知不觉的猜想猜想问题的性质；猜想模型的形 式；猜想算法的内容猜想是从已知向未知探索的重要途径。 猜