5.5递归算法实例及程序实现.ppt

,山上有座庙,庙里有个老和尚对小和尚讲故事,讲的是,从前有座山,山上有座庙,庙里有个老和尚对小和尚讲故事。讲的是,从前有座山,山上有座庙,庙里有个老和尚对小和尚讲故事。讲的是……什么是递归?:函数或过程调用它本身,称为递归。、较难解决的问题变成规模较小的、容易解决的同一问题,规模较小的问题又变成规模更小的问题,当问题小到一定程度时,可以直接得出它的解,从而得到原来问题的解。即采用“大事化小,小事化了”的基本思想。:(1)每一步骤解决问题的方法要一致(递归公式);(2)有结束条件。从前有座山,山上有座庙,这个故事没有结束条件,不能用递归算法来解决。:斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”。斐波那契数列一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔都不死,那么n个月以后可以繁殖多少对兔子?我们不妨拿新出生的一对小兔子分析一下:第一,二个月小兔子没有繁殖能力,所以还是一对;第三个月,生下一对小兔总数共有两对;第四个月,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对;------依次类推可以列出下表:表中数字1,1,2,3,5,8---构成了一个数列。这个数列有个十分明显的特点,那是:前面相邻两项之和,(nasInteger)asIntegerIfn<3Thentu=1Elsetu=tu(n-1)+tu(n-2)mand1_Click()DimnAsIntegern=Val()=“第”+Str(n)+“个月后有"+Str(tu(n))+"对兔子"EndSub月数123456789101112…兔子对数1123581321345589144…分析:求第n个月后兔子的数目是多少对?递归公式:tu(n)=tu(n-1)+tu(n-2)当n>=3时结束条件:tu(n)=1当n=1或2解析:求解第6个月之后有多少对兔子的递归过程第一阶段:未知已知tu(6)=tu(5)+tu(4)tu(5)=tu(4)+tu(3)tu(4)=tu(3)+tu(2)tu(3)=tu(2)+tu(1)第二阶段:已知未知tu(2)=1tu(1)=1tu(3)=tu(2)+tu(1)=2tu(4)=tu(3)+tu(2)=2+1=3tu(5)=tu(4)+tu(3)=5tu(6)=tu(5)+tu(4)=8Functiontu(nasInteger)asIntegerIfn<3Thentu=1Elsetu=tu(n-1)+tu(n-2)mand1_Click()DimnAsIntegern=Val()=“第”+Str(n)+“个月后有"+Str(tu(n))+"对兔子"EndSub例2:小猴在第一天摘下若干个桃子,当天吃掉一半多一个;第二天吃了剩下的桃子的一半多一个;以后每天都吃尚存桃子的一半多一个,到第7天早上想吃时发现桃子只剩下一个,问小猴第一天共摘下了多少个桃子?用自定义函数来解决此递归问题的VB程序如下:Functiontao(nAsInteger)AsIntegerIfn=7Thentao=1Elsetao=EndifEndFunctionPrivate mand1_Click() ="小猴摘下的桃子数为:"+str(tao(1))+"只"End Sub 则画线处的语句应为()A.(tao(n+1)-1)*2B.(tao(n+1)+1)*2C.(tao(n-1)-1)*2D.(tao(n-1)+1)*2B分析:Tao(1)=(tao(2)+1)*2Tao(2)=(tao(3)+1)*2Tao(3)=(tao(4)+1)*2Tao(4)=(tao(5)+1)*2Tao(5)=(tao(6)+1)*2第一天早上第二天早上第三天早上第四天早上第五天早上第六天早上第七天早上Tao(7)=1Tao(6)=(tao(7)+1)*,函数gcb用递归算法求两个正整数m、n的最大公约数的算法如下:(1)当m<n时,交换m、n的值(2)当m整除n时,返回n值;否则将n和mmodn作为参数重新调用该函数。Private mand1_Click()   DimaasIntegerDimbasIntegera=val()b=val()=Str(gcb(a,b))End Sub Functiongcb(mA