欢迎来到天天文库
浏览记录
ID:43182477
大小:409.50 KB
页数:20页
时间:2019-10-01
《递归算法及程序实现》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第28课递归算法及程序实现1.汉诺塔问题。相传古代东方有一座寺庙,庙内有三根座桩,第一根座桩上叠有一摞64个中心带孔、直径各不相同的圆盘片,这些圆盘片叠成塔状,即越上面的盘片的直径越小。要把这64个盘片从第一根座桩搬到第三根座桩上,搬动的规则如下:(1)一次只能从有盘片的座桩上取走一个盘片;(2)被取走的盘片必须马上放到另一根座桩上;(3)任何一根座桩上如果有一个以上盘片,则这些盘片必须呈直径上小下大的塔状。需要搬动多少次才能把64个盘片从第一根座桩搬到第三根座桩上?2.用递归算法计算n的阶乘n!。新课引入相传古代东方有一座寺庙
2、,庙内有三根座桩,第一根座桩上叠有一摞64个中心带孔、直径各不相同的圆盘片,这些圆盘片叠成塔状,即越上面的盘片的直径越小。要把这64个盘片从第一根座桩搬到第三根座桩上,搬动的规则如下:(1)一次只能从有盘片的座桩上取走一个盘片;(2)被取走的盘片必须马上放到另一根座桩上;(3)任何一根座桩上如果有一个以上盘片,则这些盘片必须呈直径上小下大的塔状。把“从一根座桩上取走一个盘片,放到另一根座桩上”说成是“搬动一次”。问题提出需要搬动多少次才能把64个盘片从第一根座桩搬到第三根座桩上?先将问题缩小化,尝试2个盘、3个盘、4个盘、5个盘等的
3、搬动过程。Hanoi游戏(点击上图运行体验)3个盘片移动过程演示4个盘片移动过程演示5个盘片移动过程演示经过实践可知,根据规则将3个盘从座柱A搬到座柱C上,最少需要搬动7次,整个移动过程如下:(0)是最初的状态,(1)是经1次搬动后的状态,(2)是经2次搬动后的状态,等等。分析(0)、(3)、(4)、(7)这几个过程,搬动3个盘片的过程可分为先将2个盘从座柱A搬到座柱B,然后将最后1个盘从座柱A搬到座柱C,最后再将2个盘从座柱B搬到座柱C。当分析搬动4个盘片的过程时,整个过程可分为先将3个盘从座柱A搬到座柱B,然后将最后1个盘从座柱A搬
4、到座柱C,最后再将3个盘从座柱B搬到座柱C,以此类推,移动n(n>1)个盘从座柱A移动到座柱C的过程如下:步骤①:将(n-1)个盘从座柱A搬动到座柱B,在座柱C的帮助下步骤②:将第N个盘从座柱A搬动到座柱C步骤③:将(n-1)个盘从座柱B搬动座柱C,在座柱A的帮助下移动规则是每次只能搬动一个盘,所以搬动(n-1)个盘时,肯定需要另一个柱子帮助。当n=1时,也就是搬动一个盘,那只要直接将这个盘从座柱A搬到座柱C就可以了。(1)汉诺塔的算法流程图算法Hanoi(n,a,c,b)的含义是:将n个盘从座柱A(源柱)搬至座柱C(目标柱)在座
5、柱B(帮助柱)的帮助下完成,算法的含义十分重要,它说明了过程Hanoi四个参数所表示的含义。这种直接或者间接地调用自身的算法就是递归算法。递归算法的特点:递归过程一般通过函数或子过程来实现。递归算法的实质:是把问题转化为规模缩小了的同类问题的子问题,然后递归调用函数(或过程)来表示问题的解。(2)编写程序代码。'Hanoi过程四个参数分别是盘数,源柱,目标柱,帮助柱,过程完成功能将N个盘从源柱搬动到目标柱在帮助柱帮助下。Subhanoi(nAsInteger,aAsString,cAsString,bAsString)If(n=1
6、)Then'当只有一个盘时num=num+1'计算器增加1List1.AddItem(Str(num)+""+a+"->"+c)'搬动一个盘从源柱到目标柱ElseCallhanoi(n-1,a,b,c)'搬动N-1个盘从座柱A到座柱B,在座柱C帮助下num=num+1List1.AddItem(Str(num)+""+a+"->"+c)Callhanoi(n-1,b,c,a)'搬动N-1个盘从座柱B到座柱C,在座柱A帮助下EndIfEndSub(3)搬动次数计算将n个盘片从座柱A搬到座柱C,完成步骤①需要h(n-1)次搬动,
7、完成步骤②只需要1次搬动,而完成步骤③也需要搬动h(n-1)次。这样,把n个盘片从座柱A搬到座柱C所需的搬动次数h(4)=2×h(3)+1=2×(2×h(2)+1)+1=2×(2×(2×h(1)+1)+1)+1=2×(2×(2×1+1)+1)+1=24-1=15,2×(2×(2×1+1)+1)+1恰好是二进制数1111转化为十进制的式子。汉诺塔问题是一个经典的NP问题,对于计算机来说仍然是一个“难”的问题,“难”主要是说程序执行步数随着N的增长呈指数级增长,如果塔上有64个盘,则搬动次数是二进制11111…111(64个1)次,换算为
8、十进制数值为264-1=18446744073709551615,目前按每秒可以完成10亿次搬动(大约是230),也需要234秒,大约是198841天,约544年,即使有这样的速度在有生之年是无法看到所有
此文档下载收益归作者所有