论文国家队栗师.docx

论文国家队栗师.docx转化目标在解题中的应用湖南省长沙市长郡屮学栗师【摘要】本文主要简单讨论目标转化思想对算法和分析解决问题的应用。第一部分概述了为什么要目标转化。第二部分举例说明了转化目标在算法设计中的作用,先达到转化后的目标,再通过转化后的目标得到最终目标。第三部分也通过一道例题,介绍了转化目标在分析问题中的作用。最后总结一些常见的转化目标的方法,以及怎样才能灵活的运用它。【关键字】转化目标、放大、缩小、简化问题【正文】一、引言在信息学算法设计的过程中,总会遇到这样或者那样的困难。一个很人的原因就是人的思维的深度和广度都是有限的,而未知世界是无穷的。当遇到一道难解决的问题时,总是觉得目标太遥远,关系错综复杂,无从下手。这时,不妨尝试转化一下日标,从转化后的日标进行思考。例如,减少限制,放松条件,缩小范围等。解决了转化后的H标后,再站在一个新的髙度设计算法,或者把转化的目标的算法推广到原目标。目标转化思想从两个方向为我们提供了捷径:算法和思路。二、在算法设计中应用转化目标方法如果一步不能达到目的,那么就分步解决,每一步就达到了一个屮间口标,这种方法会经常用到。最常见的就是,如果H标有多个限制,先只对一个限制的得出结论,再从得出的结论出发,考虑其它的限制。下面是以PolandOlympiadofInformatics2003的一题为例,来说明这一种方法。[例1]超级马在一个无限的棋盘上有一个超级马,它可以完成各种动作。每一种动作都是通过两个整数来确定——第一个数说明列的数(正数向右,负数向左),第二个数说明行的数(正数向上,负数向下),移动马来完成这个动作。。对每一个超级马进行确认,是否通过自己的行动可以到达盘面上的每一个区。,它代表数据库的数!<^<100o在这个数字后出现K数据库。它们的何:一个第一行中会出现整数N,它是马能够完成的各种动作的数,19口00。接下来数据库的每一个行中包含两个整数P和0它们由单个空格分开,说明动作,・100勻,^<,当第i个数据库的超级马可以到达盘面的每一个区,第i行应包含一个词TAK,而另一个词NIE则恰恰相反。输入样例252422-3-3431351-321414-22-。看到题Fl,最容易想到的算法是广搜。从当前已知能够到达的格子出发,按照马的走法,扩展出另外一些能到达的格子,一直扩展下去,最后判断是不是扩展完了所有的棋盘。很快会发现这种做法是不行的,棋盘上格子的个数是无限的,不能判断能够到达所有的格子。但这个困难马上就有了解决的办法,显然只要判断超级马是否能到达开始点的4个相邻格。因为如果能够到达这4个格子,那么必然能够到达棋盘上的任意一个位置。问题解决了没有?没有。虽然最终冃标只需耍判断四个格子,但是,它在走到这4个格子的过程中经过的点可能会有很多个。更糟糕的是,当问题无解时,无法进行正确的判断,最后实现算法时造成死机。如杲把无限的棋盘变成相当大的有界棋盘,看它在这个有界棋盘上能否到达这4个格子。但这仍然是无用功,这个有界棋盘会有很大,这样时间效率很低,算法也缺乏证明。尝试各种图论算法、动态规划、贪心等,最后都以意料Z中的结果一一失败而告终。要得到高效的算法,似乎只有一条出路:数学思想。要用数学思想解题,先要建立数学模型。以超级马最开始的格子为原点建立平面坐标系。然后把马的一种动作用一个平面向量P,来表示,那么,我们耍判断,对丁“.(c>=O,l<z<n),Pi=l于是,就确定了这题的数学模型:解方程。使得(,就X)匕进一步,只需要判断(心)为(・1,0),(1,0),(0,-1),(0,1)的情况。而这四种情况是一样的,可以只考虑(0,1)。那么,要判断下面的方程是否有非负整数解:ClP\+C2Pl+ + CnPn=(0,1)方程①例如,题目中样例的第1个数据n=5,5个向量是H=(2,4),P2二⑵2),A=(・3,・3),A=(4,3),A=(l,3),那么方程①的一个非负整数解就是:3(2,4)+5(2,2)+13(・3,・3)+5(4,3)+3(1,3)二(0,1)。“放大”目标。这是一个线性方程,未知数比较多,而方程只有一个。直觉告诉我们,如果方程有解的话,那么解的数量应该是非常多的,很有可能是无穷多个。从构造出一组解的角度进行思考是比较明智的选择。当尝试了各种各样的构造方法后,发现有两个因素影响着我们的构造:一个就是,要使右边向量的Y值达到1;另一个就是,耍使左边的系数c都非负。摆在面前的就是两块