递归与回溯算法

1、递归与回溯算法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;2Function fib(n:integer):longint;Begin if(n=0)or(n=1)then fib:=1 else fi

2、b:=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，则有：32.有些数据结构是递归定义的，采用递归的方法编写算法既方便又有效。如单链表：Type node=lnode lnode=record data:integer;

3、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;43.问题的求解方法是递归的 例：整数划分问题（版本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,则其分法

4、为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的划分组成。7Function q(n,m:integer):integer;Be

5、gin if(n1)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 递归过程或函数直接（或间接）调用自身，但如果仅有这些操作，那么将会由于无休止地调用而引起死循环。因此一个正确的递归程序虽然每次调用的是相同的子程序，但它的参数、输入数据等均有所变化，并且在正常的情况下，随着调用的深入，必定会出现调用到某一层时，不再执行调用而是终止函数的执行

6、。 递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决。 递归分解不是随意地分解，要保证“大问题”和“小问题”相似。例：采用递归算法求实数数组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中的最小值。而求解子

7、表中的最小值方法与总表相同，即再分别把它们分成两个更小的子表，如此不断分解，直到表中只有一个元素为止(该元素就是该表中的最小值)。10function 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.hig

8、h，则排序的步骤如下：(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

9、+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.对给定的问题建立数学模型，或即使有一定的数学模型，但采用数学方法解决有一定的困难。对于这一类试题，我们只好用模拟或搜索求解。尽管搜索的时间复杂度一般是指数级的，但在缺乏解决问题的有效模型时，搜索却是一种行之有效的解决问题的基本方法，而且使用搜索算法解决问题时，在实现过程中

10、有很大的优化空间。信息学奥赛中考察搜索算法，一是考察选手算法运用能力，二是考察选手算法优化能力。枚举法（穷举法）回溯（深度优先搜索）广度优先搜索16 枚举法的基本思想是根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的。能使命题成立，即为其解。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法有所不同。因为适用枚举法求解的问题必须满足两个条件：(1) 可预先确定每个状态的元素个数n；(2) 状态元素a1，a2，an的可能值为一个连续的值域。设:ai1状态元素ai的最小值；aik状态元素ai的最大值(1in)，即a11a1a1k，a21a2a2k， ai1aia

11、ik，an1anankfor a1a11 to a1k do fo a2a21 to a2k do for aiai1 to aik do for anan1 to ank do if 状态(a1，ai，an)满足检验条件 then 输出问题的解；17 S E N D+ M O R EM O N E Y算式中的字符分别表示不同的阿拉伯数字，找出能使等式成立的所有数字组合。直接枚举S、E、N、D、M、O、R、Y分别从0.9范围内尝试每个取值可能，共有108种组合需要判断 。观察算式的形式，根据加法运算的特点可知：M=1,进一步分析，O0,S=9,因此只需枚举判断75种组合即可。18 回溯法也是搜

12、索算法中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优先搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。 N皇后问题 在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置2个皇后），编程求解所有的摆放方法。19以4皇后为例：20回溯法的基本思想为： 在按某种搜索策略的搜索过程中，在某种状态，继续往前搜索已经确定不会得到正确答案的情况下，我们可以返回上一搜索状态，去沿新的可能性继续搜索。要回溯到上一状态，则说明我们在前进中的状态必须保存下来

13、，我们采用“栈”来存放。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个皇后的的递归算

14、法：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;26N皇后问题的递归算法的程序如下：program N_Queens; const maxn= 10;最多皇后数 var A:array 1.maxn of boolean; 同列-竖线被控制标记 b:array 2.maxn * 2 of boo

15、lean;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;27procedure try(i: integer);搜索第i个皇后

16、的可行位置 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;28Beginmain write(Queens Numbers = ); total:=0; readln(n); fi

17、llchar(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

18、;if end;forend;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; end31 else回溯 if j=maxj then begin dep:=dep-1; if dep0 then 取回栈顶元素； else p:=true; end else p:=false; unti

19、l p=true;repeat 1 until dep=0;repeat 2end;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和矩阵输出：最大效益和方案输入：513 11 10 4 713 10 10 8 5 5 9 7 7 415 12 10 11 510 11 8 8 4输出：501：52：33：44：15：233 const maxn=10; var

20、 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;34procedure try(k,t:

21、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,i35begin init; max:=0; fillchar(p,sizeof(p),0); t

22、ry(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 43n=41 2 11121615 8 513 4 914 6 710 337分析： 逐个尝试1到n*n之间的数k放在（i，j）处，依次判断它与上方（i-1,j）和左边(i,j-1)上的数之和是否为素数，是就放在(i,j)处，再处理（i,j+1);如果不是素数，则继续在k+1到n*n之间搜索合适的数能放在(i,j)处。如果找不到

23、合适的数放在（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);

24、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;40procedure try(x,y,dep:integer);递归搜索（x,y）处放第 dep 个数var i:integer;begin if dep=n*n+1 then print else 如果已放了n*n个数，得出一种方法 for i

25、:=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;41procedure 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;e

26、nd;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=b1*bh*n 搜索范围：目前因式中尚待分解出因子ai显然 jik 约束条件： ( n div aiai)and(n mo

27、d ai=0) 若n不可能再分解出因子aiak，应回溯 若满足上述约束条件，则分解出因子ai，即bh+1=ai，产生一个分解方案：n=b1*b2*bh*bh+1*n将表达式的尾因子n、目前从因子表中分解出的因子数h和待分解的因子序号j作为递归程序的值参；因子表指针i作为局部变量。46由此得出递归程序 procedure print (j，n，h)；从aj出发递归搜索分解方案 var i：:integer； begin if h0 then 输出第t个方案为n=b1*b2*bh*n； for i：=j to k do 试分解ajak if n div ai0 then begin inc(t);

28、 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;49var 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.递归前对尚待搜索的信息进行

29、预处理 如果搜索对象是通过某种运算直接得出其结果的，那么搜索前一般需进行预处理通过相应运算将所有搜索对象的计算结果置入常量表，搜索过程中只要将当前搜索对象的结果值从常量表取出即可。这样可以显著改善搜索效率。否则，在搜索过程中每遇到这些对象都要计算，则会产生大量的重复运算。2、记忆化搜索如果解答树中存在一些性质相同的子树，那么，只要我们知道了其中一棵子树的性质，就可以根据这个信息，导出其它子树的性质。这就是自顶向下记忆化搜索的基本思想。51序关系计数问题1、枚举所有序关系表达式由于类似于a=b和b=a的序关系表达式是等价的，为此，规定等号前面的大写字母在ASCII表中的序号，必须比等号后面的字母

30、序号小。状态（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 iFirst to n do if

31、i in Can then Inc(Total)； Exit; 回溯 end；then for iFirst 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!) 532、粗略利用信息 若已经确定了前k个数，并且下一个关系符号是小于号，这时所能产生的序关系数就是剩下的n-k个数所能产生的序关系数

32、。设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)54procedure Count(Step，First，Can)； Step，First，Can的含义同算法1begin if Step=n then begin 若确定了最后一个关系符号，则输出统计结果 for iFirst to

