递归与回溯算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,递归与回溯算法,1,递归的定义：,在定义一个过程或函数时出现调用本过程或本函数的成分，称为递归。若调用自身，称为直接递归。若过程或函数,p,调用过程或函数,q,，而,q,又调用,p,，则称为间接递归。,在程序设计中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。,递归的使用：,1.,定义是递归的,Function,jiech(n:integer):longint,;,Begin,if n=0 then,jiech,:=1,else,jiech,:=n*jiech(n-1);,End;,2,Function,fib(n:integer):longint,;,Begin,if(n,=0)or(n=1)then fib:=1,else fib:=fib(n-1)+fib(n-2);,End;,爬楼梯时可以,1,次走,1,个台阶，也可以,1,次走,2,个台阶。对于由,n,个台阶组成的楼梯，共有多少种不同的走法？,1,个台阶：只有,1,种走法；,2,个台阶：有两种走法；,(1+1,；,2),N,个台阶,(n2),，记走法为,f(n,),：,第,1,次走,1,个台阶，还剩,(n-1),个台阶，走法为,f(n-1),；,第,1,次走,2,个台阶，还剩,(n-2),个台阶，走法为,f(n-2),。,所以，,f(n,)=f(n-1)+f(n-2),。,定义,f(0)=1,，则有：,3,2.,有些数据结构是递归定义的，采用递归的方法编写算法既方便又有效。如单链表：,Type,node=,lnode,lnode,=record,data:integer,;,next:node,;,end;,求一个不带头结点的单链表,head,的所有,data,域之和的递归算法如下：,Function,sum(head:node):integer,;,Begin,if head=nil then sum:=0,else sum:=,head.data+sum(head.next,);,End;,4,3.,问题的求解方法是递归的,例：整数划分问题（版本,1,）,为避免重复，记,设,f(n,k,),为把正整数,n,分成,k,份的分法，那么：,先考虑特殊情况：,f(n,1)=1(n=n),f(n,n,)=1(n=1+1+1),当,kn,时，,f(n,k,)=0,(4),若,n1=1,，则：,其分法为,f(n-1,k-1),；,5,(5),若,n11,则,其分法为,f(n-k,k,),。,6,整数划分问题（版本,2,）,在正整数,n,的所有不同的划分中，将最大加数,n1,不大于,m,的划分个数记作,q(n,m,),。我们可以建立如下的递归关系。,(1)q(n,1)=1,n=1,；,当最大加数,n1,不大于,1,时，任何正整数,n,只有一种划分形式，即：,n=1+1+1,。,(2),q(n,m,)=,q(n,n,),，,m=n,；,最大加数,n1,实际上不能大于,n,。因此，,q(1,m)=1,。,(3),q(n,n,)=1+q(n,n-1),；,正整数,n,的划分有,n1=n,的划分和,n1m1;,n,的最大加数,n1,不大于,m,的划分由,n1=m,的划分和,n1=m-1,的划分组成。,7,Function,q(n,m:integer):integer,;,Begin,if(n,1)or(m1)then exit(0);,if(n,=1)or(m=1)then exit(1);,if nm then,exit(q(n,n,);,if n=m then exit(q(n,m-1)+1);,exit(q(n,m-1)+q(n-m,m);,End;,正整数,n,的划分数,p(n,)=,q(n,n,),。,8,递归过程或函数直接（或间接）调用自身，但如果仅有这些操作，那么将会由于无休止地调用而引起死循环。因此一个正确的递归程序虽然每次调用的是相同的子程序，但它的参数、输入数据等均有所变化，并且在正常的情况下，随着调用的深入，必定会出现调用到某一层时，不再执行调用而是终止函数的执行。,递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决。,递归分解不是随意地分解，要保证“大问题”和“小问题”,相似,。,例：采用递归算法求实数数组,A0.n,中的最小值。,9,算法,1:,设,f(a,i,),为数组元素,a0.ai,中的最小值。当,i=0,时，有,f(a,i,)=a0,；假设,f(a,i-1),已求出，则：,算法,2,：设,f(i,j,),为,ai.aj,中的最小值。将,a0.an,看作一个线性表，它可以分解成,a0.ai,和,ai+1.an,两个子表，分别求得各自的最小值,x,和,y,，较小者就是,a0.an,中的最小值。而求解子表中的最小值方法与总表相同，即再分别把它们分成两个更小的子表，如此不断分解，直到表中只有一个元素为止,(,该元素就是该表中的最小值,),。,10,function,min(i,j:integer):real,;,var,mid:integer,;,min1,min2:real;,begin,if i=j then min:=,ai,else,begin,mid:=(,i+j,)div 2;min1:=,min(i,mid,);,min2:=min(mid+1,j);,if min1min2 then min:=min1,else min:=min2;,end;,end;,11,归并排序：,设归并排序的区间是,Rlow.high,，则排序的步骤如下：,(1),分解,:,将当前区间,Rlow.high,一分为二，即求,mid=(,low+high)div,2,；递归地对子区间,Rlow.mid,和,Rmid+1.high,进行继续分解。其终结条件是子区间长度为,1(,因为一个记录的子表一定是有序表,),。,(2),归并,:,与分解过程相反，将已排序的子区间,Rlow.mid,和,Rmid+1.high,归并为一个有序的区间,Rlow.high,。,procedure,mergesort(var,r:arr;low,high:integer,);,var,mid:integer,;,begin,if low0 then begin,hanoi(n-1,s,d,t);tot:=tot+1;,writeln(s,-,d);hanoi(n-1,t,s,d);,end;,end;,begin,readln(n,);tot:=0;,hanoi(n,A,B,C,);,writeln(tot,);,end.,15,搜索算法,信息学奥赛的试题一般有两种类型：,1.,简明的数学模型揭示问题本质。对于这一类试题，我们尽量用解析法求解。,2.,对给定的问题建立数学模型，或即使有一定的数学模型，但采用数学方法解决有一定的困难。对于这一类试题，我们只好用模拟或搜索求解。,尽管搜索的时间复杂度一般是指数级的，但在缺乏解决问题的有效模型时，搜索却是一种行之有效的解决问题的基本方法，而且使用搜索算法解决问题时，在实现过程中有很大的优化空间。信息学奥赛中考察搜索算法，一是考察选手算法运用能力，二是考察选手算法优化能力。,枚举法（穷举法）,回溯（深度优先搜索）,广度优先搜索,16,枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。,虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：,(1),可预先确定每个状态的元素个数,n,；,(2),状态元素,a,1,，,a,2,，,，,a,n,的可能值为一个连续的值域。,设,:a,i1,状态元素,a,i,的最小值；,a,ik,状态元素,a,i,的最大值,(1in),，即,a,11,a,1,a,1k,，,a,21,a,2,a,2k,，,a,i1,a,i,a,ik,，,，,a,n1,a,n,a,nk,for a,1,a,11,to a,1k,do,fo,a,2,a,21,to a,2k,do ,for a,i,a,i1,to,a,ik,do ,for a,n,a,n1,to,a,nk,do,if,状态,(a,1,，,，,a,i,，,，,a,n,),满足检验条件,then,输出问题的解；,17,S E N D,+M O R E,M O N E Y,算式中的字符分别表示不同的阿拉伯数字，找出能使等式成立的所有数字组合。,直接枚举,S,、,E,、,N,、,D,、,M,、,O,、,R,、,Y,分别从,0.9,范围内尝试每个取值可能，共有,10,8,种组合需要判断。,观察算式的形式，根据加法运算的特点可知：,M=1,进一步分析，,O,0,S=9,因此只需枚举判断,7,5,种组合即可。,18,回溯法也是搜索算法中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优先搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。,N,皇后问题 在,N*N,的棋盘上放置,N,个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置,2,个皇后），编程求解所有的摆放方法。,19,以,4,皇后为例：,20,回溯法的基本思想为：,在按某种搜索策略的搜索过程中，在某种状态，继续往前搜索已经确定不会得到正确答案的情况下，我们可以返回上一搜索状态，去沿新的可能性继续搜索。要回溯到上一状态，则说明我们在前进中的状态必须保存下来，我们采用“栈”来存放。,21,基本思路：若已有满足约束条件的部分解，不妨设为（,x1,x2,x3,xi,），,in then,输出结果,else for j:=,下界,to,上界,do,begin,xi,:=hj;,if,可行,满足限界函数和约束条件,then,begin,置值；,try(i+1);,取消置值；,end;,end;,end;,24,算法框架：,1.,针对所给问题，定义问题的解空间；,2.,确定易于搜索的解空间结构；,3.,以深度优先的方式搜索解空间，并且在搜索过程中用剪枝避免无效搜索；,4.,递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法。,25,下面是放置第,i,个皇后的的递归算法：,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;,26,N,皇后问题的递归算法的程序如下：,program N_Queens;,const maxn=10;,最多皇后数,var,A:array 1.maxn of boolean;,同列,-,竖线被控制标记,b:array 2.maxn*2 of boolean;i+j,和相等,-,左下到右上斜线被控制标记,c:array 1maxn.maxn1 of boolean;j-i,差相等,-,左上到右下斜线被控制标记,x:array 1.maxn of integer;,记录皇后的解,total:longint;,解的总数,n:integer;,皇后个数,procedure out;,输出方案,var i:integer;,begin,inc(total);write(total:3,:);,for i:=1 to n do write(xi:3);writeln;,end;,27,procedure try(i:integer);,搜索第,i,个皇后的可行位置,var j:integer;,begin,if i=n+1 then out;N,个皇后都放置完毕，则输出解,for j:=1 to n do,if,aj,and,bj,+i and,cj,i then begin,xi,:=j;,aj,:=false;,bj,+i:=false;,cj,i:=false;,try(i+1);,搜索下一皇后的位置,aj,:=true;,bj,+i:=true;,cj,i:=true;,end;,end;,28,Beginmain,write(Queens,Numbers=);,total:=0;,readln(n,);,fillchar(a,sizeof(a,),true);,fillchar(b,sizeof(b,),true);,fillchar(c,sizeof(c,),true);,try(1);,writeln(total,=,total);,end.,思考练习：跳棋的挑战,29,深度优先搜索的基本算法结构,（,1,）递归实现。,procedure,dfs_try(i,);,begin,for i:=1 to,maxr,do,begin,if,子结点,mr,符合条件,then,begin,产生的子结点,mr,入栈；,if,子结点,mr,是目标结点,then,输出；,else dfs_try(i+1);,栈顶元素出栈；,end;if,end;for,end;,30,(2),非递归实现,procedure,dfs(dep,);,begin,dep,:=0;,repeatrepeat,1,dep,:=dep+1;,j:=0;p:=false;,repeatrepeat,2,j:=j+1;,if,mr,符合条件,then,begin,产生子结点并将其记录；,if,子结点,mr,是目标结点,then,输出并出栈,else p:=true;,end,31,else,回溯,if j=,maxj,then,begin,dep,:=dep-1;,if,dep,0 then,取回栈顶元素；,else p:=true;,end,else p:=false;,until p=,true;repeat,1,until,dep,=0;repeat 2,end;,32,工作安排,(task),n,个人从事,n,项工作，每人只能从事一项，求最佳安排使效益最高。,设有,A,，,B,，,C,，,D,，,E,五人从事,J1,，,J2,，,J3,，,J4,，,J5,五项工作，每人,只能从事一项，他们的效益如下,:,当,A,从事,J5,，,B,从事,J3,，,C,从事,J4,，,D,从事,J1,，,E,从事,J2,时收益最大值：,50,输入：,n,和矩阵,输出：最大效益和方案,输入：,5,13 11 10 4 713 10,10,8 5 5 9 7 7 415 12 10 11 510 11 8 8 4,输出：,50,1,：,52,：,33,：,44,：,15,：,2,33,const,maxn=10;,var,data:array1.maxn,1.maxn of integer;,矩阵,n,i,j,max:integer;,f,g:array 1.maxn of integer;,f,：,保存临时组合；,g,：,保存最佳组合,p:array 1.maxn of integer;,工作是否已分配,procedure init;,begin,assign(input,task.in,);,reset(input);,readln(n,);,for i:=1 to n do,for j:=1 to n do read(datai,j);,close(input);,end;,34,procedure try(k,t:integer);,搜索第,k,个人应从事的工作，获利共为,t,，,初始时：,try,（,1,，,0,）,var,i:integer;,begin,if k=n+1 then,if tmax then,begin max:=t;g:=f;,保存当前的最佳方案,exit;end;,for i:=1 to n do,if pi=0 then,begin,fk:=i;pi:=1;,try(k+1,t+datak,i);,pi:=0;,end;,end;,t:=t+datak,i;,Try(k+1,t);,t:=t-datak,i,35,begin,init;,max:=0;,fillchar(p,sizeof(p),0);,try(1,0);,writeln(max,);,for i:=1 to n do,writeln(i,:,gi,);,end.,36,数字排列,在一个,N*N,的棋盘上（,1=n=100),填入,1,2,.,n*n,共,n*n,个数，使得任意两个相邻的数之和为素数。例如：,n=2,时，有,:12 43,n=41 2 11121615 8 513 4 914 6 710 3,37,分析：逐个尝试,1,到,n*n,之间的数,k,放在（,i,，,j,）,处，依次判断它与上方（,i-1,j,）,和左边,(i,j-1),上的数之和是否为素数，是就放在,(,i,j,),处，再处理（,i,j+1);,如果不是素数，则继续在,k+1,到,n*n,之间搜索合适的数能放在,(,i,j,),处。如果找不到合适的数放在（,i,j,）处，回溯到它的前一个位置。,const maxn=100;,type a=array1.2*maxn*,maxnof,boolean;,var,i,j,k,m,n,x,y,nn:integer,;,p:a;,素数表：,pi=true:i,是素数，,pi=false:i,不是素数,b:array1.maxn,1.maxnof integer;,坐标,used:array1.maxn*,maxnof,boolean;,检查是否该数是否用过,38,筛选法创建素数表,procedure prime;,var i,j,s:integer;,begin,fillchar(p,sizeof(p),true,);,p1:=false;,for i:=2 to,3*n div 2,do,依次搜索素数,i,并筛掉是,i,倍数的数,if pi then,begin,j:=2*i;,while j1 then if not(pbx-1,y+k)then,ok:=false;,if y1 then if not(pbx,y-1+k)then,ok:=false;,end;,40,procedure,try(x,y,dep:integer,);,递归搜索（,x,y,）,处放,第,dep,个,数,var i:integer;,begin,if,dep,=n*n+1 then print,else,如果已放了,n*n,个数，得出一种方法,for i:=1 to n*n do,if not(usedi)and ok(x,y,i)then,begin,bx,y:=i;,usedi:=true;,if y=n then try(x+1,1,dep+1),如果当前是最右边一列，则转到下一行首列,else try(x,y+1,dep+1);,继续放当前行的下一列,usedi:=false;,释放标志,end;,end;,41,procedure print;,var i,j:integer;,begin,for i:=1 to n do begin,for j:=1 to n do write(bi,j:4);,writeln;,end;,halt;,end;,42,主程序：,begin,readln(n,);,if n=1 then begin,writeln(NO);halt;end,;,prime;,b1,1:=1;,for i:=2 to n*n do usedi:=false;,used1:=true;,try(1,2,2);,writeln(NO,);,end.,思考练习：数环,43,因式分解,输入自然数,n,（,10,9,）,将,n,分解成一系列自然数乘积的形式：,N=a1*a2*.*am,，,1a1=a2=.=am0,，,则产生一个分解方案,n=b,1,*,b,h,*n,搜索范围：,目前因式中尚待分解出因子,a,i,显然,jik,约束条件：,(n div,a,i,a,i,)and(n,mod,a,i,=0),若,n,不可能再分解出因子,a,i,a,k,，,应回溯,若满足上述约束条件，则分解出因子,a,i,，即,b,h+1,=,a,i,，,产生一个分解方案：,n=b,1,*b,2,*,b,h,*b,h+1,*n,将表达式的尾因子,n,、,目前从因子表中分解出的因子数,h,和待分解的因子序号,j,作为递归程序的值参；因子表指针,i,作为局部变量。,46,由此得出递归程序,procedure print(j,，,n,，,h),；,从,a,j,出发递归搜索分解方案,var i,：,:integer,；,begin,if h0 then,输出第,t,个方案为,n=b,1,*b,2,*,*,b,h,*n,；,for i,：,=j to k do ,试分解,a,j,a,k,if n div,a,i,0 then begin,inc(t,);for i:=1 to h do write(bi,*);writeln(n1);,end;,for i:=j to k do,if n1 div aiai then exit,else if n1 mod ai=0,then begin,bh+1:=ai;,try(i,n1 div ai,h+1);,end;,end;,49,var,a,b:array1.100000 of,longint,;,n,t,k:longint,;,主程序,:,begin,readln(n,);,t:=0;,makebiao,;,try(1,n,0);,writeln(t,);,end.,50,回溯法的优化,1.,递归前对尚待搜索的信息进行预处理,如果搜索对象是通过某种运算直接得出其结果的，那么搜索前一般需进行预处理,通过相应运算将所有搜索对象的计算结果置入常量表，搜索过程中只要将当前搜索对象的结果值从常量表取出即可。这样可以显著改善搜索效率。否则，在搜索过程中每遇到这些对象都要计算，则会产生大量的重复运算。,2,、记忆化搜索,如果解答树中存在一些性质相同的子树，那么，只要我们知道了其中一棵子树的性质，就可以根据这个信息，导出其它子树的性质。这就是自顶向下记忆化搜索的基本思想。,51,序关系计数问题,1,、枚举所有序关系表达式,由于类似于,a=b,和,b=a,的序关系表达式是等价的，为此，规定等号前面的大写字母在,ASCII,表中的序号，必须比等号后面的字母序号小。,状态（,Step,，,First,，,Can,）：其中,Step,表示当前确定第,Step,个关系符号；,First,表示当前大写字母中最小字母的序号；,Can,是一个集合，集合中的元素是还可以使用的大写字母序号,边界条件（,step=n,）：即确定了最后关系符号,搜索范围（,Firstin,）：枚举当前大写字母的序号,约束条件（,i in Can,）：序号为,i,的大写字母可以使用,52,算法,1,：,procedure Count(Step,，,First,，,Can);,从当前状态出发，递归计算序关系表达式数,begin,if Step=n then begin ,若确定了最后一个关系符号，则输出统计结果,for i,First to n do if i in Can then Inc(Total),；,Exit;,回溯,end,；,then,for i,First to n do ,枚举当前的大写字母,if i in Can then begin ,序号为,i,的大写字母可以使用,Count(Step+1,，,i+1,，,Can-i),；,添等于号,Count(Step+1,，,1,，,Can-i),添小于号,Endthen,end,；,Count,主程序调用,Count(1,，,1,，,1.n),后，,Total,的值就是结果。该算法的时间复杂度是,W(n!),53,2,、粗略利用信息,若已经确定了前,k,个数，并且下一个关系符号是小于号，这时所能产生的序关系数就是剩下的,n-k,个数所能产生的序关系数。,设,i,个数共有,Fi,种不同的序关系，那么，由上面的讨论可知，在算法,1,中，调用一次,Count(Step+1,，,1,，,Can-i),之后，,Total,的增量应该是,Fn,-Step,。这个值可以在第一次调用,Count(Step+1,，,1,，,Can-i),时求出。而一旦知道了,Fn,-Step,的值，就可以用,TotalTotal+Fn,-Step,代替调用,Count(Step+1,，,1,，,Can-i),54,procedure Count(Step,，,First,，,Can),；,Step,，,First,，,Can,的含义同算法,1,begin,if Step=n then begin ,若确定了最后一个关系符号，,则输出统计结果,for i,First to n do if i in Can then Inc(Total),；,Exit,回溯,end,；,then,for i,First to n do ,枚举当前的大写字母,if i in Can,序号为,i,的大写字母可以使用,then begin,Count(Step+1,，,i+1,，,Can-i),；,添等于号,if Fn-Step=-1 then begin,第一次调用,Fn-Step,Total,；,Count(Step+1,，,1,，,Can-i),；,添小于号,Fn-Step,Total-Fn-Step Fn-Step=Total,的增量,end then,else Total,Total+Fn-Step Fn-Step,已经求出,endthen,end,；,count,该算法实质上就是自顶向下记忆化方式的搜索，它的时间复杂度为,W(2,n,),。,55,3,、充分利用信息,在搜索的过程中，如果确定在第,k,个大写字母之后添加第一个小于号，则可得到下面两条信息：,第一条信息：前,k,个大写字母都是用等号连接的。前半部分将产生的序关系数，就是,n,个物体中取,k,个的组合数,第二条信息：在此基础上继续搜索，将产生,Fn-k,个序关系表达式。,这样，我们可以得到,Fn,的递推关系式：,采用上述公式计算,Fn,的算法记为算法,3,，它的时间复杂度是,W(n,2,),。,56,var,Total,：,Comp,；,答案,F,：,array0.maxn of Comp,；,Fi,为,i,个数的序关系表达式个数,i,，,j,：,Integer,；,x,：,Comp,；,begin,FillChar(F,，,Sizeof(F,),，,0),；,F,初始化,F0,1,；,for i,1 to n do begin,递推,F,数组,Fi,0,；,x,1,；,for j,1 to i do begin,计算,Fi,x,x,*(i-j+1)/j,；,Fi,Fi+x,*Fi-j,Endfor,end,；,for,writeln(Fn,),；,输出结果,end,；,main,算法,3,充分利用信息，通过两重循环的递推计算,Fn,，,将时间复杂度降到,W(n,2,),实现了程序的最优性要求。,57,生日蛋糕,7,月,17,日是,Mr,W,的生日，,ACM-THU,为此要制作一个体积为,n,的,m,层生日每层都是一个圆柱体。设从下往上数第,i(1im),层蛋糕是半径为,R,i,，,高度为,h,i,的圆柱。当,iR,i+1,且,h,i,h,i+1,。,由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积,Q,最小,(,令,Q=S),。,请编程对给出的,n,和,m,，,找出蛋糕的制作方案（适当的,r,i,和,h,i,的值），使,S,最小。,（除,Q,外，以上所有数据皆为正整数）,58,输入,有两行，第一行为,n,（,n10000,），,表示待制作的蛋糕的体积为,n,；,第二行为,m(m20),，,表示蛋糕的层数为,m,。,输出,仅一行，是一个正整数,S,（,若无解则,S=0,）。,样例输入,1002,样例输出,68,附：圆柱公式体积,V=r,2,h,侧面积,A=2rh,底面积,A=r,2,59,我们设当前为第,i,层蛋糕，半径和高度为,R,H,，当前的表面积为,S,，余下的体积为,V,。,我们可以用,(I,R,H,V,S),表示一个状态。,则初始状态为（,1,R1,H1,N-R1*R1*H,R1*R1+2*R1*H1,）,目标状态（,M,Rm,Hm,0,Sm,），其中,Sm,表示总面积。于是我们的目标是找到一条从初始结点到任意目标结点的路径，并且,Sm,最小。,（,I,Ri,Hi,Vi,Si,）,（,i+1,R,i+1,H,i+1,V,i+1,S,i+1,）,其中必须满足,:,1.RiR,i+1,2.HiH,i+1,3.V,i+1,=Vi-R,i+1,*R,i+1,*H,i+1,4.S,i+1,=Si+2*R,i+1,*H,i+1,60,算法,1:,Procedure,search(I,Ri,Hi,Si,Vi,),If i=M then,更新最优值,Else,For R,i+1,-R,i,-1,downto,1,For H,i+1,-H,i,-1,downto,1,S,i+1,-S,i,+2*R,i+1,*H,i+1,V,i+1,-V,i,-R,i+1,*H,i+1,search(i+1,R,i+1,H,i+1,S,i+1,V,i+1,),主程序：,For R,1,-n,downto,m do,For H,1,Best then exit;,if St0 then for R:=,LastR,downto,St do,begin,O:=,Min(LastV,div(R*,R),LastH,);,for H:=O,downto,St do,begin,NowV,:=,LastV,-R*R*H;,NowS,:=2*R*R;,try(St-1,R-1,H-1,NowV,LastS+NowS);,end;,end,else if,LastV,=0 then Best:=,LastS,End;,62,Beginmain,打开文件；读入数据；,Best:=,MaxInt,;,for R:=M to,trunc(sqrt(N,)do,for H:=N div(R*R),downto,M do,begin,V:=N-R*R*H;,S:=2*R*H;,try(M-1,R-1,H-1,V,S+R*R);,end;,End.,63,剪枝：,Ri,Hi,分别是第,i,层可能的最大半径和最大高度，,Ri,和,Hi,都是递减的，上面还有,M-i+1,层。设,FSi,表示估计的剩余最小侧面积，,Vi,表示剩余的体积，,Si,表示现有的面积。,如果当前面积加上预测可能的最小面积大于已经得到的最优面积,Best,，就可以剪掉当前枝。即：,如果,FS,i,+S,i,=Best,，就放弃继续搜索。,另外，,如果，就没有必要继续搜索下去了；,如果以后的每次蛋糕都按最大去做，也不能将剩余的体积,Vi,做完，那么就没有必要搜索下去了。,64,分数分解,近来,IOI,专家们正在进行一项有关整数方程的研究，研究涉及到整数方程解集的统计问题，问题是这样的：,对任意的正整数,N,，我们有整数方程：,1,X1,1,X2,1,Xn,=1,该整数方程的一个解集,x1,x2,，,xn,是使整数方程成立的一组正整数，例如,n,n,n,，,n,就是一个解集，在统计解集时，,IOI,专家把数据值相同但顺序不一样的解集认为是同一个解集，例如：当,n=3,时，我们把,2,3,6,和,3,，,6,，,2,义为是同一个解集。,现在的任务是：对于一个给定的,m,在最多只允许,1,个,xi,大于,m,时，求出整数方程不同解集的个数。,输入：输入文件共一行，有,2,个空格分开的正整数，它们分别是,n,m(n,=20,m1e10 then exit;,for i:=p to m do search(step+1,i,t1*i+t2,t2*i);,End;,主程序：,begin,readln(n,m);Tot:=0;,for i:=2 to m do search(2,i,1,i);,writeln(tot,);,end.,If (n-step+1)/p+t1/t21 then exit;,Procedure,reduce(var,t1,t2:comp);,67,埃及分数,在古埃及，人们使用单位分数的和（形如,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,都大。,输入：,a,，,b,输出：若干个数，从小到大排列，依次是单位分数的分母。,输入样例：,19 45,输出样例：,5 6 18,68,数组,D,：存储所有的分母,状态：,Step(,阶段数,)a/b(,分数值,),下一状态：,Step+1 a/b-1/Dstep,与分数分解类似：,PROCEDURE,Search(k,a,b,);,决定第,k,个分母,dk,reduce(a,b,);,化简,a,b,if k=depth+1 then exit,else if (b mod a=0)and (b div adk-1)then ,dk,:=b div a;,if not found or (,dk,maxlongint,div b then t:=,maxlongint,防止溢出,If found and (t=,answerdepth,)then t:=answerdepth-1;,S:=b div a+1;,69,Program,aiji,;,初始化；,for depth:=1 to,maxdepth,do ,search(1,a,b);if,找到解,then,输出,深度可变的深度优先搜索,70,