枚举与搜索PPT学习教案

1、会计学1枚举与搜索枚举与搜索第1页/共65页注意：注意：1. 加号与等号各自需要两根火柴棍加号与等号各自需要两根火柴棍2. 如果如果AB，则，则A+B=C与与B+A=C视为不同的等式（视为不同的等式（A、B、C=0）3. n根火柴棍必须全部用上根火柴棍必须全部用上第2页/共65页第3页/共65页第4页/共65页第5页/共65页第6页/共65页第7页/共65页第8页/共65页第9页/共65页现有一个棱长为现有一个棱长为n的立方体，可以分成的立方体，可以分成n3个个1*1*1的的单位立方体。每个单位立方体都有一个整数值。单位立方体。每个单位立方体都有一个整数值。n3个单位立方体的数和不会超过个单位

2、立方体的数和不会超过longint范围。现在要范围。现在要求在这个立方体找到一个包含完整单位立方体的长求在这个立方体找到一个包含完整单位立方体的长方体，使得该长方体内所有单位立方体的数和最大。方体，使得该长方体内所有单位立方体的数和最大。输入：输入： n(1n20)；n个个n*n的数字矩阵，每个数的数字矩阵，每个数字矩阵代表一层，每个数字代表一个单位立方体的字矩阵代表一层，每个数字代表一个单位立方体的整数值，整数值，-999单位立方体的整数值单位立方体的整数值999999输出：输出：长方体的数和长方体的数和第10页/共65页第11页/共65页第12页/共65页3 3、提取恰当的信息、提取恰当的

3、信息上述考察实际上求出上述考察实际上求出z z轴坐标为轴坐标为z z2 2的平面中矩形（的平面中矩形（x1，y1，x2，y2）的数和。我们将这个数和记为）的数和。我们将这个数和记为value(a) value(a) value(A)=value(ABCD)+value(B)-value(BC)- value(A)=value(ABCD)+value(B)-value(BC)-value(BD)value(BD)这就启发我们用另一种方法表示立方体的信息：设这就启发我们用另一种方法表示立方体的信息：设recxrecx，y y，zz表示表示z z轴坐标为轴坐标为z z的水平面中矩形（的水平面中矩形（

4、1 1，1，x，y）的数和。）的数和。 z z轴坐标为轴坐标为z z的水平面中的水平面中左上角为（左上角为（x1，y1）、右下）、右下角为（角为（x2，y2）的矩阵的数和为）的矩阵的数和为recxrecx2 2，y y2 2，z+ z+ recxrecx1 1，y y1 1，z-recxz-recx2 2，y y1 1，z-recxz-recx1 1，y y2 2，zz 第13页/共65页RecRec数组可以在输入数据的同时计算数组可以在输入数据的同时计算fillchar(recfillchar(rec，size(rec)size(rec)，0)0)；recrec数组初始化数组初始化 forf

5、or z1 to n do 逐层输入信息逐层输入信息 forfor x1 to n do 逐行输入逐行输入z平面的信息平面的信息forfor y1 to n do 逐列输入逐列输入z平面上平面上x行的信息行的信息beginbegin read(mapx read(mapx，y y，z)z)； 输入输入z z平面上（平面上（x,yx,y）中的数）中的数 if (x=1)and(y=1) if (x=1)and(y=1) 计算计算z z平面上以（平面上以（1 1，1 1）为左上角、（）为左上角、（x,yx,y）为右下角的矩形的数和）为右下角的矩形的数和 then rec1 then rec1，1

6、1，zzmap1map1，1 1，zz else if y=1 then recx else if y=1 then recx，y y，zzrecx-1recx-1，n n，z+mapxz+mapx，y y，zz else recx else recx，y y，zrecxzrecx，y-1y-1，z+mapxz+mapx，y y，zz； endend；forfor 这样，考察过程就可以改为这样，考察过程就可以改为 sumsum+recxsumsum+recx2 2，y y2 2，z z2 2+recx+recx1 1，y y1 1，z z2 2-recx-recx2 2，y y1 1，z z2

