递归与回溯精选文档.ppt

递归与回溯本讲稿第一页，共二十八页重点内容n递归的概念递归的概念n递归的表示递归的表示n递归实现方法递归实现方法n用递归实现简单回溯算法用递归实现简单回溯算法n实现递归时应注意的几个方面实现递归时应注意的几个方面n递归与递推的区别和联系递归与递推的区别和联系本讲稿第二页，共二十八页递归的概念n先看大家都熟悉的一个民间故事：从前有座山，山上有先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说尚讲故事，故事里说。象这样，一个对象部分地由。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之为递归。它自己组成，或者是按它自己定义，我们称之为递归。n一个函数、过程、概念或数学结构，如果在其定义或说明内部一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。自己，就被称为递归调用。本讲稿第三页，共二十八页递归的特点与应用场合递归的特点与应用场合n用递归方法编写的问题解决程序具有结构清晰，可读用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法题的解决方法是递归形式的时候，往往采用递归算法来解决。来解决。本讲稿第四页，共二十八页递归的实现方法递归的实现方法递归是借助于一个递归工作递归是借助于一个递归工作栈栈来实现来实现.1.递推递推:问题向一极推进，这一过程叫做递推；这问题向一极推进，这一过程叫做递推；这一过程相当于压栈一过程相当于压栈.2.回归回归:问题逐一解决，最后回到原问题，这一过问题逐一解决，最后回到原问题，这一过程叫做回归。这一过程相当于弹栈程叫做回归。这一过程相当于弹栈.本讲稿第五页，共二十八页一个简单的实例一个简单的实例n将将n个不同颜色的球个不同颜色的球,分别放到分别放到n个不同的盒子中去个不同的盒子中去,问有多少种放法问有多少种放法?n分析分析:显然所有的方法数为显然所有的方法数为 n!这样这样,对于任意输入的整数对于任意输入的整数n,我们只要算出我们只要算出n!即可即可n设设f(n)=n!,则有，则有，本讲稿第六页，共二十八页用递归实现Var n:integer;t:longint;function f(n:integer):longint;beginif n=0 then f:=1else f:=n*f(n-1)end;beginwrite(n=);readln(n);t:=f(n);writeln(n!=,t);end.本讲稿第七页，共二十八页N=3时的递归过程本讲稿第八页，共二十八页本讲稿第九页，共二十八页本讲稿第十页，共二十八页递归的表示nHanoi塔问题塔问题n进制转换问题进制转换问题n快速排序快速排序n归并排序归并排序n皇后问题皇后问题n背包问题背包问题n地图着色问题地图着色问题n本讲稿第十一页，共二十八页用递归实现回溯算法用递归实现回溯算法 回回溯溯法法也也叫叫试试探探法法，每每次次试试着着往往前前走走，一一直直走走到到不不通通，然然后后撤撤回回，重新试探重新试探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；本讲稿第十二页，共二十八页回溯法的几个重要因素回溯法的几个重要因素(1)状态状态:作为递归的值参。作为递归的值参。(2)边界条件边界条件:作为递归的结束条件。作为递归的结束条件。(3)递归范围递归范围:作为作为for循环的初值和终值。循环的初值和终值。(4)约束条件约束条件:满足解的条件。满足解的条件。(5)最优性要求：满足最优解的条件。最优性要求：满足最优解的条件。本讲稿第十三页，共二十八页N皇后问题 在在N*N的棋盘上放置的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置两个皇后），编程求解所有的摆放方法。任一对角线上不能放置两个皇后），编程求解所有的摆放方法。本讲稿第十四页，共二十八页基本思想基本思想n由于皇后的摆放位置不能通过某种公式来确定，因此对于由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置可以进行试探；每个皇后的摆放位置可以进行试探；n按行放置皇后，每一行放一皇后；按行放置皇后，每一行放一皇后；n对每一行所放置的皇后按列进行试探；对每一行所放置的皇后按列进行试探；n若某个位置能放，则放，否则试放下一个位置若某个位置能放，则放，否则试放下一个位置n若某一行没有任何一个位置可放，则表示前面的皇后没放好，若某一行没有任何一个位置可放，则表示前面的皇后没放好，需要回溯。需要回溯。n若若n个皇后都放好了，则得到了一个解。个皇后都放好了，则得到了一个解。本讲稿第十五页，共二十八页算法基本框架算法基本框架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;本讲稿第十六页，共二十八页边界条件设置边界条件设置n怎样判断某列放置了皇后怎样判断某列放置了皇后 a:array 1.MaxN of Boolean;竖线被控制标记竖线被控制标记n怎样判断某对角线上放置了皇后怎样判断某对角线上放置了皇后 b:array 2.MaxN*2 of Boolean;左上到右下斜线被控制标记左上到右下斜线被控制标记 c:array 1-MaxN.MaxN-1 of Boolean;左下到右上斜线被控制标记左下到右上斜线被控制标记本讲稿第十七页，共二十八页程序Procedure Try(i:integer)；var j:integer;begin if i=n+1 then print；for j:=1 to n do if aj and bi+j and ci-j then begin ai:=j;aj:=false;bi+j:=false;ci-j:=false;Try(i+1)aj:=true;bi+j:=true;ci-j:=true;end;end;本讲稿第十八页，共二十八页数字全排列问题：n任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。注意：数字不能重复，N由键盘输入（N=9）。本讲稿第十九页，共二十八页思考题思考题2:构造字串构造字串n生成长度为生成长度为n的字串，其字符从的字串，其字符从26个英文字母个英文字母的前的前p(p26)个字母中选取，使得没有相邻的个字母中选取，使得没有相邻的子序列相等。例如子序列相等。例如p=3，n=5时时 a b c b a满足条件满足条件 a b c b c不满足条件不满足条件输入：输入：n，p输出：所有满足条件的字串输出：所有满足条件的字串本讲稿第二十页，共二十八页分析分析n状态：状态：待扩展的字母序号i。n由于该变量的存储量太大，因此我们将s设为全局变量；n边界条件：边界条件：产生了一个满足条件的字串，即 i=n+1；n搜索范围：从搜索范围：从a开始的后p个字符；约束条件：约束条件：当前字串没有相邻子串相等的情况本讲稿第二十一页，共二十八页procedure solve(i:integer)；var j,k:integer；t:longint;begin if i=n+1 then 若产生了一个满足条件的字串，则输出若产生了一个满足条件的字串，则输出 begin writeln(s)；inc(t)；exit 回溯回溯 end；for k1 to p do 搜索每一个可填字母搜索每一个可填字母 begin ss+chr(64+k)；j1；检查当前字串是否符合条件检查当前字串是否符合条件 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 ji div 2 then solve(i+1)；若当前字串符合条件，则递归扩展下一个字母若当前字串符合条件，则递归扩展下一个字母 delete(s,length(s),1)恢复填前的字串恢复填前的字串 end;end;本讲稿第二十二页，共二十八页 递归与递推上楼梯问题上楼梯问题:n一个人想登上一个人想登上n级楼梯级楼梯,他上楼梯的方法有一步他上楼梯的方法有一步跨一级跨一级,也可一步跨两级也可一步跨两级,也可一步跨三级也可一步跨三级,问问他上到楼顶他上到楼顶,一共有多少种上楼梯的方法一共有多少种上楼梯的方法.本讲稿第二十三页，共二十八页n我们将上楼梯的方法用数字1，2，3表示，那么n如果只有1节楼梯，显然只有1种上楼的方法，方法为1。n如果只有2节楼梯，显然只有2种上楼的方法，方法为11，2。n如果只有3节楼梯，显然只有4种上楼的方法，方法为111，12，21，3。分析本讲稿第二十四页，共二十八页多于3节楼梯呢?n假设有n节楼梯,设 f(n)表示上节楼梯的方法数，显然有本讲稿第二十五页，共二十八页算法nFunction f(n:integer):longint;Begin if n=1 then f:=1;if n=2 then f:=2;if n=3 then f:=4;if n3 then f:=f(n-1)+f(n-2)+f(n-3);End;本讲稿第二十六页，共二十八页是否我们可以满足了呢？n看下面的算法(递推)：nFunction 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;本讲稿第二十七页，共二十八页对比！n算法采用递归的形式，由于递归要反复压栈算法采用递归的形式，由于递归要反复压栈和弹栈，使得操作要多很多，并且受到空间限和弹栈，使得操作要多很多，并且受到空间限制，时间复杂度为制，时间复杂度为O(3n)n算法采用递推的形式，只是利用公式从前往算法采用递推的形式，只是利用公式从前往后逐步递推后逐步递推,采用变量之间相互传递结果，时采用变量之间相互传递结果，时间复杂度为间复杂度为(n)n实践证明，采用算法比算法快很多，而算实践证明，采用算法比算法快很多，而算法最多做到法最多做到=20就巨慢了就巨慢了,算法算法2可做得巨可做得巨大。大。本讲稿第二十八页，共二十八页