(精品)算法合集之《转化目标在解题中的应用》

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,转化目标在解题中的应用,湖南省长沙市长郡中学 栗师,概述,在解题时，总是觉得,限制太多,范围太窄,关系错综复杂,目标太远,困难需要解决！,减少限制,放宽范围,简化关系,解题遇到困难,转化目标,解决某些题目，在算法设计中需要转化目标,题目,超级马,(1),在一个无限的棋盘上有一个超级马，它占据一个正方形单位格，可以完成各种移动动作。每一种移动动作由两个整数来描述,第一个数说明动作左右移动多少格,(,正数向右，负数向左,),，第二个数说明动作上下移动多少格,(,正数向上，负数向下,),。已知一个超级马能够完成的动作，要判断它是否能够到达棋盘上的所有位置。,题目,超级马,(2),SUP.IN,2,5,2 4,2 2,-3,-3,4 3,1 3,5,1-3,2 1,4 1,4-2,2-2,超级马个数,k,(1=,k,=100),动作数,n,(1=,n,=100),每一个动作,(,x,i,y,i,),，,(-100=,x,i,y,i,=100),TAK,表示超级马能够到达所有的位置,NIE,表示超级马不能够到达所有的位置,SUP.OUT,TAK,NIE,确定算法,(1),广搜？,数学方法,Time Limit Exceeded!,动态规划,?,在某种意义上等价于广搜,否定了上面的算法后，似乎只有一条出路了：,确定算法,(2),每一个动作（,x,i,，,y,i,),用一个平面向量,P,i,表示，,P,i,=(,x,i,y,i,),要判断的就是对于任意的,x,y,，,是否都存在着一个非负整数序列,c,，使得下面的等式成立：,确定了数学模型：,解方程,确定算法,(3),只要求当,(,x,y,)=(0,1),(0,-1),(1,0),(-1,0),的情况,由于对称性，只需要求,(,x,y,)=(0,1),的情况,所以最终目标：,方程,放大目标,方程只有一个,但是，未知数很多,如果有解，解的个数应该比较多，有可能有无限个。,尝试着构造解。,构造出现了两个困难,:,A,、方程右边,y,值要等于,1,。,B,、方程左边系数要非负。,所以先解决困难,A,太重了,先求出问题的整数解,!,两个一起搬,先搬,A,再搬,B,求,整,数,解,放大目标,求整数解,(2),目标仍然很复杂,再退一步,先考虑,n,=2,的情况,假设,x,1,y,1,x,2,y,2,0,那么，两个向量能够到达纵坐标的哪些地方？,放大目标,求整数解,(3),c,1,x,1,+,c,2,x,2,=0,c,1,=Lcm(,x,1,x,2,)/,x,1,;,c,2,=-Lcm(,x,1,x,2,)/,x,2,W,=,c,1,P,1,+,c,2,P,2,可以由,P,1,、,P,2,完成。,任意整数,k,kW,都可以由,P,1,P,2,来完成。,P,2,=(,x,2,y,2,),P,1,=(,x,1,y,1,),c,1,x,1,-c,2,x,2,c,1,P,1,+c,2,P,2,放大目标,求整数解,(4),定义,S,i,j,：,y,S,i,j,当且仅当,存在整数,k,1,k,2,满足,k,1,P,i,+,k,2,P,j,=(0,y,),2,3,4,5,1,2,k|k,Z,6,k|k,Z,5,k|k,Z,2,k|k,Z,2,0,k|k,Z,4,k|k,Z,3,3,k|k,Z,6,k|k,Z,4,9,k|k,Z,j,i,S,i,j,n,=5,P,1,=(2,4),P,2,=(2,2),P,3,=(-3,-3),P,4,=(4,3),P,5,=(1,3),P,1,-,P,2,=(0,2),3P,1,+2,P,3,=(0,6),2,P,1,-,P,4,=(0,5),-P,1,+2,P,5,=(0,2),放大目标,求整数解,(5),定义,S,：,a,、如果存在,i,j,使得,y,S,i,j,，那么,y,S,;,b,、如果,y,1,S,y,2,S,，,y,=,k,1,y,1,+,k,2,y,2,，,(,k,1,Z,k,2,Z,),那么,y,S,。,c,、其余的数都不属于,S,。,由模的知识不难得出，,S,集合也是形如,ky,|,k,Z,的形式。,S,是用所有的,S,i,j,通过加减运算得出的闭形式。,放大目标,求整数解,(6),如果,1,属于集合,S,，那么，方程,就有整数解了！,S,中最小的正数,(,上面的,y,),就是所有,S,i,j,中的最小正数的最大公约数！,找到方程,有整数解的充分条件了！,上面的构造只是一个充分条件。,它是不是必要的？,问题：,可以证明是必要的。,(0,6),(0,-5),(0,54),(0,-54),放大目标,求整数解,(7),结论,：,方程,一定可以拆成若干个多项式之和。其中任意一个多项式最多包含两项，并且多项式的向量和的,x,为,0,。,3,(2,4),-,13,(2,2)+,9,(-3,-3)+,11,(4,3)+,3,(1,3)=(0,1),3,(2,4),-3,(2,2)+,-10,(2,2)+,5,(4,3)+,9,(-3,-3)+,27,(1,3)+,6,(4,3),-24,(1,3)=(0,1),+,+,+,=(0,1),放大目标,求整数解,(8),n,=2,时显然成立；,若,n,1),g,i,|,x,i,g,|(,c,1,x,1,),设,g,=gcd(,g,2,g,3,g,k,),所有,x,i,的最大公约数是,1,g,与,x,1,互质,存在整数序列,d,2,d,3,d,k,，使得,v,i,=,d,i,g,i,，,u,i,=-,v,i,x,1,/,x,i,=-,d,i,g,i,x,1,/,x,i,=-,d,i,Lcm(,x,1,x,i,)/,x,i,g|g,i,g,|,c,1,求出了满足条件的,u,v,，,因此就可以从方程,的左边拿掉,k,-1,个向量，,v,i,x,1,+,u,i,x,i,(,其中，,1,i,0,；存在,i,，使得,x,i,0,；存在,i,，使得,y,i,=0),使得,k,1,P,i,+,k,2,P,j,是,Y,方向正半轴上的向量。,证明比较简单，只需要用几个不等式，证明如果没有这样的,P,i,，,P,j,，,k,1,，,k,2,，,就不可能到达,Y,轴正半轴。具体过程请参见我的论文。,求非负整数解,(7),同时考虑两个位置,：,(0,1),，,(0,-1),。,如果,T,中有一个正数，也有一个负数，那么超级马能够到达这两个位置。,(,结论,),如果要能够到达,(0,1),，,T,中就必须有一个正数；要能够到达,(0,-1),，就必须有一个负数。,(,结论,),在满足前面,3,个大,前提下，超级马能够到达,Y,坐标轴上的所有位置的充要条件就是,：,T,中至少有一个,正,数，至少有一个负数。,(,+,),算法,得到了问题的算法：,步骤,1,：,g,0;,For(,P,i,是竖直向量,)Do,g,gcd(,g,|,y,i,|);,For(,P,i,不是竖直向量,)Do Begin,For(,P,j,不是竖直向量,)Do Begin,t,gcd(|,x,i,|,|,x,j,|);,len,|,P,i,*,x,j,/,t,-,P,j,*,x,i,/,t,|;,g,gcd(,g,len,);,End For;,End For;,If,g,1 Then Begin,输出,(,NIE);Halt;End,If;,步骤,2,：,positive,false;,negative,false,;,For (,P,i,是竖直向量,)Do Begin,If,y,i,0 Then,positive,true,Else,negative,true,;,End For;,For(,P,i,不是竖直向量,)Do Begin,For(,P,j,不是竖直向量且,x,i,与,x,j,符号不相同,)Do Begin,W,=,P,i,*|,x,j,|+,P,j,*|,x,i,|;,If,W,是,Y,方向正向量,Then,positive,true,;,If,W,是,Y,方向负向量,Then,negative,true,End For,End For,If Not,positive,Or Not,negative,Then Begin,输出,(,NIE);halt,;End If;,步骤,3,：,交换每一个向量的,x,值与,y,值，重复作步骤,1,，步骤,2,；,输出,(TAK),算法的时间复杂度是,O(,n,2,),。,总结,(1),题目首先是要求方程的非负整数解，而方程求整数解比求非负整数解要简单。所以首先把目标放大成了求解整数解。求完整数解后，就站在了一个新的高度上，由整数解得出非负整数解变得简单。,在求解整数解和非负整数解的过程中，也不是直接得出一个有解的充分必要条件，而是首先构造出一个充分条件，再证明它的必要性。,总结,(2),转化目标,这体现了解题的一个过程：,由易入难；,由简单到复杂；,由浅入深,；,由特殊到一般。,解此题的关键：,谢谢,