递归与回溯法课件.ppt

《递归与回溯法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归与回溯教案朱全民递归什么是递归？先看大家都熟悉的一个民间故事：从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说，从前有座山，山上有座庙，庙里有一个老和尚在给小和尚讲故事，故事里说……。象这样，一个对象部分地由它自己组成，或者是按它自己定义，我们称之为递归。一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。递归的概念与应用递归过程是借助于一个递归工作栈来实现的问题向一极推进，这一过程叫做递推；问题

2、逐一解决，最后回到原问题，这一过程叫做回归。递归的过程正是由递推和回归两个过程组成。递归的概念与应用用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识，只不过初学者要建立起递归概念不十分容易。我们先从一个最简单的例子导入。递归及其实现用递归算法求

3、n!定义：函数fact(n)=n!fact(n-1)=(n-1)!则有fact(n)=nfact(n-1)已知fact(1)=1编写如下递归程序varn:integer;t:longint;functionfac(n:integer):longint;beginifn=0thenfac:=1elsefac:=n*fac(n-1)end;beginwrite(‘n=’);readln(n);t:=fac(n);writeln(‘n!=’,T);end.N=3时的递归过程这相当于从菜心“推到”外层。递归算法的出发点不放在初始条件上，放在求解的目标上，从所

4、求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。就本例而言，读者会认为递归算法可能是多余的，费力而不讨好。但许多实际问题不可能或不容易找到显而易见的递推关系，这时递归算法就表现出了明显的优越性。下面我们将会看到，递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，具有良好的可读性，易于理解.许多看来相当复杂，或难以下手的问题，如果能够使用递归算法就会使问题变得易于处理。搜索的本质一、两种题型：1.简明的数学模型揭示问题本质。对于这一类试题，我们尽量用解析法求解。2.对给定的问题建立数学模型，或即使有一定的数学模型，但采

5、用数学方法解决有一定困难。对于这一类试题，我们只好用模拟或搜索求解。二、搜索的本质：搜索的本质就是逐步试探，在试探过程中找到问题的三、搜索问题考察的范围1.算法的实现能力2.优化算法的能力简单回溯法N皇后问题背包问题寻找国都名……回溯法回溯法也是搜索算法中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优秀搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。procedurerun（当前状态）；vari：integer；beginif当前状

6、态为边界thenbeginif当前状态为最佳目标状态then记下最优结果；exit；{回溯}end；fori←算符最小值to算符最大值dobegin算符i作用于当前状态，扩展出一个子状态；if(子状态满足约束条件)and(子状态满足最优性要求)thenrun(子状态)end；end；在应用回溯法求所有路径的算法框架解题时，应考虑如下几个重要因素：⑴定义状态：即如何描述问题求解过程中每一步的状况。为了精简程序，增加可读性，我们一般将参与子结点扩展运算的变量组合成当前状态列入值参，以便回溯时能恢复递归前的状态，重新计算下一条路径；⑵边界条件：即在什么情况

7、下程序不再递归下去。如果是求满足某个特定条件的一条最佳路径，则当前状态到达边界时并非一定意味着此时就是最佳目标状态。因此还须增加判别最优目标状态的条件；⑶搜索范围：在当前状态不满足边界条件的情况下，应如何设计算符值的范围。换句话说，如何设定for语句中循环变量的初值和终值。⑷约束条件和最优性要求：当前扩展出一个子结点后应满足什么条件方可继续递归下去；如果是求满足某个特定条件的一条最佳路径，那么在扩展出某个子状态后是否继续递归搜索下去，不仅取决于子状态是否满足约束条件，而且还取决于子状态是否满足最优性要求。⑸参与递归运算的参数：将参与递归运算的参数设为

8、递归子程序的值参或局部变量。若这些参数的存储量大（例如数组）且初始值需由主程序传入，为避免内存溢出，则必须将