33、n do if i in Can then Inc(Total)；Exit 回溯 end；then for iFirst 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 TotalTotal+Fn-Step Fn-Step已经求出

34、 endthen end；count该算法实质上就是自顶向下记忆化方式的搜索，它的时间复杂度为W(2n)。 553、充分利用信息在搜索的过程中，如果确定在第k个大写字母之后添加第一个小于号，则可得到下面两条信息：第一条信息：前k个大写字母都是用等号连接的。前半部分将产生的序关系数，就是n个物体中取k个的组合数第二条信息：在此基础上继续搜索，将产生Fn-k个序关系表达式。这样，我们可以得到Fn 的递推关系式：采用上述公式计算Fn的算法记为算法3，它的时间复杂度是W(n2)。56var Total ：Comp；答案 F ：array0.maxn of Comp；Fi为i个数的序关系表达式个数 i，

35、j ：Integer； x ：Comp； begin FillChar(F，Sizeof(F)，0)；F初始化 F0 1； for i1 to n do begin递推F数组 Fi 0；x1； for j1 to i do begin 计算Fi xx*(i-j+1)/j；Fi Fi+x*Fi-j Endfor end；for writeln(Fn)； 输出结果 end；main算法3充分利用信息，通过两重循环的递推计算Fn，将时间复杂度降到W(n2),实现了程序的最优性要求。 57生日蛋糕 7月17日是MrW的生日，ACM-THU为此要制作一个体积为n的m层生日每层都是一个圆柱体。设从下往上数

36、第i(1im)层蛋糕是半径为Ri， 高度为hi的圆柱。当iRi+1且hihi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小(令Q= S)。请编程对给出的n和m，找出蛋糕的制作方案（适当的ri和hi的值），使S最小。（除Q外，以上所有数据皆为正整数）58输入有两行，第一行为n（n10000），表示待制作的蛋糕的体积为n；第二行为m(m20)，表示蛋糕的层数为m。输出仅一行，是一个正整数S（若无解则S=0）。样例输入1002样例输出68附：圆柱公式体积V=r2h侧面积A=2rh底面积A=r259我们设当前为第i层蛋糕，半径和高度为R,H，当前的

37、表面积为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,Ri+1,Hi+1,Vi+1,Si+1）其中必须满足:1.RiRi+12.HiHi+13.Vi+1=Vi-Ri+1*Ri+1*Hi+14.Si+1=Si+2*Ri+1*Hi+160算法1:Procedure search(I,Ri,Hi,Si,Vi)If i=M then 更新

38、最优值ElseFor Ri+1-Ri-1 downto 1For Hi+1-Hi-1 downto 1Si+1-Si+2*Ri+1*Hi+1Vi+1-Vi-Ri+1*Hi+1search(i+1,Ri+1,Hi+1,Si+1,Vi+1)主程序：For R1-n downto m doFor H1Best 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; t

39、ry(St-1,R-1,H-1,NowV,LastS+NowS); end; end else if LastV=0 then Best:=LastSEnd;62Beginmain 打开文件；读入数据；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，就可以剪掉当前枝。即：如果FSi+Si=Best