浅谈逆向思维在解题中的应用

《浅谈逆向思维在解题中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、正难则反-浅谈逆向思维在解题中的应用绍兴市第一中学唐文斌【摘要》逆向思维是一种思考问题的方式，它有悖于通常人们的习惯，而正是这一特点，使得许多靠正常思维不能或是难于解决的问题迎刃而解。本文通过几个例子，总结了逆向思维在信息学解题中的应用。逆向思维容斥原理参数搜索二分动态规划记忆化引言我们先看一个简单的问题：平面上有四个点，构成一个边长为1的正方形。现在进行一种操作，每次可以选择两个点力和〃，把/关于E对称到G然后把/去掉。求证：不可能经过有限次操作得到一个边长大于1的正方形操作后的结果是相当复杂的，如果我们从正面着手，很难证明命题。不妨从反面来看问题：观察可以发现，每一步操作都是可逆的。即

2、，我们如果可以把正方形变大，也可以把正方形变小。证明：不妨设四个顶点都是整点。假设我们可以通过有限次操作得到一个边长大于1的正方形，那么我们把所有操作反过来对原正方形进行操作，我们可以得到一个边长小于1的正方形。因为四个顶点都是整点，操作之后，点的坐标依然是整数。所以我们得到一个边长小于1且四个点都是整点的正方形。这显然不可能。所以假设不成立。命题得证。上面的例子说明了逆向思维在数学问题中的应用。山重水复疑无路，应用逆向思维，换个角度看问题，便柳暗花明又一村了。例一、DinnerIsReady1ZhejiangUniversityOnlineJudge1442(acm.zju.edu.cn

3、)题目大意:妈妈烧了〃根骨头分给门个孩子们，第了个孩子有两个参数Mim和Maxi,分别表示这个孩子至少要得到加巾根骨头，至多得到Maxi根骨头。输入：第一行包含两个数t7（0〈"W8）,J/（0〈必，表示孩子数量和骨头的数量。接下来n行分别输入Mini和Maxi（0WMinWMaxWM）输出：输出一个整数，表示妈妈有多少种分配方案（骨头不能浪费，必须都分给孩子们）初步分析：该题模型很简单，即求如下方程组的整数解的个数：/=iMin}0厂/?-]

4、1这是一个很经典的组合问题，可由隔板原理得出答案。D=M/=1i=设K-=X+Mini则原方程组转化为0

5、s,

6、无法计算，但是，冈可解！！！我们希望把

7、s,

8、的计算转化到可解的冈。于是：Answer=

9、S,nS2nS3...nSH=

10、S-(S]+

11、S2

12、+...+Sn)+(S]cSr+S]cS?+・..+

13、s“_jcSn)—(-1)"*S]cc...cS.这是一种容斥原理的形式。至此，问题已经解决。我们应用逆向思维，在原集合的模M不可解的情况下，通过可解的训得到答案。并给出了一个基于容斥原理的算法。时间复杂度为0(2!*(n+M)).例二、GreedyPath1有/?个城市，被加条路连接着。最近成立了一些旅行社，在这些城市之间给旅行者们提供服务。旅行者从城市2•到城市丿需要付给旅行社的费用是G,j,需要的时间为7b。很多旅行者希望加入旅行社，但是旅行社只有一辆车。于是旅行社的老板决定组织一次旅行大赚一笔。公司里的专家需

14、要提供一条使得贪心函数尸⑹最大的回路G。F(G)等于总花费除以总时间。但是没有人找到这样的回路，于是公司的领导请你帮忙。输入：第一行包含两个数/7(3W/7W50),刃分别表示点数和边数。接下来m行每行包含一条路的描述。输入四个数,A,B,Ca.b,Ta,b(O^G.^lOO,0W7LW100)输出：如果不存在这样的路，输出0。否则输出回路中包含的城市个数，然后依次输出通过的城市的顺序。如果有很多条这样的路，输出任意一条。初步分析：SaratovStateUniversityOnlineJudge236(acm.sgu.ru)题目要求是求一条回路，但不是边权和最大或者最小，所以我们不能直接

15、使用经典算法。设&二｛V,Q,S为G中所有回路C二（厂,刃）组成的集合。我们的目标是找到集合S中的一条回路使得F©取到最大值：F（C）=应用逆向思维：如果我们知道二（y*,E^wS是一条最优回路，那么ycF（c*）=n工®Q-F（C*）x工®Te=0Zj心*人于是我们定义函数:0&）二max（V，匕f-i—r~MewEewE我们做一个猜想：如果有o（f*）=0,那么存在C*=（叱鯛wS满足yc严二厶ewE*我们认为c*就