递归与回溯精选PPT.ppt

《递归与回溯精选PPT.ppt》由会员分享，可在线阅读，更多相关《递归与回溯精选PPT.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、递归与回溯第1页，此课件共28页哦重点内容n递归的概念递归的概念n递归的表示递归的表示n递归实现方法递归实现方法n用递归实现简单回溯算法用递归实现简单回溯算法n实现递归时应注意的几个方面实现递归时应注意的几个方面n递归与递推的区别和联系递归与递推的区别和联系第2页，此课件共28页哦递归的概念n先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说山上有座庙，庙里有一个老和尚在给

2、小和尚讲故事，故事里说。象这样，一个对象部分地由它自己组成，或者是按它自。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之为递归。己定义，我们称之为递归。n一个函数、过程、概念或数学结构，如果在其定义或说一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。数直接或者间接调用自己，就被称为递归调用。第3页，此课件共28页哦递归的特点与应用场合递归的特点与

3、应用场合n用递归方法编写的问题解决程序具有结构清晰，可读用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法题的解决方法是递归形式的时候，往往采用递归算法来解决。来解决。第4页，此课件共28页哦递归的实现方法递归的实现方法递归是借助于一个递归工作递归是借助于一个递归工作栈栈来实现来实

4、现.1.递推递推:问题向一极推进，这一过程叫做递推；这问题向一极推进，这一过程叫做递推；这一过程相当于压栈一过程相当于压栈.2.回归回归:问题逐一解决，最后回到原问题，这一过问题逐一解决，最后回到原问题，这一过程叫做回归。这一过程相当于弹栈程叫做回归。这一过程相当于弹栈.第5页，此课件共28页哦一个简单的实例一个简单的实例n将将n个不同颜色的球个不同颜色的球,分别放到分别放到n个不同的盒子中去个不同的盒子中去,问有多少种放法问有多少种放法?n分析分析:显然所有的方法数为显然所有的方法数为 n!这样这样,对于任意输入的整数对于任意输入的整数n,我们只要算出我们只要算出n!即可即可n设设f(n)=

5、n!,则有，则有，第6页，此课件共28页哦用递归实现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.第7页，此课件共28页哦N=3时的递归过程第8页，此课件共28页哦第9页，此课件共28页哦第10页，此课件共28页哦递归的表示nHanoi塔问题塔问题n进制转换问题进制转换问题n快速排序快速排序n归并排序归并排序n皇后问题皇后问题n背包问题背包问题n地图

6、着色问题地图着色问题n第11页，此课件共28页哦用递归实现回溯算法用递归实现回溯算法 回回溯溯法法也也叫叫试试探探法法，每每次次试试着着往往前前走走，一一直直走走到到不不通通，然然后后撤撤回，重新试探回，重新试探procedure run（当前状态）；（当前状态）；var i：integer；begin if 当前状态为边界当前状态为边界 then begin if 当前状态为最佳目标状态当前状态为最佳目标状态 then 记下最优结果；记下最优结果；exit；回溯回溯 end；for i算符最小值算符最小值 to 算符最大值算符最大值 do begin 算符算符i作用于当前状态，扩展出一个子状

7、态；作用于当前状态，扩展出一个子状态；if(子状态满足约束条件子状态满足约束条件)and(子状态满足最优性要求子状态满足最优性要求)then run(子状态子状态)end；end；第12页，此课件共28页哦回溯法的几个重要因素回溯法的几个重要因素(1)状态状态:作为递归的值参。作为递归的值参。(2)边界条件边界条件:作为递归的结束条件。作为递归的结束条件。(3)递归范围递归范围:作为作为for循环的初值和终值。循环的初值和终值。(4)约束条件约束条件:满足解的条件。满足解的条件。(5)最优性要求：满足最优解的条件。最优性要求：满足最优解的条件。第13页，此课件共28页哦N皇后问题 在在N*N的

8、棋盘上放置的棋盘上放置N个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一个皇后而彼此不受攻击（即在棋盘的任一行，任一列和任一对角线上不能放置两个皇后），编程求解所有的摆放方法。对角线上不能放置两个皇后），编程求解所有的摆放方法。第14页，此课件共28页哦基本思想基本思想n由于皇后的摆放位置不能通过某种公式来确定，因此对由于皇后的摆放位置不能通过某种公式来确定，因此对于每个皇后的摆放位置可以进行试探；于每个皇后的摆放位置可以进行试探；n按行放置皇后，每一行放一皇后；按行放置皇后，每一行放一皇后；n对每一行所放置的皇后按列进行试探；对每一行所放置的皇后按列进行试探；n若某个位置能放，则放，否则

