文档介绍：第28课递归算法及程序实现新课引入相传古代东方有一座寺庙,庙内有三根座桩,第一根座桩上叠有一摞64个中心带孔、直径各不相同的圆盘片,这些圆盘片叠成塔状,即越上面的盘片的直径越小。要把这64个盘片从第一根座桩搬到第三根座桩上,搬动的规则如下: (1)一次只能从有盘片的座桩上取走一个盘片; (2)被取走的盘片必须马上放到另一根座桩上; (3)任何一根座桩上如果有一个以上盘片,则这些盘片必须呈直径上小下大的塔状。 把“从一根座桩上取走一个盘片,放到另一根座桩上”说成是“搬动一次”。问题提出需要搬动多少次才能把64个盘片从第一根座桩搬到第三根座桩上? 先将问题缩小化,尝试2个盘、3个盘、4个盘、5个盘等的搬动过程。 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搬到座柱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(目标柱)在座柱B(帮助柱)的帮助下完成,算法的含义十分重要,它说明了过程Hanoi四个参数所表示的含义。这种直接或者间接地调用自身的算法就是递归算法。 递归算法的特点:递归过程一般通过函数或子过程来实现。 递归算法的实质:是把问题转化为规模缩小了的同类问题的子问题,然后递归调用函数(或过程)来表示问题的解。(2)编写程序代码。 'Hanoi过程四个参数分别是盘数,源柱,目标柱,帮助柱,过程完成功能将N个盘从源柱搬动到目标柱在帮助柱帮助下。 Subhanoi(nAsInteger,aAsString,cAsString,bAsString) If(n=1)Then'当只有一个盘时 num=num+1'计算器增加1 (Str(num)+""+a+"->"+c)'搬动一个盘从源柱到目标柱 Else Callhanoi(n-1,a,b,c)'搬动N-1个盘从座柱A到座柱B,在座柱C帮助下 num=num+1 (Str(num)+""+a+"->"+c) Callhanoi(n-1,b,c,a)'搬动N-1个盘从座柱B到座柱C,在座柱A帮助下 EndIf EndSub