![课件-第3章附加节递归_第1页](http://file4.renrendoc.com/view/62035a10bf95ad179c957543a826eeb0/62035a10bf95ad179c957543a826eeb01.gif)
![课件-第3章附加节递归_第2页](http://file4.renrendoc.com/view/62035a10bf95ad179c957543a826eeb0/62035a10bf95ad179c957543a826eeb02.gif)
![课件-第3章附加节递归_第3页](http://file4.renrendoc.com/view/62035a10bf95ad179c957543a826eeb0/62035a10bf95ad179c957543a826eeb03.gif)
![课件-第3章附加节递归_第4页](http://file4.renrendoc.com/view/62035a10bf95ad179c957543a826eeb0/62035a10bf95ad179c957543a826eeb04.gif)
![课件-第3章附加节递归_第5页](http://file4.renrendoc.com/view/62035a10bf95ad179c957543a826eeb0/62035a10bf95ad179c957543a826eeb05.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
栈和队3栈和队3.3用举例迷宫求栈的应用:递给自己定义,则称这个对象是递归的;若一个过程直接地或间接地调用自己,则称这个定义是递归n!
当n0n(n
当n1longFactorial(longn){if(n==0)returnelsereturnn*Factorial(n-}求解阶n的过main:参数 计算 返回递 结归 参数 计算 返回 果调 返用 参数 计算 返回 回参数 计算 返回参数 直接定值= 返回数据结构是递归fftemplate<classvoidPrint(ListNode<E>*f){if(f->next==NULL)cout<<f->data<<elsePrint(f-}a4 template<classvoidPrint(ListNode<E>*f,Evalue){if(f!=NULL)if(f->data==cout<<f->data<<endl;elsePrint(f->next,value);}递归找含xfffffx问题的解法是递归例,汉诺塔(TowerofHanoi)问题的解法:n1,则将这一个盘子直接从A柱移到C柱上。否则,执行以下三步:C柱做过渡,将A(n-1)个盘子移到B柱上:将AC用AB(n-1)个盘子移到C柱上。#includevoidHanoi(intn,charA,charB,charC)//if(n==1)cout<<"move"<<A<<"to<<C<<else{Hanoi(n-1,A,C,cout<<"move"<<A<<"to"<<<<Hanoi(n-1,B,A,}}A-A-
A-
A-A-
C-
B-B-
A-—分而治之策略(分治法构成递归的条Procedure<name>(<parameterlist>)if(<initialcondition>) return(initialvalue); //return(<name>(parameterexchange}递归过程与递归工作递归调 (n- (n- 返回次
longFactorial(longn){inttemp;if(n==0)returnelsetemp=n*Factorial(n-return}voidmain(){intn;n=}递归工作参参框函数递归时的活动记调用函数
<下一条指令Function(<参数表返回地址返回地址(下一条指令参计算Fact时活动记录的内4//参数返回值4//return36return//22return//36return//22return//11return//01return//递归过程改为非递归过递归过程简洁、易编、易递归过程效率低,重复计算改为非递归过程的目的是提高效这时不必返回后计算斐波那契数列的函数Fib(n)的定(n)
nFib(n1)
nF00,F11,F21,F32,F43,F5求解斐波那契数列的递归算longFib(longn)if(n<=1)returnelsereturnFib(n-1)+Fib(n-}
调用次 NumCall(k)=2*Fib(k+1)-单向递归用迭代法实longFibIter(longn){if(n<=1)returnn;longtwoback=0, oneback=1, for(inti=2;i<=n;i++){Current=twoback+twoback= oneback=}return}尾递归用迭代法实voidrecfunc(intA[], intn){if(n>=0){cout<<A[n]<<“”;recfunc(A,}}voidsterfunc(intA[],intn)while(n>=0){cout<< "<<A[n]<<n--}}递归与回n皇后问nn列的国际象棋棋盘上,若两个皇则称为它们为互相攻击。n皇后问题是指找到这n个皇后的互不攻击的布局。 2#4#1#5#k=n+i-j-0123
0#
1#3#5#0#2#6#解题思安放i行0n-1j0,n-1在j列其它皇后,则出现攻击,撤消在第j列j列安放的皇后不动,递归安放第i+1行皇后。4 col[n]:col[i]i列是否安放了 md[2n-1]md[kk条主对角线 sd[2n-1sd[kk条次对角线是q[nq[iivoidQueen(inti)for(intj=0;j<n;j++)if(ij列没有攻击)ij列安放皇后if(in-1输出一个布局elseij列的皇后}}}voidQueen(inti)for(intj=0;j<n;j++)if(!col[j]&&!md[n+i-j-1]&&{/*ijcol[j]=md[n+i-j-1]=sd[i+j]=q[i]=/*ij列安放皇后if(in-1) /*输出一个布局for(intk=0;k<n;cout<<k<<q[k]<<‘,’;cout<<endl;}elsecol[j]=md[n+i-j-1]=sd[i+j]=0;q[i]=0; /*ij列的皇后*/}}}4532迷宫问45321(入口1(入口234(堵死3(堵死5(堵死 回 退到 右拐弯 左拐弯进到(出口
左直右小行行行型宫型数000700数0007007据交通路口结构定交通路口结构定structIntersection{intleft;intforward;intright;}#include<iostream.h>#include<fstream.h>#include<stdlib.h>classMaze{intMazeSize;intEXIT;Intersection*intsec;Maze(charintTraverseMaze(int}Maze::Maze(char*filename)//filenameifstreamfin;fin.open(filename,ios::in|if(!fin){cerr迷宫数据文件<<<<“打不开”<<}fin>> intsec=new//for(inti=1;i<=MazeSize;fin>>intsec[i].left>>>>fin>> //}迷宫漫游与求解算intMaze::TraverseMaze(intCurrentPos)if(CurrentPos0) //1if(CurrentPos==EXIT){ cout<<C
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2023九年级语文上册 第二单元 综合性学习 君子自强不息教案 新人教版
- 统编版《道德与法治》六年级下册第2课《学会宽容》精美课件(第2课时)
- 专题5.11 相交线与平行线章末八大题型总结(拔尖篇)(人教版)(解析版)
- 砂(砂石)换土回填单元工程质量评定表
- 海上船抛石方筑堤施工工法
- 七年级数学上册数学 6.3余角、补角、对顶角(三大题型)(解析版)
- 结构力学优化算法:遗传算法(GA):遗传算法的收敛性分析
- 结构力学数值方法:谐波平衡法:高级谐波平衡法技术
- 2019年良品铺子公司财务分析总结性研究报告
- 2023华宁县国有资本运营集团有限责任公司招聘试题及答案解析
- 2024年秋季人教版七年级上册历史全册教学课件新教材
- DB11T 489-2024 建筑基坑支护技术规程
- 第1.1课-七律二首-送瘟神-【中职专用】高二语文同步备课课件(高教版2023职业模块)
- 小学数学五年级口算训练——分数乘除法
- 大直径泥水平衡盾构掘进施工重难点分析及应对措施
- 行车系统电气设备及控制思路教学课件
- DCS操作基本知识试题
- 系统功能语法-投射小句
- 铜键合丝资料学习文献综述
- 幼儿园园长负责制实施方案
- (完整版)英语中48个音标对应的字母组合
评论
0/150
提交评论