9、试放下一个位置若某个位置能放，则放，否则试放下一个位置n若某一行没有任何一个位置可放，则表示前面的皇后没若某一行没有任何一个位置可放，则表示前面的皇后没放好，需要回溯。放好，需要回溯。n若若n个皇后都放好了，则得到了一个解。个皇后都放好了，则得到了一个解。第15页，此课件共28页哦算法基本框架算法基本框架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 放

10、置第放置第i个皇后；个皇后；对放置皇后的位置进行标记；对放置皇后的位置进行标记；Try（i+1）对放置皇后的位置释放标记；对放置皇后的位置释放标记；end;end;第16页，此课件共28页哦边界条件设置边界条件设置n怎样判断某列放置了皇后怎样判断某列放置了皇后 a:array 1.MaxN of Boolean;竖线被控制标记竖线被控制标记n怎样判断某对角线上放置了皇后怎样判断某对角线上放置了皇后 b:array 2.MaxN*2 of Boolean;左上到右下斜线被控制标记左上到右下斜线被控制标记 c:array 1-MaxN.MaxN-1 of Boolean;左下到右上斜线被控制标记左

11、下到右上斜线被控制标记第17页，此课件共28页哦程序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;第18页，此课件共28页哦数字全排列问题：n任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方

12、式：123，132，213，231，312，321。注意：数字不能重复，N由键盘输入（N=9）。第19页，此课件共28页哦思考题思考题2:构造字串构造字串n生成长度为生成长度为n的字串，其字符从的字串，其字符从26个英文字母个英文字母的前的前p(p26)个字母中选取，使得没有相邻的个字母中选取，使得没有相邻的子序列相等。例如子序列相等。例如p=3，n=5时时 a b c b a满足条件满足条件 a b c b c不满足条件不满足条件输入：输入：n，p输出：所有满足条件的字串输出：所有满足条件的字串第20页，此课件共28页哦分析分析n状态：状态：待扩展的字母序号i。n由于该变量的存储量太大，因此

13、我们将s设为全局变量；n边界条件：边界条件：产生了一个满足条件的字串，即 i=n+1；n搜索范围：从搜索范围：从a开始的后p个字符；约束条件：约束条件：当前字串没有相邻子串相等的情况第21页，此课件共28页哦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+

14、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;第22页，此课件共28页哦 递归与递推上楼梯问题上楼梯问题:n一个人想登上一个人想登上n级楼梯级楼梯,他上楼梯的方法有一步他上楼梯的方法有一步跨一级跨一级

15、,也可一步跨两级也可一步跨两级,也可一步跨三级也可一步跨三级,问问他上到楼顶他上到楼顶,一共有多少种上楼梯的方法一共有多少种上楼梯的方法.第23页，此课件共28页哦n我们将上楼梯的方法用数字1，2，3表示，那么n如果只有1节楼梯，显然只有1种上楼的方法，方法为1。n如果只有2节楼梯，显然只有2种上楼的方法，方法为11，2。n如果只有3节楼梯，显然只有4种上楼的方法，方法为111，12，21，3。分析第24页，此课件共28页哦多于3节楼梯呢?n假设有n节楼梯,设 f(n)表示上节楼梯的方法数，显然有第25页，此课件共28页哦算法nFunction f(n:integer):longint;Beg

16、in 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;第26页，此课件共28页哦是否我们可以满足了呢？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;第27页，此课件共28页哦对比！n算法采用递归的形式，由于递归要反复压栈算法采用递归的形式，由于递归要反复压栈和弹栈，使得操作要多很多，并且受到空间限和弹栈，使得操作要多很多，并且受到空间限制，时间复杂度为制，时间复杂度为O(3n)n算法采用递推的形式，只是利用公式从前往算法采用递推的形式，只是利用公式从前往后逐步递推后逐步递推,采用变量之间相互传递结果，时采用变量之间相互传递结果，时间复杂度为间复杂度为(n)n实践证明，采用算法比算法快很多，而算实践证明，采用算法比算法快很多，而算法最多做到法最多做到=20就巨慢了就巨慢了,算法算法2可做得巨可做得巨大。大。第28页，此课件共28页哦