• 1. 递 归长沙市雅礼中学 朱全民
  • 2. 重点内容递归的概念 递归的表示 递归实现方法 用递归实现简单回溯算法 实现递归时应注意的几个方面 递归与递推的区别和联系
  • 3. 递归的概念先看大家都熟悉的一个民间故事:从前有座山,山上有座庙,庙里有一个老和尚在给小和尚讲故事,故事里说,从前有座山,山上有座庙,庙里有一个老和尚在给小和尚讲故事,故事里说……。象这样,一个对象部分地由它自己组成,或者是按它自己定义,我们称之为递归。 一个函数、过程、概念或数学结构,如果在其定义或说明内部又直接或间接地出现有其本身的引用,则称它们是递归的或者是递归定义的。在程序设计中,过程或函数直接或者间接调用自己,就被称为递归调用。
  • 4. 递归的特点与应用场合用递归方法编写的问题解决程序具有结构清晰,可读性强等优点,且递归算法的设计比非递归算法的设计往往要容易一些,所以当问题本身是递归定义的,或者问题所涉及到的数据结构是递归定义的,或者是问题的解决方法是递归形式的时候,往往采用递归算法来解决。
  • 5. 递归的实现方法递归是借助于一个递归工作栈来实现. 1.递推: 问题向一极推进,这一过程叫做递推;这一过程相当于压栈. 2.回归: 问题逐一解决,最后回到原问题,这一过程叫做回归。这一过程相当于弹栈.
  • 6. 一个简单的实例将n个不同颜色的球,分别放到n个不同的盒子中去,问有多少种放法? 分析: 显然所有的方法数为 n! 这样,对于任意输入的整数n,我们只要算出n!即可. 设f(n)=n!,则有,
  • 7. 用递归实现Var n :integer; t:longint; function f (n:integer):longint; begin if n=0 then f:=1 else f:=n*f (n-1) end; begin write(‘n=’);readln(n); t:=f (n); writeln(‘n!=’,t); end.
  • 8. N=3时的递归过程
  • 9. (本页无文本内容)
  • 10. (本页无文本内容)
  • 11. 递归的表示Hanoi塔问题 进制转换问题 快速排序 归并排序 N皇后问题 背包问题 地图着色问题 ……
  • 12. 用递归实现回溯算法 回溯法也叫试探法,每次试着往前走,一直走到不通,然后撤回,重新试探.procedure run(当前状态); var i:integer; begin if 当前状态为边界 then begin if 当前状态为最佳目标状态 then 记下最优结果; exit;{回溯} end; for i←算符最小值 to 算符最大值 do begin 算符i作用于当前状态,扩展出一个子状态; if (子状态满足约束条件)and(子状态满足最优性要求)then run(子状态) end; end;
  • 13. 回溯法的几个重要因素(1) 状态: 作为递归的值参。 (2) 边界条件: 作为递归的结束条件。 (3) 递归范围: 作为for循环的初值和终值。 (4) 约束条件: 满足解的条件。 (5) 最优性要求:满足最优解的条件。
  • 14. N皇后问题 在N*N的棋盘上放置N个皇后而彼此不受攻击(即在棋盘的任一行,任一列和任一对角线上不能放置两个皇后),编程求解所有的摆放方法。
  • 15. 基本思想由于皇后的摆放位置不能通过某种公式来确定,因此对于每个皇后的摆放位置可以进行试探; 按行放置皇后,每一行放一皇后; 对每一行所放置的皇后按列进行试探; 若某个位置能放,则放,否则试放下一个位置 若某一行没有任何一个位置可放,则表示前面的皇后没放好,需要回溯。 若n个皇后都放好了,则得到了一个解。
  • 16. 算法基本框架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;
  • 17. 边界条件设置怎样判断某列放置了皇后 a: array [1..MaxN] of Boolean; {竖线被控制标记} 怎样判断某对角线上放置了皇后 b: array [2..MaxN * 2] of Boolean; {左上到右下斜线被控制标记} c: array [1-MaxN .. MaxN-1] of Boolean; {左下到右上斜线被控制标记}
  • 18. 程序Procedure Try( i: integer); var j:integer; begin if i=n+1 then print; for j:=1 to n do if a[j] and b[i+j] and c[i-j] then begin a[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;
  • 19. 思考题1: 0,1背包问题已知一个容量大小为M重量的背包和N种物品, 第i种物品的重量为Wi,若将物品放入背包将得到Pi的效益, 求怎样选取物品将得到效益最大。 输入数据: 从文件的第一行读入M和N,接下来N行,第i+1行的两个数分别表示第i种物品的重量和效益。 输出数据: 第一行输出一个数,表示背包所装物品的最大效益。 第二行输出若干个数字,分别表示所装物品的标号。
  • 20. 基本思想按物品顺序选择放置背包;每个物品有选和不选两种可能性; 按顺序将第某件物品放进包; 如果第i件物品能放进包,则放,并更新当前最优值; 如果第i件物品不能放进包,则有可能是前面的物品不能,则需要回溯; 若每件物品都试探了一次,则输出最优解。
  • 21. 设置剪枝条件设F[i]表示选第i~n个物品全部放到背包能得到的总效益。显然, F[ n ] = P n F[ i ] = F[ i+1 ]+Pi (i = 1 .. n-1) 假设当前已选到第i号物品, 如果, 当前搜索的效益值 + F[i+1] < 当前的最优值,则没有必要继续搜索下去。
  • 22. 算法框架Procedure Search( i: byte; weight :integer); Var K :byte; Begin If Now + F[i] <= Ans Then Exit; {剪枝条件} If Now > Ans Then Ans := Now; {修改最优解} For K:=i to n Do {选取物品} If W[k]<=weight Then Begin Now:=Now + P[k]; Out[k]:=True; Search (k+1, weight-W[k]); Now:=Now-P[k]; Out[k]:=False; End; End;
  • 23. 思考题2:构造字串生成长度为n的字串,其字符从26个英文字母的前p(p≤26)个字母中选取,使得没有相邻的子序列相等。例如p=3,n=5时 ‘a b c b a’满足条件 ‘a b c b c’不满足条件 输入:n,p 输出:所有满足条件的字串
  • 24. 分析状态:待扩展的字母序号i。 由于该变量的存储量太大,因此我们将s设为全局变量; 边界条件:产生了一个满足条件的字串,即 i=n+1; 搜索范围:从’a’开始的后p个字符; 约束条件:当前字串没有相邻子串相等的情况
  • 25. procedure solve (i: integer); var j, k: integer; t : longint ; begin if i=n+1 then {若产生了一个满足条件的字串,则输出} begin writeln (s); inc( t );exit {回溯} end; for k←1 to p do {搜索每一个可填字母} begin s←s+chr(64 + k );j←1;{检查当前字串是否符合条件} while (j<=i div 2) and (copy(s,length(s)-j+1,j)<>copy(s,length(s)-2*j+1,j)) do inc (j); if j>i div 2 then solve(i+1); {若当前字串符合条件,则递归扩展下一个字母} delete( s, length (s), 1 ) {恢复填前的字串} end; end;
  • 26. 递归与递推上楼梯问题: 一个人想登上n级楼梯,他上楼梯的方法有一步跨一级,也可一步跨两级,也可一步跨三级,问他上到楼顶,一共有多少种上楼梯的方法.
  • 27. 我们将上楼梯的方法用数字1,2,3表示,那么 如果只有1节楼梯,显然只有1种上楼的方法,方法为1。 如果只有2节楼梯,显然只有2种上楼的方法,方法为11,2。 如果只有3节楼梯,显然只有4种上楼的方法,方法为111,12,21,3。分析
  • 28. 多于3节楼梯呢?假设有n节楼梯, 设 f(n)表示上n节楼梯的方法数,显然有
  • 29. 算法Function f(n:integer):longint; Begin if n=1 then f:=1; if n=2 then f:=2; if n=3 then f:=4; if n>3 then f:=f(n-1)+f(n-2)+f(n-3); End;
  • 30. 是否我们可以满足了呢?看下面的算法(递推): Function f(n:integer):longint; var a,b,c,d: longint; Begin a:=1;b:=2;c:=4; for i:=4 to n do begin d:=a+b+c; a:=b;b:=c;c:=d; end; f:=d; End;
  • 31. 对比!算法1采用递归的形式,由于递归要反复压栈和弹栈,使得操作要多很多,并且受到空间限制,时间复杂度为O(3n). 算法2采用递推的形式,只是利用公式从前往后逐步递推,采用变量之间相互传递结果,时间复杂度为O(n). 实践证明,采用算法2比算法1快很多,而算法1最多做到N=20就巨慢了,算法2可做得巨大。