• 1. 搜索教案朱全民
  • 2. 搜索的本质一、两种题型: 1.简明的数学模型揭示问题本质。对于这一类试题,我们 尽量用解析法求解。 2.对给定的问题建立数学模型,或即使有一定的数学模型,但采用数学方法解决有一定困难。对于这一类试题,我们只好用模拟或搜索求解。 二、搜索的本质: 搜索的本质就是逐步试探,在试探过程中找到问题的解。三、搜索问题考察的范围 1.算法的实现能力 2.优化算法的能力
  • 3. 简单回溯法N皇后问题 背包问题 寻找国都名 ……
  • 4. N皇后问题在N*N的棋盘上放置N个皇后而彼此不受攻击(即在棋盘的任一行,任一列和任一对角线上不能放置2个皇后),编程求解所有的摆放方法。 八皇后的两组解
  • 5. 基本思想由于皇后的摆放位置不能通过某种公式来确定,因此对于每个皇后的摆放位置都要进行试探和纠正,这就是“回溯”的思想。 在N个皇后未放置完成前,摆放第i个皇后和第i+1个皇后的试探方法是相同的,因此完全可以采用递归的方法来处理。
  • 6. 算法基本框架Procedure Try(I:integer); {搜索第I行皇后的位置} var j:integer; begin if I=n+1 then 输出方案; for j:=1 to n do if 皇后能放在第I行第J列的位置 then begin 放置第I个皇后; 对放置皇后的位置进行标记; Try(I+1) 对放置皇后的位置释放标记; end; end;
  • 7. 细节处理怎样判断某列放置了皇后 A:array [1..MaxN] of Boolean; {竖线被控制标记} 怎样判断某对角线上放置了皇后 B:array [2..MaxN * 2] of Boolean; {左上到右下斜线被控制标记} C:array [1–MaxN..MaxN–1] of Boolean; {左下到右上斜线被控制标记}
  • 8. 0,1背包问题已知一个容量大小为M重量的背包和N种物品,每种物品的重量为Wi。若将物品放入背包将得到Pi的效益,求怎样选取物品将得到效益最大
  • 9. 算法分析本题可以用递归求解:设当前有N个物品,容量为M;因为这些物品要么选,要么不选,我们假设选的第一个物品编号为I(1~I-1号物品不选),问题又可以转化为有N-I个物品(即第I+1~N号物品),容量为M-Wi的子问题……如此反复下去,然后在所有可行解中选一个效益最大的便可。 另外,为了优化程序,我们定义一个函数如下: F[I]表示选第I~N个物品能得到的总效益。不难推出: F[N]=Pn F[I]=F[I+1]+Pi (I=1…N-1) 假设当前已选到第I号物品,如果当前搜索的效益值+F[I+1]的值仍然比当前的最优值小,则没有必要继续搜索下去。
  • 10. 算法框架Procedure Search(I:Integer; J:Byte); {递归求解} Var K :Byte; Begin If Now+F[J]<=Ans Then Exit; {如果没有必要搜索下去} If Now>Ans Then Begin {修改最优解} Ans:=Now; Out:=Ou; End; For K:=J To N Do {选取物品} If W[K]<=I Then Begin Now:=Now+P[K]; Ou[K]:=True; Search(I-W[K],K+1); Now:=Now-P[K]; Ou[K]:=False; End; End;
  • 11. 给出一个矩阵及一些国都名: o k d u b l i n dublin a l p g o c e v tokyo r a s m u s m b london o s l o n d o n rome y i b l g l r c bonn k r z u r i c h paris o a i b x m u z oslo t p q g l a m v lima 要求从这个矩阵中找出这些国都名,并输出它们的起始位置及方向。 寻找国都名 搜索的方向
  • 12. 算法思想将字符矩阵读入到二维数组,然后对每一个国都名进行搜索,首先需要在矩阵中找到国都名的第一个字符,然后沿八个方向进行搜索。直到找到国都名为止。若在矩阵中没有找到,则输出相应的信息。 在搜索过程时,类似八皇后问题,建立一个标志数组,标识已经搜索过的方向,在对八个方向搜索时,可以建立一个方向数组,使得程序更加简洁明了 Const Fx : Array[1..8,1..2] Of Shortint {定义八个方向} =((0,1),(0,-1),(1,0),(-1,0),(1,-1),(-1,1),(1,1),(-1,-1));
  • 13. Procedure Work(T,X,Y:Integer); {搜索路径,T为国都名的字符位置,X,Y为当前搜索的坐标} Var I : Integer; Begin If T=Length(S)+1 Then begin {搜索完,打印输出} Out; exit end; For I:=1 To 8 Do {八个方向进行搜索} Begin X:=X+Fx[I,1]; Y:=Y+Fx[I,2]; {坐标变化} If (A[X,Y]=S[T])And(B[X,Y]) Then Begin W:=W+Chr(I+48); {记录路径} B[X,Y]:=False; {设置已经搜索} Work(T+1,X,Y); {继续搜索下一个} Delete(W,Length(W),1);{恢复原路径} B[X,Y]:=True; {恢复标志} End; X:=X-Fx[I,1]; Y:=Y-Fx[I,2]; {返回后,坐标恢复} End; End;
  • 14. 图搜索策略综合数据库 产生式规则 状态空间图与节点的耗散值 搜索算法的框架
  • 15. 八数码问题 在3*3组成的九宫格棋盘上,摆有八个将牌,每一个将牌都刻有1—8中的某一个数码。棋盘中留有一个空格,允许其周围的某一个将牌向空格中移动,如右图所示。这样通过移动将牌就可以不断改变的布局结构,给出一个初始布局(称初始状态)和一个目标布局(称目标状态),问如何移动将牌,才能实现从初始状态到目标状态的转换。
  • 16. 综合数据库{Pxy},其中1<=x,y<=3,Pxy∈{0,1,2,3,4,5,6,7,8},且Pxy互不相等 用Pascal语言描述如下: type tState = array[1..3,1..3]of byte; var S ,G: tState; {S为初始状态,G为目标状态} M : array[0.. 181440] of tState; {综合数据库}
  • 17. 产生式规则if 条件 then 规则; 设Pxy表示将牌第x行第y列的数码,m,n表示数码空格所在的行列值,记Pm,n=0,则可以得到如下四条规则: ① if n -1>=1 then begin Pm, n:=Pm,n -1­ ; Pm,n -1­ ­:=0 end; ② if m - 1>=1 then begin Pm, n:=Pm-1, n ; Pm-1, n :=0 end; ③ if n + 1<=3 then begin Pm, n:=Pm, n+1; Pm, n+1:=0 end; ④ if m + 1<=3 then begin Pm, n:=Pm+1­,n; Pm+1­, n:=0 end;
  • 18. 控制策略 PROCEDURE Production-System; DATA初始化数据库 Repeat  在规则集中选择某一条可作用于DATA的规则R   DATAR作用于DATA后得到的结果      Until DATA满足结束条件
  • 19. 宽度优先搜索PROCEDURE BFS-SEARCH;(算法3) 1.       G:=G0; 2.       Open:=(Source) ; 3.       Closed:=nil; 4.       Repeat 5.       IF OPEN=nil then Exit(Fail); 6.       n:=FIRST(OPEN);Remove(n,Open); 7.       Add(n,Closed); 8.       If n=Goal then Exit(Success); 9.       mi:=Expand(n); 10.  对mi,舍去在G中已经出现的节点; 11.  将图中未出现的mi加入到Open表的表尾 12.    Add(mi,G); 13.    Until false;  
  • 20. 八数码问题扩展过程
  • 21. 八数码搜索的主框架1.          List[1]=source;Closed:=0;Open:=1; {加入初始节点,List为扩展节点的表} 2.          Repeat 3.          Closed:=Closed+1; N:=List[Closed]; {取出Closed对应的节点} 4.          For x:=1 to 4 do [ 5.          New:=Move(N,4); {对N节点使用第x条规则,得到New} 6.          If not_Appear(New,List) then [ {如果New没有在List中出现} 7.          Open:=Open+1;List[Open]:=New;{加入新节点到Open} 8.          List[Open].Father:=Closed; {修改指针} 9.          If List[Open]=Goal then GetOut; 10.   ]; 11.   ] 12.   Until Closed
  • 22. 聪明的打字员(NOI2001第一试第三题) 阿兰是某机密部门的打字员,她现在接到一个任务:需要在一天之内输入几百个长度固定为6的密码。当然,她希望输入的过程中敲击键盘的总次数越少越好。 不幸的是,出于保密的需要,该部门用于输入密码的键盘是特殊设计的,键盘上没有数字键,而只有以下六个键:Swap0, Swap1, Up, Down, Left, Right,为了说明这6个键的作用,我们先定义录入区的6个位置的编号,从左至右依次为1,2,3,4,5,6。下面列出每个键的作用: Swap0:按Swap0,光标位置不变,将光标所在位置的数字与录入区的1号位置的数字(左起第一个数字)交换。如果光标已经处在录入区的1号位置,则按Swap0键之后,录入区的数字不变; Swap1:按Swap1,光标位置不变,将光标所在位置的数字与录入区的6号位置的数字(左起第六个数字)交换。如果光标已经处在录入区的6号位置,则按Swap1键之后,录入区的数字不变; Up:按Up,光标位置不变,将光标所在位置的数字加1(除非该数字是9)。例如,如果光标所在位置的数字为2,按Up之后,该处的数字变为3;如果该处数字为9,则按Up之后,数字不变,光标位置也不变; Down:按Down,光标位置不变,将光标所在位置的数字减1(除非该数字是0),如果该处数字为0,则按Down之后,数字不变,光标位置也不变; Left:按Left,光标左移一个位置,如果光标已经在录入区的1号位置(左起第一个位置)上,则光标不动; Right:按Right,光标右移一个位置,如果光标已经在录入区的6号位置(左起第六个位置)上,则光标不动。 当然,为了使这样的键盘发挥作用,每次录入密码之前,录入区总会随机出现一个长度为6的初始密码,而且光标固定出现在1号位置上。当巧妙地使用上述六个特殊键之后,可以得到目标密码,这时光标允许停在任何一个位置。 现在,阿兰需要你的帮助,编写一个程序,求出录入一个密码需要的最少的击键次数。
  • 23. 产生式规则设当前状态为(S,index),下一个状态为(S’,index’) ① Swap0: if index<>1 then [ S’:=S;S’[1]:=S[index];S’[index]:=S[1];Index’:=index;] ② Swap1: if index<>6 then [ S’:=S;S’[6]:=S[index];S’[index]:=S[6];Index’:=index;] ③ Up: if S[index]<>9 then [ S’:=S;S’[index]:=S’[index]+1;Index’:=index;] ④ Down: if S[index]<>0 then [ S’:=S;S’[index]:=S’[index]-1;Index’:=index; ] ⑤ Left: if index<>0 then [ S’:=S; Index’:=index-1;] ⑥ Right: if index<>6 then [ S’:=S; Index’:=index+1;]
  • 24. 深度优先搜索递归算法伪代码: procedure DFS_ recursive(N); 1.       if N=target then 更新当前最优值并保存路径; 2.       for r:=1 to 规则数 do [ 3.       New:=Expand(N,r) 4.       if 值节点New符合条件 then [ 5.       产生的子节点New压入栈; 6.       DFS_recursive(i+1); 7.       栈顶元素出栈; 8.       ] 9.       ]   program DFS; 1.        初始化; 2.        DFS_recursive(N);
  • 25. 深度优先搜索的非递归形式program DFS; 1.       dep:=0; 2.       Repeat 3.       dep:=dep+1; 4.       j:=0;brk:=false; 5.       Repeat 6.       j:=j+1; 7.       New=Expand(Track[dep],j); 8.       if New 符合条件 then [ 9.       产生子节点New并将其压栈; 10.   If 子节点New=target then 更新最优值并出栈 11.   else brk:=true; 12.   ] 13.   else if j>=规则数 then Backtracking 14.   else brk:=false; 15.   Until brk=true 16.   Until dep=0;
  • 26. 条件1:V = nπ H = m 层 形状:每层都是一个圆柱体。 条件2: 设从下往上数第i(1<=i<=m)层蛋糕是半径为Ri, 高度为Hi的圆柱。 当iRi+1且Hi>Hi+1。 条件3: 表面积Q最小,令Q= Sπ 问题: 给出的n和m, 找出蛋糕的制作方案(适当的Ri和Hi的值),使S最小。 (除Q外,以上所有数据皆为正整数) 输入 n (n<=10000), m (m<=20) 输出 S(若无解则S=0)。圆柱公式 V=πR2H S侧=2πRH S底=πR2生日蛋糕
  • 27. 解析法?
  • 28. 转变思路,搜索?数据库 用( i , Ri , Hi , Vi , Si )表示第i层蛋糕的一个状态。其中Ri ,Hi分别为第i层蛋糕的半径和高,Vi , Si分别表示做完第i层蛋糕后剩下的蛋糕体积和当前蛋糕的表面积。可见, 初始状态:(1,R1,H1,n-R1*R1*H1,R1*R1+2*R1*H1) 目标状态:(m,Rm,Hm,0,Sm) 于是,我们的目标是找到一条从初始状态到任意目标状态的路径,并且Sm最小. 扩展的规则 ( i , Ri , Hi , Vi , Si )  ( i+1,Ri+1,Hi+1,Vi+1,Si+1) 满足: (1) Ri > Ri+1 (2) Hi > Hi+1 (3) Vi+1 = Vi - Ri+1* Ri+1* Hi+1 (4) Si+1 = Si + 2 * Ri+1* Hi+1
  • 29. 确定第一层蛋糕的大小 根据上一层蛋糕的大小确定下一层蛋糕该怎么做 看是否符合条件 1)是否做到了m层 2)是否最终体积为0 3)是否当前面积最小 若上述条件成立,则保留当前最优值,否则继续做下一层蛋糕,若重做蛋糕 基本算法
  • 30. Search (i, Ri , Hi , Si , Vi) {对每层蛋糕进行搜索} if (i=m) and (Vi =0) then 更新最优值 else for Ri + 1Ri -1 downto i for Hi + 1Hi -1 downto i [ Si + 1Si + 2 * Ri + 1* Hi + 1 Vi + 1Vi - Ri + 1* Ri + 1* Hi + 1 Search ( i+1, Ri + 1, Hi + 1, Si + 1,Vi + 1) ] Problem-Cake {枚举所有的初始状态 ----- 第一层蛋糕的大小} for R1m to sqrt ( n ) do /*假设 H1=1,只做一层蛋糕 */ for H1n div (R1*R1) downto m do [ S1=2 * R1* H1+ R1* R1 V1=n - R1* R1 * H1 Search (1, R1, H1, S1, V1) ]
  • 31. 优化??(1)因为知道余下的蛋糕体积,因此可以估算一下余下侧面积, 这样我们可以就加入如下剪枝条件: if 当前的表面积 + 余下的側面积 > 当前最优值 then exit 设已经做了i层蛋糕,则还需做m-i层, Si’:为第i层蛋糕的侧面积, FSi:余下的侧面积,怎么求FSi ? 因为: 2Vi= 2Ri+1 * Ri+1 * Hi+1 + ...+ 2Rm * Rm * Hm = Ri+1 * Si+!’ + ...+ Rm * Sm’ ≤ Ri+1 * (Si+1’+ ...+ Sm’) = Ri+1 * FSi 所以: FSi ≥ 2Vi / Ri+1 因此剪枝条件为: if Si-1 + 2 * Vi-1 / Ri >当前最优值 then exit
  • 32. 优化??(2)如果剩下的蛋糕材料太少,不能保证做到m层,那么没有必要继续往下做了,设, 最m层半径和高都为1,Rm=Hm=1 第m-1层半径和高都为2,Rm-1=Hm-1=2 ………… 第 i +1层半径和高都为i, Ri = Hi = m – i 这样, 余下的m-i层的最小体积为 因此,剪枝条件为, if Vi< MINi then exit
  • 33. (3)如果剩下的蛋糕材料太多,以最大的方式做完m层, 仍有材料剩余,那么没有必要继续往下做了,设, 第i+1层半径和高分别为,Ri+1 = Ri – 1 , Hi+1 = Hi –1 第i+2层半径和高分别为,Ri+2 = Ri – 2 , Hi+2 = Hi –2   ………… 第 m层半径和高分别为,Ri+m = Ri –m ,Hi+m= Hi –m 这样, 余下的m-i层的最大体积为优化??因此,剪枝条件为, if Vi > MAXi,R,H then exit
  • 34. 计算MINi for i1 to n do [ S S + i * i * i; MINm-i  S ] 计算MAXi,R,H for R1 to sqrt(n) do for H1 to n div (R*R) do [ S 0; for im downto 1 do [ S S +(R-i)*(R-i)*(H-i); MAXi,R,H  S ] ] 初始化
  • 35. Search (i, Ri , Hi , Si , Vi) {对每层蛋糕进行搜索} if Si + 2 * Vi / Ri >当前最优值 then exit; {剪枝1} if Vi < MINi then exit; {剪枝2} if Vi > MAXi then exit; {剪枝3} if i
  • 36. 小节可行性剪枝 剪枝2:if Vi< MINi then exit剪枝3:if Vi > MAXi,R,H then exit最优化剪枝 剪枝1: if Si-1 + 2 * Vi-1 / Ri >当前最优值 then exit剪枝原则 正确、高效
  • 37. 深度搜索消耗时间 ≈ 每个节点操作系数 × 节点个数 优化 1)减少节点个数——这就是剪枝优化; 2)减少每个节点的操作系数——即程序操作量。
  • 38. 搜索对象的选取------汽车调度问题
  • 39. 0143142551321线路一线路二线路三0351314142125间隔为14间隔为11间隔为8汽车到站情况示例图:同一条线路上的公共汽车以相同的时间间隔到站 时间单位用“分”表示,从0 到59 。 每条公共汽车线路至少有两辆车到达本站。 公共汽车线路数K一定≤17,汽车数目N一定小于300。 来自不同线路的公共汽车可能在同一时刻到达本站。 不同公共汽车线路的车首次到站时间和到站的时间间隔都有可能相同。目标: 编一个调度表,公共汽车线路数目最少的情况下,使公共汽车到达本站的时刻满足输入数据的要求。
  • 40. 问题要素时间车辆路线题目要求的是车和线路的关系, 时间在其中起的是描述作用和条件制约作用, 搜索对象应该是车或线路这两个关键要素。
  • 41. 以车辆为搜索对象搜索策略是: 按到达的时间顺序,看车辆是属于哪条线路。 1)某车属于新线路的第一辆车 2)属于已有线路的第二辆车,此时确定了一条路线
  • 42. 以车辆为搜索对象扩展的搜索树
  • 43. 以线路为搜索对象搜索策略是: 枚举每条线路包含哪些车,确定该线路,搜索每层都要确定一条路线。 1)将未确定归属路线的到达时间最小的车固定为 新路线的第一辆车。 2)其后枚举这条路线的第二辆车,从而确定该路线。
  • 44. 以线路为搜索对象扩展的搜索树
  • 45. 策略比较 1)谁易于优化剪枝 ◇可行性剪枝(方法1好) ◇与已知最优解比较剪枝(方法1好) ◇排除重复剪枝(差不多) 2)谁的操作量小 ◇主递归程序的枚举循环 (17<60) ◇剪枝函数消耗时间(差不多)
  • 46. 两种搜索方法的实际比较
  • 47. 彩票问题 已知: 彩票上的数字:1,2,…,M 彩民的选择:A1,A2,…,An,其中Ai属于1,2,…,M 每人只能买一张彩票,每人彩票选择都不同 抽出两个自然数X和Y。 如果1/A1+2/A2+…+1/An= X/Y,则中奖(获取纪念品)。 输入: N,M,X,Y 输出: 所需准备的纪念品数量 1≤X, Y≤100,1≤N≤10,1≤M≤50。 输入数据保证输出结果不超过105。
  • 48. 分析:对于每个数,有选和不选两种可能性,显然可以建立如下模型: x1/1 + x2/2 + x3/3 + … + xm/m = X/Y 其中,xi=0或者1(1<=i<=m) x1+x2+x3+…+xm=n逐个搜索xi O(2m)
  • 49. x1/1 + x2/2 + x3/3 + … + xm/m = X/Y同时乘以m!*Y通分。 令Ti=m!*Y/i (1<=i<=m), T0=m!*X 则: T1x1+T2x2+T3x3+…+Tmxm=T0这就变成了一个01背包问题。 每个包裹的体积是Ti,箱子体积T0 从M个中选N个,填满箱子。 求方案数。如何优化??
  • 50. T1x1+T2x2+T3x3+…+Tmxm=T0 如何剪枝?f[i, T]表示为了满足T1x1+T2x2+…+Tmxm=T,最少要让多少个xi取1。 f[i, T]=min{f[i-1,T], f[i-1,T-Ti]+1}按照xm, xm-1, xm-2, …, x1的顺序搜索。 假设xp~xm都已经取定,令S=Tpxp+Tp+1xp+1+…+Tmxm,L=xp+xp+1+…+xm,如果f[p-1, T-S]+L>N,那么就可以回溯,不必继续搜索了。T~O(m!)。太大了! f数组开不下,时间上也不允许。
  • 51. 动态规划的思想,空间矛盾太大。抓住矛盾:解决空间问题! T太大了,可不可以想办法把它变小呢?同余T1x1+T2x2+T3x3+…+Tmxm=T0 f[i, T]表示为了满足T1x1+T2x2+…+Tmxm=T,至少要让多少个xi取1。 f[i, T]=min{f[i-1,T], f[i-1,T-Ti]+1}
  • 52. T1x1+T2x2+T3x3+…+Tmxm=T0 f[i, T]表示为了满足(T1x1+T2x2+…+TmXm)mod P=T,至少要让多少个xi取1。 f[i, T]=min{f[i-1,T], f[i-1,(T-Ti)mod P]+1}0<=TN,那么就可以回溯,不必继续搜索了。剪枝效果有所削弱 但是空间复杂度降到了O(mP),这里P可以任取。
  • 53. 取P为大质数。(比如<10000的最大质数) 剪枝效果相当的好。题目给定范围内的数据都在1s内解。 注意要使用高精度。总结 1、空间换时间。 2、抓住主要矛盾,用同余法解决空间矛盾。
  • 54. Amazing Robots: IOI2003已知条件: 迷宫 i(i=1,2) (每个不会大于20*20) 守卫 Gi(0<=Gi<=10) (守卫循环移动进行执勤) (守卫巡逻的方格数(2..4)) 求: 两个机器人都离开迷宫所用的最少指令数目 和离开指令序列(10000 步以内)。
  • 55. 每一步可以发出的命令可以是N, E, S, W中的一种,有4种选择。 对每一步具体发出哪个命令,直接搜索。 假设最后结果是T。(也就是最少出宫时间) 时间复杂度是O(4T)这种方法时间复杂度太高,绝对不可行!!
  • 56. 5*4和4*4的迷宫 第一个机器人的位置是(2,2) 第二个机器人的位置是(3,2) 当前时间是0。 状态((2,2),(3,2),0)状态表示: (第一个机器人位置,第二个机器认位置,时间)
  • 57. E((2,2),(3,2),0)((2,3),(3,3),1)时间已知,则所有Guard的位置可知。 Guard、Robot的位置均已知,所以状态可以转移
  • 58. 设出宫时间是T。 总共(n*n)*(n*n)*T种状态。 用BFS实现算法,HASH表判重。 总的复杂度是O(Tn4)。T<=10000, n<=20。 时间复杂度太大,不可承受!
  • 59. 0时刻1时刻2时刻3时刻0时刻和2时刻是一样的 1时刻和3时刻是一样的。 稍加分析:此Guard循环以2为周期循环。
  • 60. 状态转移,需要的信息是:Robot位置,Guard位置。 Position of Robot1, 2是的作用就是记录Robot位置。 Time的作用就是为了计算Guard的位置状态:(position of Robot1, position of Robot2, Time) Time<=10000,这是状态数过多的罪魁祸首!题目说:Guard巡逻经过的格子数只可能是2, 3, 4。 也就是说机器人巡逻周期只能是2, 4, 6。 [2, 4, 6]=12,所以第0时刻、12时刻、24时刻……Guard的状态完全相同。 12可以看作Guard的周期。Time只要记录当前是第几个周期。因为周期确定了,Guard的位置也完全确定了! 0<=Time<=11
  • 61. 状态数(n*n)*(n*n)*12=12n4。 用BFS算法,标志数组判重。 时间复杂度O(12n4)。n<=20 完全可以承受
  • 62. 邮票面值设计给定一个信封,最多只允许粘贴N张邮票,计算在给定K(N+k<=40) 种邮票的情况下(假定所有的邮票数量都足够),如何设计邮票的面值,能得到最大max ,使得1-max之间的每一个邮资值都能得到。 例如,N=3,K=2,如果面值分别为1分、4分,则在l分-6分之间的每一个邮资值都能得到(当然还有8分、9分和12分):如果面值分别为1分、3分,则在1分-7分之间的每一个邮资值都能得到。可以验证当N=3,K=2时,7分就是可以得到连续的邮资最大值,所以MAX=7,面值分别为l分、3分。 样例: INPUT N=3 k=2 OUTPUT 1 3 MAX=7
  • 63. 基本算法搜索的过程实质上是枚举K种邮票的面值,然后计算这K种邮票对应的MAX值。于是可以得到如下算法: 算法1 Procedure Search(m) 搜索第m种邮票的面值 1.       If m = K+1 Then [ 2.       If 当前方案更优 Then 保存当前方案; 3.       Exit; 4.       ] 5.       For I Am-1+1 to N*Am-1+1 do [ {N*Am-1+1肯定不能有前K中邮票构成} 6.       Am := I; 7.       Search(m+1); 8.       ]
  • 64. 优化(算法2)显然一定有面值为1的邮票。可以按递增的次序来搜索各种邮票的面值,关键在于确定每一层搜索的上界。设当前搜索到第m层,用不超过N-1张前m-1种邮票可以得到的MAX值记为MAX(m-1),则第m种邮票面值的上界是MAX(m-1)+1,否则邮资值MAX(m-1)+1就无法用这m种邮票贴出来了。 Procedure Search(m) 搜索第m种邮票的面值 1.       If m = K+1 Then [ 2.       If 当前方案更优 Then 保存当前方案; 3.       Exit; 4.       ] 5.       For I Am-1+1 to Max(M-1) do [ 6.       Am := I; 7.       Search(m+1); 8.       ]
  • 65. 埃及分数 在古埃及,人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。如:2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。 对于一个分数a/b,表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。 如: 19/45=1/3 + 1/12 + 1/180 19/45=1/3 + 1/15 + 1/45 19/45=1/3 + 1/18 + 1/30, 19/45=1/4 + 1/6 + 1/180 19/45=1/5 + 1/6 + 1/18. 最好的是最后一种,因为1/18比1/180,1/45,1/30,1/180都大。 给出a,b(0
  • 66. 分析1.节点类型 是一个K元组(a1,a2,...ak), 代表当前解中的分母a1,a2..ak. 2.节点扩展方法 按照a1
  • 67. 可变深度的搜索算法PROCEDURE Search(k,a,b); {决定第k个分母d[k]} 1.           If k=depth+1 then exit {depth需要进行枚举} 2.           else if (a =1) and (b>d[k-1]) then [  {a整除b的情况} 3.           d[k]:=b; 4.           if not found or (d[k]
  • 68. 智破连环阵(N0I2003)已知: M个武器(1  M 100) N棵炸弹(1  N 100) 炸弹爆炸半径(1 k 1000) 炸弹消灭半径范围以内的,处于攻击状态的武器 第i号武器被消灭后,第i+1号武器立即处于攻击状态 要求:用最少的炸弹消灭所有的武器
  • 69. 示例图
  • 70. 问题转化设炸弹的攻击的半径为r 第i号炸弹的坐标为(u[i],v[i]) 第j号武器的坐标为(x[j],y[j]) 则炸弹i能炸到炸弹j的基本条件是 (u[i]-x[j])2+(v[i]-y[j])2<=r2 我们可以枚举哪些炸弹是否爆炸,使得消灭所有的武器,时间复杂度为M*2n ,M,N可达到100,显然此方法时间复杂度巨大。
  • 71. 按武器搜索怎么样?1)我们必须将武器按它的编号划分成若干段 2)每一段的武器,哪些炸弹能对它们进行销毁,如下图:
  • 72. 算法将武器根据编号分为x段,[Si,Ti] (S1=1,Ti>=Si,Ti+1=Si+1)。 然后判断是否可以从A国的N颗炸弹中选出x颗,分别可以炸掉其中的一段。 如何分段:搜索算法 如何分段,理论复杂度为2m ,需要优化,留给学生思考? 如何选取炸弹:二分图的匹配
  • 73. 子串 给定一个由自然数串联而成的无限数列1234567891011121314……(母串) 求任意一个长度不超过200的数列(子串)在其中最早出现的位置。
  • 74. 分析:首先,由于母串可无限扩充,显然我们不可能把它全部生成出来。 如果边生成母串,边判断所生成的数串是否包含给定的子串,即使是使用字符串处理中高效的KMP算法,耗费的工作量也是巨大的。
  • 75. 1121314先枚举第1位1 自然数1之后为2,3,…… 母串中形如123…… 与子串从第2位开始不符枚举前2位11 自然数11之后为12,13…… 母串中形如111213…… 与子串从第3位开始不符考虑第2位开始12 自然数12之前为11,末位与子串第1位相同,之后为13,14,…… 母串中形如1314…… 与子串匹配!
  • 76. 如何优化呢?较好的方法是另辟蹊径: 刚才我们枚举的是母串的每一位,不妨换一个角度,从子串着手。 先来观察一些片断: 12345678910111213141516……
  • 77. 很自然得到算法:枚举子串所包含第一个完整的数a的位数La。 假设a在母串的第k位出现(k<=La) 判断接下来由a生成的序列是否与子串吻合。 如果吻合,则最优解的判断: (1) LaAns_k 4.跟据Ans_a及Ans_k计算出位数
  • 78. 总时间复杂度约为O(n^3),与之前的不可估量相比有了本质性提高。 第4步可通过多种途径求得,这里不作介绍。 由于其中牵涉到许多高精度的计算及字符串处理,要求我们细致认真。
  • 79. 小结充分挖掘题目特性是解决本题的关键。 得以使枚举这类看似低效率的方法得到较好的运用。 同时细致全面的考虑问题也是必不可少的。