《数据结构与算法栈和队列剖析.pptx》由会员分享，可在线阅读，更多相关《数据结构与算法栈和队列剖析.pptx（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1/39第六讲 递归算法本讲知识点：(1)了解递归的特点(2)掌握递归向非递归转换的方法(3)了解栈在处理递归问题中的应用重点：递归思路分析难点：栈在递归向非递归转换中的应用第1页/共39页2/39一、递归递归是程序设计中最有力的方法之一。优点：采用递归编出的程序简洁、清晰，程序结构符合结构化程序设计，可读性好。问题：编译程序是如何处理这类带有递归调用功能的程序的？如果使用了无递归功能的程序设计语言，应该如何设计和实现这类程序呢？第2页/共39页3/39数学中常常利用递归手段来定义一些概念，如求阶乘的运算。n的阶乘定义为：n*(n1)!n0n!=1n=0求阶乘第3页/共39页4/39递归算法l
2、ongf(intn)longp;if(n=0)return1;elsereturnn*f(n-1);voidmain()longx=f(4);coutx;递归项终止项第4页/共39页5/39longf(intn)longp;if(n=0)return1;elsereturnn*f(n-1);voidmain()longx=f(3);coutx;123n=3 4567longf(intn)longp;if(n=0)return1;elsereturnn*f(n-1);n=2 891011longf(intn)longp;if(n=0)return1;elsereturnn*f(n-1);n=1
3、12131415longf(intn)longp;if(n=0)return1;elsereturnn*f(n-1);n=0 16171819带回了12122带回了12324带回了627282920带回了22526第5页/共39页6/39u调用前：调用前：（1）将所有的）将所有的实参、返回地址实参、返回地址传递给被调用函数保存传递给被调用函数保存（2）为被调用函数的局部变量）为被调用函数的局部变量分配存储分配存储区区（3）将）将控制转移控制转移到被调用函数入口。到被调用函数入口。u调用后：调用后：（1）保存保存被调用函数的计算被调用函数的计算结果结果。（2）释放释放被调用函数的被调用函数的数据
4、数据区区（3）依照被调用函数保存的返回地址将）依照被调用函数保存的返回地址将控制转移控制转移到调用到调用函数函数函数调用的过程第6页/共39页7/39整数划分问题递归法求解排列组合u设m.n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。u例：f(5,3)=5，5种表示方式：3+23+1+12+2+12+1+1+11+1+1+1+1参看s3/partition.cpp第7页/共39页8/39相同的问题相同的问题:m个苹果放到个苹果放到n个盘子上，个盘子上，问有多少种放法问有多少种放法?整数划分问题第8页/共39页9/39递归出口：递归出口：没有苹果或者盘子只剩
5、下没有苹果或者盘子只剩下1个个则只有则只有1种方法种方法整数划分问题5个苹果放到1个盘子里，只有1种放法第9页/共39页10/39递归项：递归项：(1)苹果数苹果数少于少于盘子数盘子数等价于去掉多余的盘子等价于去掉多余的盘子整数划分问题5个苹果放到6个盘子里的放法，等价于5个苹果放到5个盘子里的放法第10页/共39页11/39递归项：递归项：(2)苹果数苹果数多于多于盘子数盘子数a：至少有：至少有1个盘子空着的放法个盘子空着的放法加上加上b：所有盘子都有苹果的放法：所有盘子都有苹果的放法整数划分问题a：5个苹果放到4个盘子里，至少有1个盘子空着的放法，就是5个苹果放到3个盘子里的放法第11页/
6、共39页12/39递归项：递归项：(2)苹果数苹果数多于多于盘子数盘子数a：至少有：至少有1个盘子空着的放法个盘子空着的放法加上加上b：所有盘子都有苹果的放法：所有盘子都有苹果的放法整数划分问题b：既然所有盘子都有苹果，可以把每个盘子里的苹果拿走一个，就是1个苹果放到4个盘子的放法第12页/共39页13/39intf(intm,intn)if(m=0|n=1)return;/没有苹果或者盘子剩下没有苹果或者盘子剩下1个个if(mn)return;/苹果数少于盘子数，只需要相同的盘子数苹果数少于盘子数，只需要相同的盘子数就足够了就足够了if(m=n)return1+;/苹果数和盘子数相等，苹果数
7、和盘子数相等，b所有盘子都有苹果，所有盘子都有苹果，和和a至少有至少有1个盘子空着，可取消这条语句个盘子空着，可取消这条语句returnf(m,n-1)+f(m-n,);/苹果数多于盘子数，苹果数多于盘子数，a+b递归实现第13页/共39页14/39intf(intm,intn)if(m=0|n=1)return1;if(m1简单递归问题u例如：求P3(3)P0(3)=1P1(3)=3P1(3)=3P2(3)=13P2(3)=(3*3*3-1)/2=13P3(3)=(5*3*13-2*3)/3=63第17页/共39页18/39floatp(intn,floatx)floatp1,p2;if(n
8、=0)return(1.0);/终止条件elseif(n=1)return(x);/终止条件elsep1=(2*n-1)*x*p(n-1,x);p2=(n-1)*p(n-2,x);return(p1-p2)/n);递归实现第18页/共39页19/39分析问题用两个变量pre1,pre2，记录递推关系的子问题的解p(i,x)=(2i-1)x p(i-1,x)(i-1)p(i-2,x)/ipre1=p(i-2,x)pre2=p(i-1,x)当求出第i阶多项式的值后，i值加1，需要修改pre1和pre2。则用pre1记录pre2当前的值，而用pre2记录新求出的多项式的值。直到i=n。递推关系式：第
9、19页/共39页20/39floatp(intn,floatx)floatpre1,pre2,a,b,valuep;inti;if(n=0)return(1.0);elseif(n=1)return(x);/接下一页非递归实现参看s3/legendre.cpp第20页/共39页21/39elsepre1=1.0;pre2=x;for(i=2;inext;deletep;p=head;算法分析第27页/共39页28/39voidpush(intxx,intyy,charddirection)node*new_node;new_node=newnode;if(new_node!=NULL)new_
10、node-x=xx;new_node-y=yy;new_node-direction=ddirection;new_node-next=NULL;if(head=NULL)head=new_node;elsenew_node-next=head;head=new_node;elsecoutnext;xx=p-x;yy=p-y;deletep;elsecoutn因为栈已空导致本次出栈失败n;returnhead;算法分析第29页/共39页30/39voidprint()/输出栈内元素if(head!=NULL)node*p=head;while(p!=NULL)cout“”x“”y;cout“”
11、directionnext;elsecoutn栈为空，打印失败n;/栈类的定义结束算法分析第30页/共39页31/39voidCreateMaze()/创建迷宫intmax_way=MAX_X*MAX_Y;/400intx,y;for(x=0;xMAX_X;x+)for(y=0;yMAX_Y;y+)mazexy=1;/019都是墙壁srand(unsigned)time(NULL);for(inti=0;i=max_way;i+)x=rand()%(MAX_X-2)+1;y=rand()%(MAX_Y-2)+1;mazexy=0;/0表示可走的路maze11=0;/入口mazeMAX_X-2M
12、AX_Y-2=0;/1818出口maze01=8;mazeMAX_X-1MAX_Y-2=0;/maze1918第31页/共39页32/39voidPrintMaze()/输出迷宫的当前状态输出迷宫的当前状态intx,y;system(“cls”);coutendl;for(x=0;xMAX_X;x+)for(y=0;yMAX_Y;y+)if(mazexy=0)cout;continue;/通路通路if(mazexy=1)cout;continue;/墙墙if(mazexy=2)cout;continue;/死胡同死胡同if(mazexy=3)cout;continue;/向下走向下走if(ma
13、zexy=4)cout;continue;/向右走向右走if(mazexy=5)cout;continue;/向左走向左走if(mazexy=6)cout;continue;/向上走向上走if(mazexy=7)cout;continue;/当前站立当前站立位置位置if(mazexy=8)cout;continue;/通路通路coutendl;Sleep(200);/延时函数延时函数第32页/共39页33/39voidmain()CreateMaze();/创建迷宫PrintMaze();/输出当前迷宫的初始状态stack_for_mazestack;/定义一个栈的对象，用来记录行走路线mov
14、e(stack);/行走中PrintMaze();/输出迷宫的最终状态stack.print();算法分析第33页/共39页34/39voidmove(stack_for_maze&s)intx=1,y=1;/出发点while(1)mazexy=2;if(mazexy+1=0)/s.push(x,y,R);/当前位置压栈mazexy=4;y=y+1;/向右走到一个新位置mazexy=7;PrintMaze();if(x=MAX_X-1)&(y=MAX_Y-2)s.push(x,y,*);coutn成功走出！n;return;elsecontinue;第34页/共39页35/39/省略其余三个方
15、向的试探代码/上下左右均不通则回退，即出栈一次，/如果出栈导致栈空则说明无路可走了！if(s.pop(x,y)=NULL&mazex-1y!=0&mazexy-1!=0&mazexy+1!=0&mazex+1y!=0)coutn没有找到合适路径！n;maze01=7;/没有找到路，站在起点！if(maze11!=1)maze11=2;return;/while/move第35页/共39页36/39设定当前位置的初值为入口位置；do若当前位置可通，则将当前位置插入栈顶；若该位置是出口位置，则算法结束；否则切换当前位置的东邻方块为新的当前位置；否则while(栈不空）；求迷宫中一条从入口到出口的路
16、径的算法：求迷宫中一条从入口到出口的路径的算法：第36页/共39页37/39若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转 找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；/从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；若栈空，则表明迷宫没有通路。求迷宫中一条从入口到出口的路径的算法：求迷宫中一条从入口到出口的路径的算法：第37页/共39页38/39本讲小结（1）递归的定义等（2）能通过分析将递归算法转换为非递归（3）熟悉迷宫程序的运行流程抓紧复习哦！实验1顺序表的内容部分开放了！第38页/共39页39/39感谢您的观看！第39页/共39页