资源描述：
《算法合集之《转化目标在解题中的应用》.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、转化目标在解题中的应用湖南省长沙市长郡中学栗师概述在解题时，总是觉得限制太多范围太窄关系错综复杂目标太远困难需要解决！减少限制放宽范围简化关系解题遇到困难转化目标解决某些题目，在算法设计中需要转化目标题目——超级马(1)在一个无限的棋盘上有一个超级马，它占据一个正方形单位格，可以完成各种移动动作。每一种移动动作由两个整数来描述——第一个数说明动作左右移动多少格(正数向右，负数向左)，第二个数说明动作上下移动多少格(正数向上，负数向下)。已知一个超级马能够完成的动作，要判断它是否能够到达棋盘上的所有位置。题目——超级马(2)SUP.IN252422-3-3431351-321414-22-2超级
2、马个数k(1<=k<=100)动作数n(1<=n<=100)每一个动作(xi,yi)，(-100<=xi,yi<=100)TAK表示超级马能够到达所有的位置NIE表示超级马不能够到达所有的位置SUP.OUTTAKNIE确定算法(1)广搜？数学方法TimeLimitExceeded!动态规划?在某种意义上等价于广搜否定了上面的算法后，似乎只有一条出路了：确定算法(2)每一个动作（xi，yi)用一个平面向量Pi表示，Pi=(xi,yi)要判断的就是对于任意的x,y，是否都存在着一个非负整数序列c，使得下面的等式成立：确定了数学模型：解方程确定算法(3)只要求当(x,y)=(0,1),(0,-1),
3、(1,0),(-1,0)的情况由于对称性，只需要求(x,y)=(0,1)的情况所以最终目标：………………方程①放大目标——方程只有一个但是，未知数很多如果有解，解的个数应该比较多，有可能有无限个。尝试着构造解。构造出现了两个困难:A、方程右边y值要等于1。B、方程左边系数要非负。所以先解决困难A太重了先求出问题的整数解!两个一起搬先搬A再搬B求整数解放大目标——求整数解(2)目标仍然很复杂再退一步先考虑n=2的情况假设x1,y1,x2,y2≠0那么，两个向量能够到达纵坐标的哪些地方？放大目标——求整数解(3)c1x1+c2x2=0c1=Lcm(x1,x2)/x1;c2=-Lcm(x1,x2)/
4、x2W=c1P1+c2P2可以由P1、P2完成。任意整数k,kW都可以由P1,P2来完成。P2=(x2,y2)P1=(x1,y1)c1x1-c2x2c1P1+c2P2放大目标——求整数解(4)定义Si,j：y∈Si,j当且仅当存在整数k1,k2满足k1Pi+k2Pj=(0,y)23451{2k
5、k∈Z}{6k
6、k∈Z}{5k
7、k∈Z}{2k
8、k∈Z}2{0}{k
9、k∈Z}{4k
10、k∈Z}3{3k
11、k∈Z}{6k
12、k∈Z}4{9k
13、k∈Z}jiSi,jn=5P1=(2,4)P2=(2,2)P3=(-3,-3)P4=(4,3)P5=(1,3)P1-P2=(0,2)3P1+2P3=(0,6)2P1-
14、P4=(0,5)-P1+2P5=(0,2)放大目标——求整数解(5)定义S：a、如果存在i,j使得y∈Si,j，那么y∈S;b、如果y1∈S,y2∈S，y=k1y1+k2y2，(k1∈Z,k2∈Z),那么y∈S。c、其余的数都不属于S。由模的知识不难得出，S集合也是形如{ky
15、k∈Z}的形式。S是用所有的Si,j通过加减运算得出的闭形式。放大目标——求整数解(6)如果1属于集合S，那么，方程①就有整数解了！S中最小的正数(上面的y)就是所有Si,j中的最小正数的最大公约数！找到方程①有整数解的充分条件了！上面的构造只是一个充分条件。它是不是必要的？问题：可以证明是必要的。(0,6)(0,-5)
16、(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<=k-1时成立；当n=k时，如果找到这样的u,v，满足：用归纳法证明结论①：可以假设所有的x的最大公约数是1，否则，只要约掉公约数就可以
17、了。选出k-1个和为0的多项式uixi+vix1，去掉x1,就剩下k-1个x了。放大目标——求整数解(9)设gi=Lcm(xi,x1)/x1(i>1)gi
18、xig
19、(c1x1)设g=gcd(g2,g3……gk)所有xi的最大公约数是1g与x1互质存在整数序列d2,d3……dk，使得vi=digi，ui=-vix1/xi=-digix1/xi=-diLcm(x1,xi)/xig
20、gig
21、c1求出了满
