第28课-递归算法及程序实现.ppt

高中信息技术必修2：算法与程序设计 授课人：杨鹏 授课人：杨鹏 第一课件网 免费教学资源下载基地 * 第一课件网 免费教学资源下载基地 * 第一课件网 免费教学资源下载基地 * 第一课件网 免费教学资源下载基地 * 第一课件网 免费教学资源下载基地 * 第一课件网 免费教学资源下载基地 * 第28课 递归算法及程序实现 　1.汉诺塔问题。相传古代东方有一座寺庙，庙内有三根座桩，第一根座桩上叠有一摞64个中心带孔、直径各不相同的圆盘片，这些圆盘片叠成塔状，即越上面的盘片的直径越小。要把这64个盘片从第一根座桩搬到第三根座桩上，搬动的规则如下：（1）一次只能从有盘片的座桩上取走一个盘片；（2）被取走的盘片必须马上放到另一根座桩上；（3）任何一根座桩上如果有一个以上盘片，则这些盘片必须呈直径上小下大的塔状。需要搬动多少次才能把64个盘片从第一根座桩搬到第三根座桩上？ 　2.用递归算法计算n的阶乘n!。 新课引入 相传古代东方有一座寺庙，庙内有三根座桩，第一根座桩上叠有一摞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个盘从源柱搬动到目标柱在帮助柱帮助下。Sub hanoi n As Integer, a As String, c As String, b As String If n 1 Then 当只有一个盘时num num + 1 计算器增加1List1.AddItem Str num + + a + - + c 搬动一个盘从源柱到目标柱ElseCall hanoi n - 1, a, b, c 搬动N-1个盘从座柱A到座柱B，在座柱C帮助下num num + 1List1.AddItem Str num + + a + - + c Call hanoi n - 1, b, c, a 搬动N-1个盘从座柱B到座柱C，在座柱A帮助下End IfEnd Sub （3）搬动次数计算将n个盘片从座柱A搬到座柱C，完成步骤①需要h n-1 次搬动，完成步骤②只需要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