汉诺塔问题的非递归算法分析.pdf
《汉诺塔问题的非递归算法分析.pdf》由会员分享,可在线阅读,更多相关《汉诺塔问题的非递归算法分析.pdf(4页珍藏版)》请在三一文库上搜索。
1、汉诺塔递归与非递归算法研究 作者 1,作者 2,作者 3 3 (陕西师范大学计算机科学学院,陕西西安 710062) 摘要 : 摘要内容 (包括目的、方法、结果和结论四要素) 摘要又称概要 ,内容提要 .摘要是以提供文献内容梗概为目的,不加 评论和补充解释,简明 ,确切地记述文献重要内容的短文.其基本要素包括研究目的,方法 ,结果和结论 .具体地讲就是研究工作的 主要对象和范围,采用的手段和方法,得出的结果和重要的结论,有时也包括具有情报价值的其它重要的信息.摘要应具有独立 性和自明性 ,并且拥有与文献同等量的主要信息,即不阅读全文 ,就能获得必要的信息. 关键词 :关键词 1; 关键词 2;
2、关键词 3;(一般可选38 个关键词,用中文表示,不用英文 Title 如 :XIN Ming-ming , XIN Ming (1.Dept. of *, University, City Province Zip Code, China;2.Dept. of *, University, City Province Zip Code, China;3.Dept. of *, University, City Province Zip C ode, China) Abstract: abstract(第三人称叙述,尽量使用简单句;介绍作者工作(目的、方法、结果)用过去时,简述作者结论用一 般
3、现在时) Key words: keyword1; keyword2; keyword3; ( 与中文关键词对应,字母小写( 缩略词除外 )) ; 正文部分用小5 号宋体字,分两栏排,其中图表宽度不超过8cm.。设置为A4 页面 1 引言 (一级标题四号黑体加粗) 引言的作用就是引出为什么要写这篇文章,主要有以下 几个方面: (1)如果以采用新方法新理论,就要引出为什么要采用 这种方法; (2)如果是为了阐明某个观点,就要引出目前观点和目 前对所研究领域的现状; (3)为什么要研究“XXX ”算法(为什么要研究它,背 景及必要性) 如:(文中举例内容仅供参考)汉诺塔问题的描述:汉 诺塔 ( T
4、ower of Hanoi )问题又称“世界末日问题”有这样一个 故事 1 。古代有一个焚塔,塔内有3 个基座 A,B,C ,开始时 A基座上有 64 个盘子,盘子大小不等, 大的在下, 小的在上。 有一个老和尚想把这64 个盘子从 A座移到 B座,但每次只容 许移动一个盘子,且在移动过程中,3 个基座上的盘子都始 终保持大盘在下,小盘在上。移动过程中可以利用C基座做 辅助。如图1 所示: ACB n . . . 1 2 图 1 汉诺塔问题 这个问题当时老和尚和众僧们,经过计算后,预言当所 有的盘子都从基柱A 移到基座 B 上时, 世界就将在一声霹雳 中消灭,而梵塔、庙宇和众生也都将同归于尽。
5、其实,不管 这个传说的可信度有多大,如果考虑把64 个盘子, 由一个塔 柱上移到另一根塔柱上,并且始终保持上小下大的顺序。假 设有 n 个盘子,移动次数是f(n). 显然 f(1)=1,f(2)=3,f(3)=7, 且 f(k+1)=2*f(k)+1。此后不难证明f(n)=2 n-1。n=64 时, f(64)= 264-1=18446744073709551615 假如每秒钟一次,共需多长时间呢?一年大约有 31536926 秒,计算表明移完这些金片需要5800 多亿年, 比地球寿命还 要长, 事实上, 世界、 梵塔、庙宇和众生都早已经灰飞烟灭。 对传统的汉诺塔问题,目前还有不少的学者继续研
6、究它 的非递归解法,本文通过对递归算法的研究,. 提示:(1)可以定义问题的规模n, 如盘子的数量; (2) 塔柱的数量(目前有部分理论可以支撑,不妨用计算机实现) 分析规模的变化与算法的复杂度比较。(3)可以对经典的汉 诺塔问题条件放松、加宽,如在经典的汉诺塔问题中大盘只 能在小盘下面,放松其他条件可以定义相邻两个盘子必须满 足大盘只能在小盘下面。其它盘子不作要求。 2 算法设计 2.1 汉诺塔递归算法描述(二级标题小五黑体加粗) 用人类的大脑直接去解3,4或5个盘子的汉诺塔问题还可 以,但是随着盘子个数的增多,问题的规模变的越来越大。 这样的问题就难以完成,更不用说吧问题抽象成循环的机器
7、操作。 所以类似的问题可用递归算法来求解。下面 n个盘的汉 诺塔问题可用如下递归方法实现。 如果 n=1,则将圆盘从 A直接移动到 B。 如果 n=2,则: (1)将 A上的 n-1(等于 1)个圆盘移到 C上; (2)再将 A上的一个圆盘移到B上; (3)最后将 C上的 n-1 (等于 1)个圆盘移到 B上。 如果 n=3,则: A) 将A上的 n-1(等于 2)个圆盘移到 C (借助于 B) ,步骤如下: (1)将 A上的 n-2(等于 1)个圆盘移到 B上。 (2)将 A上的一个圆盘移到C。 (3)将 B上的 n-2(等于 1)个圆盘移到 C。 B)将 A上的一个圆盘移到B。 C)将 C
8、上的 n-1(等于 2)个圆盘移到 B(借助 A) ,步骤如下: (1)将 C上的 n-2 (等于 1)个圆盘移到 A。 (2)将 C上的一个盘子移到B。 (3)将 A上的 n-2 (等于 1)个圆盘移到 B。到此,完成了三 个圆盘的移动过程。 从上面分析可以看出,当n大于等于 2时, 移动的过程可分解 为三个步骤: 第一步把A上的 n-1个圆盘移到 C上; 第二步把A上的一个圆盘移到B上; 第三步把C上的 n-1个圆盘移到 B上; 其中第一步和第三步是类同的。 算法如下:(伪码描述、自然语言描述、流程图) Main 1: int n ; 2: Input(n); 3: Hanoi(n,”A”
9、, ”B”, ”C”) ; 4: Hanoi(n,char a,char b,char c) 5: if (n0) 6: hanoi ( n - 1, a, c, b) ; 7: printf “( %d %n”, n , a, c) ; 8: hanoi ( n - 1,b, a, c) ; 递归算法结构清晰,可读性强,而且很容易用数学归纳 法证明算法的正确性,然而它的运行效率较低,它的时间复 杂度主要在程序嵌套调用所用的时间。T(N)=2T(N-1)+1, 容易 计算出T(N)=2 N-1.若在程序中消除递归调用,使其转化为非 递归调用算法。通常,消除递归采用一个用户定义的栈来模 拟系统的
10、递归调用工作栈,从而达到递归改为非递归算法的 目的。 2.2 汉诺塔非递归算法描述 2.2.1非递归 1: 遍历二叉树搜索解空间 (三级标题小五楷体) 通过定义 MAXSTACK栈, 可将递归算法转化为非递归调 用算法。具体程序如下: #define MAXSTACK 100 /* 栈的最大深度*/ int N = 3; /* N 阶问题 /* int c = 1; /* 一个全局变量,表示目前移动的步数*/ struct hanoi /* 存储汉诺塔的结构,包括盘的数目和三个盘 的名称*/ int n; char a, b, c; struct hanoi pMAXSTACK; void m
11、ove(char a, int n, char c) /* 移动函数,表示把某个盘从 某根针移动到另一根针*/ printf(“%d. Move disk %d from %c to %cn“, c+, n, a, c); void push(struct hanoi *p, int top, char a, char b, char c,int n) ptop+1.n = n - 1; ptop+1.a = a; ptop+1.b = b; ptop+1.c = c; void unreverse_hanoi(struct hanoi *p) /* 汉诺塔的非递归算法*/ int top =
12、 0; while (top = 0) while (ptop.n 1) /* 向左走到尽头*/ push(p, top, ptop.a, ptop.c, ptop.b, ptop.n); top+; if (ptop.n = 1) /* 叶子结点*/ move(ptop.a, 1, ptop.b); top-; if (top = 0) /* 向右走一步*/ move(ptop.a, ptop.n, ptop.c); top-; push(p, top, ptop+1.b, ptop+1.a, ptop+1.c, ptop+1.n); top+; int main(void) printf(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 汉诺塔 问题 递归 算法 分析
链接地址:https://www.31doc.com/p-5112392.html