递归和搜索算法.pptx

递归思想和搜索算法数模组 费鹏;递归思想和搜索算法;考虑一下刚才那个函数的运行过程;为什么能用递归解决这个问题？;关注最后一个条件，即可能存在也可能不存在没放苹果的盘子。; 介绍几种数据结构;栈;栈的基本操作;队列;队列操作;结点：包含一个数据元素及若干指向其子树的分支。 结点的度：结点拥有的子树个数。;路径与路径长度：路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。 子女结点、父母结点、祖先、后继 ;图 G 是由两个集合顶点集 V(G) 和边集 E(G) 组成的，记作G=( V(G)，E(G) )，简称G=(V，E)。;深度优先搜索;伪代码;下面是一棵搜索树;对图的深度优先遍历;对图的深度优先遍历;上图的搜索树;如何实现深度优先搜索;伪代码;实际应用：八皇后问题;如何实现：;int map[8];//记录棋子的位置 void DFS(int l){ int i, j; if(l = 8){//搜索到第8层以上时得到一个解 for(i = 0;i 8;i ++) printf(%d, map[i]); printf(\n); } for(i = 1;i = 8;i ++)//对每一个可行子节点进行深搜 { for(j = 0;j l;j ++)//判断是否可行 { if(map[j] == i || map[j] + j == l + i || map[j] - j == i - l) break; } if(j = l) { map[l] = i;//记录棋子的位置 DFS(l + 1); map[l] = 0;//返回上一层时要清空这层的信息 } } } ;考虑一个新问题：;Bool DFS(int i , int j) { step++; route[step]=(i,j) //position visited[i][j]=true; if(step==n*m) return true; for(int n=1;n9;n++){ path(i,j,n); //How will the rider move //x,y is the point that has been moved if(!map[x][y]x=1x=my=Ay=n+A-1) if(DFS(x,y)) return true; } map[i][j]=false; step--; return false; };广度优先搜索;伪代码;下面是一棵搜索树;图的广度优先算法;对图的广度优先遍历;上图的搜索树;如何实现广度优先搜索？;再来一次;伪代码;一个问题：;类似求最短路径问题 依旧是树状结构;struct P{ int x; int d; };//结构体P存储节点的值和深度 int visited[100010];//判断节点是否遍历过的数组 struct P queue[100010]; int BFS(int N, int K){ int rear = 0, font = 0, L, d;//rear指向尾，font指向头 queue[rear].x = N; queue[rear].d = 0; rear ++; while(1){ L = queue[font].x;//从队列中获得节点 d = queue[font].d; 头指针向后移一位 是否满足条件？ visited[L] = 1;; if(L * 2 = 100000 L * 2 = 0 map[L * 2] != 1){ // 该点进入队列 //visited[]数组L;// //尾指针向后移动 }//产生自乘2的节点，入队 if(L + 1 = 100000 L + 1 = 0 map[L + 1] != 1){ }产生自加1的节点，入队 if(L - 1 = 0 map[L - 1] != 1){ }产生自减1的节点，入队 } };考虑一个新问题： 八数码问题 描述：把下图的状态;深搜与广搜的比较;作业