论文国家队栗师

《论文国家队栗师》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、转化目标在解题中的应用湖南省长沙市长郡屮学栗师【摘要】本文主要简单讨论目标转化思想对算法和分析解决问题的应用。第一部分概述了为什么要目标转化。第二部分举例说明了转化目标在算法设计中的作用，先达到转化后的目标，再通过转化后的目标得到最终目标。第三部分也通过一道例题，介绍了转化目标在分析问题中的作用。最后总结一些常见的转化目标的方法，以及怎样才能灵活的运用它。【关键字】转化目标、放大、缩小、简化问题【正文】一、引言在信息学算法设计的过程中，总会遇到这样或者那样的困难。一个很人的原因就是人的思维的深度和广度都是有限

2、的，而未知世界是无穷的。当遇到一道难解决的问题时，总是觉得目标太遥远，关系错综复杂，无从下手。这时，不妨尝试转化一下日标，从转化后的日标进行思考。例如，减少限制，放松条件，缩小范围等。解决了转化后的H标后，再站在一个新的髙度设计算法，或第1页共15页者把转化的目标的算法推广到原目标。目标转化思想从两个方向为我们提供了捷径：算法和思路。二、在算法设计中应用转化目标方法如果一步不能达到目的，那么就分步解决，每一步就达到了一个屮间口标，这种方法会经常用到。最常见的就是，如果H标有多个限制，先只对一个限制的得出结论，

3、再从得出的结论出发，考虑其它的限制。下面是以PolandOlympiadofInformatics2003的一题为例，来说明这一种方法。［例1］超级马在一个无限的棋盘上有一个超级马，它可以完成各种动作。每一种动作都是通过两个整数来确定——第一个数说明列的数（正数向右，负数向左），第二个数说明行的数（正数向上，负数向下），移动马来完成这个动作。任务编写一个程序从文本文件SUP.IN输入说明各种超级马的数据库。对每一个超级马进行确认，是否通过自己的行动可以到达盘面上的每一个区。将结果存储到文本文件SUP.OUTo

4、输入在文本文件SUP.IN的第一行中存在一个整数k,它代表数据库的数!<^<100o在这个数字后出现K数据库。它们的何:一个第一行中会出现整数N,它是马能够完成的各种动作的数，19口00。接下来数据库的每一个行中包含两个整数P和0它们由单个空格分开，说明动作，・100勻，^<100o猛出文本文件SUP.OUT应由K行组成，当第i个数据库的超级马可以到达盘面的每一个区，第i行应包含一个词TAK,而另一个词NIE则恰恰相反。输入样例252422-3-3431351-3第2页共15页21414-22-2输出样例TA

5、KNIE2.1确定算法模型。看到题Fl,最容易想到的算法是广搜。从当前已知能够到达的格子出发，按照马的走法，扩展出另外一些能到达的格子，一直扩展下去，最后判断是不是扩展完了所有的棋盘。很快会发现这种做法是不行的，棋盘上格子的个数是无限的，不能判断能够到达所有的格子。但这个困难马上就有了解决的办法，显然只要判断超级马是否能到达开始点的4个相邻格。因为如果能够到达这4个格子，那么必然能够到达棋盘上的任意一个位置。问题解决了没有？没有。虽然最终冃标只需耍判断四个格子，但是，它在走到这4个格子的过程中经过的点可能会有

6、很多个。更糟糕的是，当问题无解时，无法进行正确的判断，最后实现算法时造成死机。如杲把无限的棋盘变成相当大的有界棋盘，看它在这个有界棋盘上能否到达这4个格子。但这仍然是无用功，这个有界棋盘会有很大，这样时间效率很低，算法也缺乏证明。尝试各种图论算法、动态规划、贪心等，最后都以意料Z中的结果一一失败而告终。要得到高效的算法，似乎只有一条出路：数学思想。要用数学思想解题，先要建立数学模型。以超级马最开始的格子为原点建立平面坐标系。然后把马的一种动作用一个平面向量P,来表示，那么，我们耍判断，对丁“任意的是否都存在一

7、组ci.C2.C3Cn(c>=O,l

8、13(・3,・3)+5(4,3)+3(1,3)二(0,1)。2.2“放大”目标。这是一个线性方程，未知数比较多，而方程只有一个。直觉告诉我们，如果方程有解的话，那么解的数量应该是非常多的，很有可能是无穷多个。从构造出一组解的角度进行思考是比较明智的选择。当尝试了各种各样的构造方法后，发现有两个因素影响着我们的构造：一个就是，要使右边向量的Y值达到1；另一个就是，耍使左边的系数c都非负。摆在面前的就是