74递归与回溯

递归长沙市雅礼中学朱全民重点内容递归的概念递归的表示递归实现方法用递归实现简单回溯算法实现递归时应注意的几个方面递归与递推的区别和联系递归的概念先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之为递归。一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。递归的特点与应用场合用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。递归的实现方法递归是借助于一个递归工作栈来实现.1.递推:问题向一极推进，这一过程叫做递推；这一过程相当于压栈.2.回归:问题逐一解决，最后回到原问题，这一过程叫做回归。这一过程相当于弹栈.一个简单的实例将n个不同颜色的球,分别放到n个不同的盒子中去,问有多少种放法?分析:显然所有的方法数为n!这样,对于任意输入的整数n,我们只要算出n!即可．设f(n)=n!,则有，00)1(*1)(nnnfnnf用递归实现Varn:integer;t:longint;functionf(n:integer):longint;beginifn=0thenf:=1elsef:=n*f(n-1)end;beginwrite(‘n=’);readln(n);t:=f(n);writeln(‘n!=’,t);end.N=3时的递归过程递归的表示Hanoi塔问题进制转换问题快速排序归并排序Ｎ皇后问题背包问题地图着色问题……用递归实现回溯算法•回溯法也叫试探法，每次试着往前走，一直走到不通，然后撤回，重新试探．procedurerun（当前状态）；vari：integer；beginif当前状态为边界thenbeginif当前状态为最佳目标状态then记下最优结果；exit；{回溯}end；fori←算符最小值to算符最大值dobegin算符i作用于当前状态，扩展出一个子状态；if(子状态满足约束条件)and(子状态满足最优性要求)thenrun(子状态)end；end；回溯法的几个重要因素(1)状态:作为递归的值参。(2)边界条件:作为递归的结束条件。(3)递归范围:作为for循环的初值和终值。(4)约束条件:满足解的条件。(5)最优性要求：满足最优解的条件。N皇后问题在N*N的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置两个皇后），编程求解所有的摆放方法。基本思想由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置可以进行试探；按行放置皇后，每一行放一皇后；对每一行所放置的皇后按列进行试探；若某个位置能放，则放，否则试放下一个位置若某一行没有任何一个位置可放，则表示前面的皇后没放好，需要回溯。若n个皇后都放好了，则得到了一个解。算法基本框架ProcedureTry(i:integer)；{搜索第i行皇后的位置}varj:integer;beginifi=n+1then输出方案；forj:=1tondoif皇后能放在第i行第j列的位置thenbegin放置第i个皇后；对放置皇后的位置进行标记；Try（i+1）对放置皇后的位置释放标记；end;end;边界条件设置怎样判断某列放置了皇后a:array[1..MaxN]ofBoolean;{竖线被控制标记}怎样判断某对角线上放置了皇后b:array[2..MaxN*2]ofBoolean;{左上到右下斜线被控制标记}c:array[1-MaxN..MaxN-1]ofBoolean;{左下到右上斜线被控制标记}程序ProcedureTry(i:integer)；varj:integer;beginifi=n+1thenprint；forj:=1tondoifa[j]andb[i+j]andc[i-j]thenbegina[i]:=j;a[j]:=false;b[i+j]:=false;c[i-j]:=false;Try(i+1)a[j]:=true;b[i+j]:=true;c[i-j]:=true;end;end;思考题1:0,1背包问题已知一个容量大小为M重量的背包和N种物品，第i种物品的重量为Wi，若将物品放入背包将得到Pi的效益，求怎样选取物品将得到效益最大。输入数据：从文件的第一行读入M和N,接下来N行,第i+1行的两个数分别表示第i种物品的重量和效益。输出数据：第一行输出一个数，表示背包所装物品的最大效益。第二行输出若干个数字，分别表示所装物品的标号。基本思想按物品顺序选择放置背包；每个物品有选和不选两种可能性；按顺序将第某件物品放进包；如果第i件物品能放进包，则放，并更新当前最优值；如果第i件物品不能放进包，则有可能是前面的物品不能，则需要回溯；若每件物品都试探了一次，则输出最优解。设置剪枝条件设F[i]表示选第i~n个物品全部放到背包能得到的总效益。显然，F[n]=PnF[i]=F[i+1]+Pi（i=1..n-1）假设当前已选到第i号物品,如果，当前搜索的效益值+F[i+1]当前的最优值，则没有必要继续搜索下去。算法框架ProcedureSearch(i:byte;weight:integer);VarK:byte;BeginIfNow+F[i]=AnsThenExit;{剪枝条件}IfNowAnsThenAns:=Now;{修改最优解}ForK:=itonDo{选取物品}IfW[k]=weightThenBeginNow:=Now+P[k];Out[k]:=True;Search(k+1,weight-W[k]);Now:=Now-P[k];Out[k]:=False;End;End;思考题2:构造字串生成长度为n的字串，其字符从26个英文字母的前p(p≤26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时‘abcba’满足条件‘abcbc’不满足条件输入：n，p输出：所有满足条件的字串分析状态：待扩展的字母序号i。由于该变量的存储量太大，因此我们将s设为全局变量；边界条件：产生了一个满足条件的字串，即i=n+1；搜索范围：从’a’开始的后p个字符；约束条件：当前字串没有相邻子串相等的情况proceduresolve(i:integer)；varj,k:integer；t:longint;beginifi=n+1then{若产生了一个满足条件的字串，则输出}beginwriteln(s)；inc(t)；exit{回溯}end；fork←1topdo{搜索每一个可填字母}begins←s+chr(64+k)；j←1；{检查当前字串是否符合条件}while(j=idiv2)and(copy(s,length(s)-j+1,j)copy(s,length(s)-2*j+1,j))doinc(j)；ifjidiv2thensolve(i+1)；{若当前字串符合条件，则递归扩展下一个字母}delete(s,length(s),1){恢复填前的字串}end;end;递归与递推上楼梯问题:一个人想登上n级楼梯,他上楼梯的方法有一步跨一级,也可一步跨两级,也可一步跨三级,问他上到楼顶,一共有多少种上楼梯的方法.我们将上楼梯的方法用数字1，2，3表示，那么如果只有1节楼梯，显然只有1种上楼的方法，方法为1。如果只有2节楼梯，显然只有2种上楼的方法，方法为11，2。如果只有3节楼梯，显然只有4种上楼的方法，方法为111，12，21，3。分析多于3节楼梯呢?假设有n节楼梯,设f(n)表示上ｎ节楼梯的方法数，显然有3),3()2()1(3,42,21,1)(nnfnfnfnnnnf算法Functionf(n:integer):longint;Beginifn=1thenf:=1;ifn=2thenf:=2;ifn=3thenf:=4;ifn3thenf:=f(n-1)+f(n-2)+f(n-3);End;是否我们可以满足了呢？看下面的算法(递推)：Functionf(n:integer):longint;vara,b,c,d:longint;Begina:=1;b:=2;c:=4;fori:=4tondobegind:=a+b+c;a:=b;b:=c;c:=d;end;f:=d;End;对比！算法１采用递归的形式，由于递归要反复压栈和弹栈，使得操作要多很多，并且受到空间限制，时间复杂度为O(3n)．算法２采用递推的形式，只是利用公式从前往后逐步递推,采用变量之间相互传递结果，时间复杂度为Ｏ(n)．实践证明，采用算法２比算法１快很多，而算法１最多做到Ｎ=20就巨慢了,算法2可做得巨大。