递归与搜索算法ppt课件.ppt

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

1、递归思想和搜索算法数模组费鹏递归思想和搜索算法递归递归的定义递归的特点深度优先搜索深度搜索定义深搜过程广度优先搜索递归定义在调用一个函数的过程中又出现直接或间接地调用该函数本身，成为函数的递归调用。例如：intfun(intn){intt;if(n==1)t=1;elset=n*fun(n-1);returnt;}递归考虑一下刚才那个函数的运行过程以起始n为5为例有fun(5)调用fun(4),fun(4)调用fun(3)…,直到n=1为止然后依次向上一层返回值。n=5t=5*fun(4)n=4t=4*fun(3)n=3t=3*fun(2)n=2

2、t=2*fun(1)n=1t=1考虑若在return语句前加入printf(“%d”,t)，会有怎么的输出结果输出1输出2输出6输出24输出120为什么能用递归解决这个问题？阶乘问题可以分解为规模更小的子问题，用同样的方法可以解子问题可以很容易的得到关于阶乘问题的递归公式：1,n=0,1n!=n*(n-1)!,n>1考虑一个新问题：现在有n个苹果和m个盘子，把这些苹果都放到盘子里，可以有盘子里一个苹果也不放，有多少种摆放方法。关注最后一个条件，即可能存在也可能不存在没放苹果的盘子。结果可为以下两种情况的和有空盘子的情况，则问题可简化为n个苹果放m

3、–1个盘子。没有空盘子的情况，则问题可简化为n–m个苹果放m个盘子可以得到递归公式，total总数1,n=0orm=1total(n,m)total(n,n),n

4、是否为空。●Push(Titem)——将元素item放到栈的顶部。●Pop(T&item)——取出栈顶部的元素。●Top(T&item)——获取栈顶部的元素，但不删除该元素。●IsFull()——判断栈是否已满队列先进先出（firstin/firstout,FIFO）线性结构。队首：删除端队尾：插入端第2章线性表排队买票队列操作Clear（）—清空队列。IsEmpty（）—判断队列是否为空。IsFull（）—判断队列是否已满EnQueue（Titem）—队列的尾部加入元素item。DeQueue（T&item）—取出队列的第一个元素。GetFro

5、nt（T&item）—返回队列的第一个元素，但不移去它。第2章线性表结点：包含一个数据元素及若干指向其子树的分支。结点的度：结点拥有的子树个数。树的基本术语路径与路径长度：路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。子女结点、父母结点、祖先、后继树的基本术语图G是由两个集合顶点集V(G)和边集E(G)组成的，记作G=(V(G)，E(G))，简称G=(V，E)。ABCDEABCDEABCDEV(vertex)是顶点的有穷非空集合E(edge)是两个顶点之间的关系，即边的有穷集合图的定义和基本术语深度优先搜索递归递归的定义递归的特点深

6、度优先搜索深度搜索定义深搜过程广度优先搜索深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进。当不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。伪代码VoidDFS(intV)//GivenangraphG(V,E)withnverticesandanarrayvisited[]initially//settozero,thisalgorithmvisitsallverticesreachablefromv.Gand//visit

7、ed[]areglobal.{visited[v]=1;foreachvertexwadjacentfromV{if(!visited[w])DFS(w);}}下面是一棵搜索树12354678910对图的深度优先遍历图的深度优先搜索中，我们从定点v开始，标记它为已经到达（已访问）。这时，顶点v称为未考察的点。当已经访问过某个顶点的所有相邻定点后，在算法中这个顶点称为已经考察的顶点。图的深度优先搜索是指，只要到达一个新的定顶点，顶点v的考查就暂停，新的顶点u的考查开始。当这个新的顶点考察结束后，继续顶点v的考查。当所有可达定点被全部考察结束后，搜索

8、停止。对图的深度优先遍历ADBCFEGHI上图的搜索树ABCEDHFIG如何实现深度优先搜索递归可以很方便地解决对某个一个节点的深度优先