7、 2-recx-recx1 1，y y2 2，z z2 2 ； if sumbest then bestif sumbest then bestsumsum；时间复杂度降为时间复杂度降为O O（n n6 6）。）。第14页/共65页如果长方体如果长方体a的数和是负数，则长方体的数和是负数，则长方体a的计算的计算结果废弃，考察长方体结果废弃，考察长方体b-a。因为长方体。因为长方体b的数的数和和=长方体长方体b-a的数和的数和+长方体长方体a的数和，由于长的数和，由于长方体方体a的数和为负，长方体的数和为负，长方体b-a的数和一定大于的数和一定大于等于长方体等于长方体b的数和。由此可见，在累计长

8、方体的数和。由此可见，在累计长方体数和的时候，只要由上而下地枚举长方体下底数和的时候，只要由上而下地枚举长方体下底面的面的z轴坐标即可。设轴坐标即可。设total(z)以以z轴坐标为轴坐标为z的平面为下底面的长的平面为下底面的长方体的最大数和方体的最大数和0, 1, 1, 1, 1,)1(, 0max(00)(21121122zzyxreczyxreczyxreczyxrecztotalzztotal第15页/共65页第16页/共65页第17页/共65页第18页/共65页第19页/共65页第20页/共65页第21页/共65页第22页/共65页第23页/共65页Procedure Try( i:

9、 integer)；var j:integer;begin if i=n+1 then print； for j:=1 to n do if aj and bi+j and ci-j then begin ai:=j; aj:=false; bi+j:=false; ci-j:=false; Try (i+1) aj:=true; bi+j:= true; ci-j:= true; end;end;第24页/共65页搜索的方向第25页/共65页第26页/共65页第27页/共65页第28页/共65页第29页/共65页第30页/共65页第31页/共65页第32页/共65页第33页/共65页第34页

10、/共65页2 2、粗略利用信息、粗略利用信息 若已经确定了前若已经确定了前k k个数，并且下一个关系符号是小于号，这时所个数，并且下一个关系符号是小于号，这时所能产生的序关系数就是剩下的能产生的序关系数就是剩下的n-kn-k个数所能产生的序关系数。个数所能产生的序关系数。设设i i个数共有个数共有FiFi种不同的序关系，那么，由上面的讨论可知，在种不同的序关系，那么，由上面的讨论可知，在算法算法1 1中，调用一次中，调用一次Count(Step+1Count(Step+1，1 1，Can-i)Can-i)之后，之后，TotalTotal的增的增量应该是量应该是Fn-StepFn-Step。这个

11、值可以在第一次调用。这个值可以在第一次调用Count(Step+1Count(Step+1，1 1，Can-i)Can-i)时求出。而一旦知道了时求出。而一旦知道了Fn-StepFn-Step的值，就可以用的值，就可以用TotalTotalTotal+Fn-Step Total+Fn-Step 代替调用代替调用Count(Step+1Count(Step+1，1 1，Can-i)Can-i) 第35页/共65页procedure Count(Stepprocedure Count(Step，FirstFirst，Can)Can)； StepStep，FirstFirst，CanCan的含义同算

12、法的含义同算法11 begin begin if Step=n then begin 若确定了最后一个关系符号，若确定了最后一个关系符号，则输出统计结果则输出统计结果 for i for iFirst to n do if i in Can then Inc(Total)First to n do if i in Can then Inc(Total)；Exit Exit 回溯回溯 end end；thenthen for iFirst to n do for iFirst to n do 枚举当前的大写字母枚举当前的大写字母 if i in Can if i in Can 序号为序号为i i

13、的大写字母可以使用的大写字母可以使用 then beginthen begin Count(Step+1 Count(Step+1，i+1i+1，Can-i)Can-i)； 添等于号添等于号 if Fn-Step=-1 if Fn-Step=-1 then begin then begin 第一次调用第一次调用 Fn-Step Fn-Step TotalTotal；Count(Step+1Count(Step+1，1 1，Can-i)Can-i)； 添小于号添小于号 Fn-Step Fn-Step Total-Fn-Step Fn-Step=TotalTotal-Fn-Step Fn-Step

14、=Total的增量的增量 end thenend thenelse TotalTotal+Fn-Step Fn-Step已经求出已经求出 endthen end；count该算法实质上就是自顶向下记忆化方式的搜索，它的时间复杂度为该算法实质上就是自顶向下记忆化方式的搜索，它的时间复杂度为W(2W(2n n) )。 第36页/共65页3 3、充分利用信息、充分利用信息在搜索的过程中，如果确定在第在搜索的过程中，如果确定在第k个大写字母之后添加第一个小于号，则个大写字母之后添加第一个小于号，则可得到下面两条信息：可得到下面两条信息：第一条信息：前第一条信息：前k个大写字母都是用等号连接的。前半部分

15、将产生的序关个大写字母都是用等号连接的。前半部分将产生的序关系数，就是系数，就是n个物体中取个物体中取k个的组合数个的组合数第二条信息：在此基础上继续搜索，将产生第二条信息：在此基础上继续搜索，将产生Fn-k个序关系表达式。个序关系表达式。这样，我们可以得到这样，我们可以得到Fn 的递推关系式：的递推关系式：采用上述公式计算采用上述公式计算Fn的算法记为算法的算法记为算法3，它的时间复杂度是，它的时间复杂度是W(n2)。knC101FknFCnFnkkn，其中第37页/共65页varvar Total Total ：CompComp； 答案答案 F F ：array0.maxn of Comp

16、array0.maxn of Comp；FiFi为为i i个数的序关系表达式个数个数的序关系表达式个数 i i，j j ：IntegerInteger； x x ：CompComp； beginbegin FillChar(F FillChar(F，Sizeof(F)Sizeof(F)，0)0)；FF初始化初始化 F0 1 F0 1； for i1 to n do beginfor i1 to n do begin递推递推F F数组数组 Fi 0 Fi 0；x1x1； for j1 to i do begin for j1 to i do begin 计算计算FiFi xx xx* *(i-j

17、+1)/j(i-j+1)/j；Fi Fi+xFi Fi+x* *Fi-jFi-j Endfor Endfor end end；forfor writeln(Fn) writeln(Fn)； 输出结果输出结果 end end；mainmain第38页/共65页第39页/共65页一个反例第40页/共65页第41页/共65页第42页/共65页第43页/共65页第44页/共65页DXCBCNXXBACNXXDDCNXAC332211* BADC+ CBDA DCCC 枚举每位是否进位，复杂度是枚举每位是否进位，复杂度是O(2n), (因为首位不可能进位因为首位不可能进位，无须枚举，无须枚举)。然后，用

18、高斯消元法来解方程，复杂度是。然后，用高斯消元法来解方程，复杂度是O(n3) 。总复杂度是。总复杂度是O(2n*n3) 。第45页/共65页第46页/共65页第47页/共65页第48页/共65页第49页/共65页第50页/共65页第51页/共65页第52页/共65页第53页/共65页第54页/共65页第55页/共65页第56页/共65页Amazing Robots: IOI2003已知条件： 迷宫 i（i=1,2） （每个不会大于20*20） 守卫 Gi（0=Gi=10） （守卫循环移动进行执勤） （守卫巡逻的方格数（2.4）求： 两个机器人都离开迷宫所用的最少指令数目 和离开制指令序列（10000 步以内）。第57页/共65页每一步可以发出的命令可以是N, E, S, W中的一种，有4种选择。对每一步具体发出哪个命令，直接搜索。假设最后结果是T。（也就是最少出宫时间）时间复杂度是O(4T)这种方法时间复杂度太高，绝对不可行!第58页/共65页5*4和4*4的迷宫第一个机器人的位置是(2,2)第二个机器人的位置是(3,2)当前时间是0。状态(2,2),(3,2),0)状态表示：状态表示： （第一个机器人