栈实现递归 课件_第1页
栈实现递归 课件_第2页
栈实现递归 课件_第3页
栈实现递归 课件_第4页
栈实现递归 课件_第5页
已阅读5页，还剩8页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

栈实现递归CONTENTS递归的涵义汉诺塔问题问题分析

用栈实现在运行的过程中调用自己。要素1子问题须与原始问题为同样的事，且更为简单要素2不能无限制地调用本身，须有个出口，化简为非递归状况处理递归的涵义递归算法一般用于解决三类问题第一类第三类第二类数据的定义是按递归定义的问题解法按递归算法实现。这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单数据的结构形式是按递归定义的。由于结构本身固有的递归特性，则它们的操作可递归地描述。Fibonacci函数二叉树、广义表Hanoi问题递归算法的经典问题

n!字符串全排列八皇后问题hanoi

问题来源问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。问题描述有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动hanoi的输入柱子名开始端a目的端b借助端c盘子数nhanoi(intn,chara,charb,charc)hanoi的输出移动过程按照先后移动的盘子编号n从哪根柱子移到哪根柱子移动的步数stepreturnstep;cout<<"disknmovefromxtoy";hanoi的动图实现

hanoi算法分析第一种如果只有一个盘子，直接把盘子从a柱子移到c柱子第二种不只一个盘子，设有n只盘子。1.先把a柱子上的n-1只盘子柱子移到c柱子,借助b；2.把最大的盘子直接从a柱子移到c柱子；3.把b柱子上的n-1只盘子子移到c柱子,借助a柱。if(n==1){step++;output<<"movenfromatob.";}hanoi(n-1,a,c,b);move(n,a,c);hanoi(n-1,b,c,a)入栈：最大的盘子n先入栈出栈：最小的盘子1可以直接出栈；否则出栈后要让小一级的盘子n-1入栈，然后自己出栈，最后小一级的盘子n-1入栈，hanoi的栈实现

出栈的条件：设标志位tag==1时代码

inthanio(intn){ nodex; SeqStack<int>s; intstep=0; s.Push(n,n,'a','b','c'); while(!s.Empty()){ s.Pop(x); if(x.tag==1) cout<<"第"<<++step<<"步:"<<'\t'<<"将盘子"<<x.n<<"从"<<x.a<<"移到"<<x.c<<endl; else{ s.Push(x.n-1,x.n-1,x.b,x.a,x.c); s.Push(1,x.n,x.a,x.b

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论