资源描述：
《算法合集之《转化目标在解题中的应用》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、IOI2004国家集训队论文栗师转化目标在解题中的应用湖南省长沙市长郡中学栗师【摘要】本文主要简单讨论目标转化思想对算法和分析解决问题的应用。第一部分概述了为什么要目标转化。第二部分举例说明了转化目标在算法设计中的作用，先达到转化后的目标，再通过转化后的目标得到最终目标。第三部分也通过一道例题，介绍了转化目标在分析问题中的作用。最后总结一些常见的转化目标的方法，以及怎样才能灵活的运用它。【关键字】转化目标、放大、缩小、简化问题【正文】一、引言在信息学算法设计的过程中，总会遇到这样或者那样的困难。一个很大的原因就是人的思维的深度和广度都是有限的，而未知
2、世界是无穷的。当遇到一道难解决的问题时，总是觉得目标太遥远，关系错综复杂，无从下手。这时，不妨尝试转化一下目标，从转化后的目标进行思考。例如，减少限制，放松条件，缩小范围等。解决了转化后的目标后，再站在一个新的高度设计算法，或第1页共15页IOI2004国家集训队论文栗师者把转化的目标的算法推广到原目标。目标转化思想从两个方向为我们提供了捷径：算法和思路。二、在算法设计中应用转化目标方法如果一步不能达到目的，那么就分步解决，每一步就达到了一个中间目标，这种方法会经常用到。最常见的就是，如果目标有多个限制，先只对一个限制的得出结论，再从得出的结论出发，
3、考虑其它的限制。下面是以PolandOlympiadofInformatics2003的一题为例，来说明这一种方法。[例1]超级马在一个无限的棋盘上有一个超级马，它可以完成各种动作。每一种动作都是通过两个整数来确定——第一个数说明列的数（正数向右，负数向左），第二个数说明行的数（正数向上，负数向下），移动马来完成这个动作。任务编写一个程序从文本文件SUP.IN输入说明各种超级马的数据库。对每一个超级马进行确认，是否通过自己的行动可以到达盘面上的每一个区。将结果存储到文本文件SUP.OUT。输入在文本文件SUP.IN的第一行中存在一个整数k，它代表数据
4、库的数1≤k≤100。在这个数字后出现K数据库。它们的每一个第一行中会出现整数N，它是马能够完成的各种动作的数，1≤n≤100。接下来数据库的每一个行中包含两个整数P和Q，它们由单个空格分开，说明动作，-100≤p,q≤100。输出文本文件SUP.OUT应由K行组成，当第i个数据库的超级马可以到达盘面的每一个区，第i行应包含一个词TAK，而另一个词NIE则恰恰相反。输入样例252422-3-3431351-3第2页共15页IOI2004国家集训队论文栗师21414-22-2输出样例TAKNIE2.1确定算法模型。看到题目，最容易想到的算法是广搜。从当
5、前已知能够到达的格子出发，按照马的走法，扩展出另外一些能到达的格子，一直扩展下去，最后判断是不是扩展完了所有的棋盘。很快会发现这种做法是不行的，棋盘上格子的个数是无限的，不能判断能够到达所有的格子。但这个困难马上就有了解决的办法，显然只要判断超级马是否能到达开始点的4个相邻格。因为如果能够到达这4个格子，那么必然能够到达棋盘上的任意一个位置。问题解决了没有？没有。虽然最终目标只需要判断四个格子，但是，它在走到这4个格子的过程中经过的点可能会有很多个。更糟糕的是，当问题无解时，无法进行正确的判断，最后实现算法时造成死机。如果把无限的棋盘变成相当大的有界
6、棋盘，看它在这个有界棋盘上能否到达这4个格子。但这仍然是无用功，这个有界棋盘会有很大，这样时间效率很低，算法也缺乏证明。尝试各种图论算法、动态规划、贪心等，最后都以意料之中的结果——失败而告终。要得到高效的算法，似乎只有一条出路：数学思想。要用数学思想解题，先要建立数学模型。以超级马最开始的格子为原点建立平面坐标系。然后把马的一种动作用一个平面向量Pi来表示，Pi=(xi,yi)。那么，我们要判断，对于任意的x,y，是否都存在一组c1,c2,c3……cn(ci>=0,1≤i≤n)，n使得åciiP=(xy,)。i=1于是，就确定了这题的数学模型：解方
7、程。第3页共15页IOI2004国家集训队论文栗师进一步，只需要判断(x,y)为(-1,0)，(1,0)，(0,-1)，(0,1)的情况。而这四种情况是一样的，可以只考虑(0,1)。那么，要判断下面的方程是否有非负整数解：cP+cP+......+=cP(0,1)…………………………………方程①1122nn例如，题目中样例的第1个数据n=5,5个向量是P1=(2,4),P2=(2,2),P3=(-3,-3),P4=(4,3),P5=(1,3)，那么方程①的一个非负整数解就是：3(2,4)+5(2,2)+13(-3,-3)+5(4,3)+3(1,3)=
8、(0,1)。2.2“放大”目标。这是一个线性方程，未知数比较多，而方程只有一个。直觉告诉我们，如果方程有解的
