递归算法及程序实现

递归算法及程序实现第28课递归算法及程序实现　1.汉诺塔问题。相传古代东方有一座寺庙，庙内有三根座桩，第一根座桩上叠有一摞64个中心带孔、直径各不相同的圆盘片，这些圆盘片叠成塔状，即越上面的盘片的直径越小。要把这64个盘片从第一根座桩搬到第三根座桩上，搬动的规则如下：（1）一次只能从有盘片的座桩上取走一个盘片；（2）被取走的盘片必须马上放到另一根座桩上；（3）任何一根座桩上如果有一个以上盘片，则这些盘片必须呈直径上小下大的塔状。需要搬动多少次才能把64个盘片从第一根座桩搬到第三根座桩上？　2.用递归算法计算n的阶乘n!。新课引入相传...

第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个盘从源柱搬动到目标柱在帮助柱帮助下。Subhanoi(nAsInteger,aAsString,cAsString,bAsString)If(n=1)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)次搬动，完成步骤②只需要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）次，换算为十进制数值为264-1=18446744073709551615，目前按每秒可以完成10亿次搬动（大约是230），也需要234秒，大约是198841天，约544年，即使有这样的速度在有生之年是无法看到所有的搬动过程。例：求n的阶乘。计算ｎ的阶乘ｆ(ｎ)＝ｎ×(ｎ－１)×(ｎ－２)×…×３×２×１，这是一个规模为ｎ的问题。假定已经计算出了ｆ(ｎ－１)，则ｆ(ｎ)＝ｎ×ｆ(ｎ－１)。从另一个角度看，规模为ｎ的问题ｆ(ｎ)，可以依赖于较小规模(例如规模为ｎ－１)的问题ｆ(ｎ－１)的解决，依此类推f(n-1)=(n-1)×f(n-2)......直至f(2)=2×f(1)很明显f(1)=1这样可以按相反的次序，一步一步地把f(k)计算出来(k=2,3,...,n)。这种按同一方法把问题的计算规模逐步变小的过程叫做“递归的展开”，然后逐级代入的过程叫做“递归的返回”。对于问题f(5)，递归的展开是：f(5)=5×f(4)f(4)=4×f(3)f(3)=3×f(2)f(2)=2×f(1)f(1)=1递归的返回是f(1)=1f(2)=2×f(1)=2×1=2f(3)=3×f(2)=3×2=6f(4)=4×f(3)=4×6=24f(5)=5×f(4)=5×24=120问题f(5)的计算结果为120。(1)算法流程图（点击运行）（2）编写程序代码。Functionf(nAsInteger)AsLong'求n的阶乘Ifn<=1Thenf=1'当n=1时，函数f的返回值为1Elsef=n*f(n-1)'递归地调用函数f来计算(n-1)!的值EndIfEndFunction（3）运行调试程序根据算法流程图,填空完善已经设计好的界面和部分代码的求n阶乘算法，并进行调试。课堂练习1.用递归方法设计一个算法，计算12+22+…+n2参考答案：1.1）写出递推表达式f(n)=n*n+f(n-1)(n>1)f(1)=1(n=1)2）递归算法流程图2.用递归方法设计一个算法，计算2.1）写出递推表达式f(n)=(-1)^n/(2*n)+f(n-1)(n>1)f(1)=-0.5(n=1)2）递归算法流程图

                    本文档为【递归算法及程序实现】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

递归算法及程序实现

你可能还喜欢