浅谈多角度思考在解题中的作用.pdfVIP

浅谈多角度思考在解题中的作用 计算机系 姚金宇     我们在运用各种数据结构和算法解决实际问题中，经常会遇到这样的情况： 我们从正面（即顺着题意）往往无从下手，此时往往逆向思考（即大胆地逆着题 意）会起到很神奇的作用；或者是对于同一个问题，我们可以从多个角度来思考， 此时就需要我们用敏锐的观察力选择一个效率最高或者实现最容易的角度。下面 我们通过两个例子，分别说明这两种情况在具体问题中的体现方式。  【例一】 折纸  有一张 n 个方格子的纸条，格子上无序地写着 1 到 n 这 n 个数字。每个格子 一个数字。现在沿着格子的边线折纸，可以将纸条折成一个小方块（正面只有一 个格子）。这样 n 个数字的方格就竖直地排列起来。             现在要使这些方格上的数字从上到下的排列正好是 1 到 n （无论正反）。例 如上图就是一个 7 个格子的纸条和一种可行的折叠方案。对于给定的纸条和上面 已经写好的数字，请你判断能否折成满足要求的形状。  分析：  从纸条出发开始折叠，我们发现似乎没有什么很好的思路。不妨逆向思考这 个问题：假设纸片事先是剪开成一个个小方格的，把 n 个方格纸片摞起来，再想 办法“连接”它们，使得展开以后成为原来的纸条。我们只需要判断这样的操作 是否可行。而“连接”的依据，就是格子之间的折痕。  由于每个纸片至多只会有左右两条折痕，当我们按纸条上所反映的应有的折 痕，添到这摞纸片的左右两边。如果不存在矛盾（折痕相交），则存在这样的折 叠方式。  例如左图的纸条给我们的信息是：  1 和 4 、4 和 3、3 和 2 之间有三条折痕。  将这三条折痕添上，互相之间并不发生矛  盾，所以存在这样的折叠方式。   而下图的情况则必然会发生相交，因此不存在这种折叠方式：    有了上面的分析，本题就变得十分简单了，我们只需要左右交替地给 n 张纸 片连边，然后判断边是否相交即可（这一步用栈实现，参考判断括号是否匹配的 问题）。连边和判断边是否相交的时间复杂度都是 O(n)，因此算法的总时间复杂 度是 O(n) 。  该问题还可以推广到二维的情况：在一个 n*m 的方格纸上写上 1 到 n*m， 是不是存在一种折叠方式使得满足摞起来的纸片正好是 1 到 n*m 排列。解决办 法也是类似的，只不过现在要从四个方向分别连边，然后再进行判断。  通过上面这个有趣的问题我们可以看出逆向思维的好处，往往能够通过角度 的变换使得棘手难解的问题变得简单。而实际中我们遇到更多的却是，一种思路 看似是比较好的解法，但也许并不是最优的，需要我们进一步变换角度思考，得 到更有效率的实现。下面就是这样一个例子。  【例二】模版（2005 年波兰全国竞赛 POI 试题）  有一个长度为 n 的字符文本 S （n 不超过 106 ），求一个最短的模版串 T ，使 得 T 重复多次以后能够不遗漏的覆盖 S （可以重叠）。例如：  S =ababbababbabababbabababbababbaba       上例中最短的 T=ababbaba。  分析：      首先通过下面的定理确定 T 的取法范围：  定理 4.1 ：模版串T 必然是 S 的前缀  证明：根据题设，T 必须完全覆盖 S 的最初长度为|T|的子串，即T=S(1, |T|)，故 T 是 S 的前缀。■      如果单纯枚举每一个 S 的前缀加以判断，必然没有用到前缀之间的相互联 系。因此需要对已知的信息进行加工处理，将问题进行转化。  设函数 f(i)表示串 S 与串 S(i, n)的最长公共前缀，记作  f(i)=LCP(S, S(i, n ))       并令 f(n+1)=n+1  用扩展 KMP(Knuth‐Morris‐Pratt)算法可以在