5.5递归算法实例及程序实现VIP免费

5.5递归算法实例及程序实现01【实例1】计算n的阶乘02【实例1】计算n的阶乘Functionf(nAsInteger)AsLongIfn<=1Then___________________Else___________________EndIfEndFunctionPrivateSubCommand1_Click()DimnAsIntegerDimnkAsLongn=Val(Text1.Text)nk=f(n)Text2.Text=Str(nk)EndSubf=1f=n*f(n-1)03思考：如果不用递归算法，用传统的算法，又该如何实现呢？【实例1】计算n的阶乘S=1Fori=nto1Step-1S=S*iNextiPrintSS=1:______________DoWhile__________S=S*i______________LoopPrintSFor语句Do语句04i=ni>=1i=i-1【实例2】兔子数列问题月份12345678910对数1123581321345505Functionf(nAsInteger)AsLongIfn=1Orn=2Then____________________Else____________________EndIfEndFunctionf=1f=f(n-1)+f(n-2)【实例2】兔子数列问题PrivateSubCommand1_Click()DimnAsInteger,iAsIntegerDima(1To100)AsLongn=Val(Text1.Text)a(1)=1:a(2)=1Fori=3Tona(i)=a(i-1)+a(i-2)NextiText2.Text=Str(a(n))EndSubPrivateSubCommand1_Click()DimnAsInteger,iAsIntegerDima(1To100)AsLongn=Val(Text1.Text)a(1)=1:a(2)=1:__________DoWhilei<=n____________________________________________________________________Text2.Text=Str(a(n))EndSubFor语句Do语句06i=3a(i)=a(i-1)+a(i-2)i=i+1Loop问题与练习(P125)用递归算法设计如下算法，列出递推公式(1)(2)222...21nSnSn21)1(......81614121f(n)=n*n+f(n-1）(n>1)f(1)=1(n=1)f(n)=(-1)^n/(2*n)+f(n-1)(n>1)f(1)=-0.5(n=1)07【实例5】十进制数转二进制数DimnAsInteger,rAsIntegerDimsAsStringn=Val(Text1.Text)DoWhilen<>0______________________________________________s=CStr(r)+sLoopText2.Text=sFunctionDtoB(xAsInteger)AsLongIfx=0ThenDtoB=_____________ElseDtoB=_________________EndIfEndFunctionFor循环递归算法08r=nmod2n=n\20DtoB(x\2)*10+xmod2【实例6】小猴吃桃问题DimdaysAsInteger,iAsIntegerDimsAsIntegerDima(10)AsIntegera(10)=1days=Val(Text1.Text)Fori=10To1Step-1a(i-1)=(a(i)+1)*2NextiText2.Text=Str(a(days))Functiontao(daysAsInteger)AsIntegerIfdays=10Thentao=1Else_______________________EndIfEndFunctionFor语句递归算法09tao=(tao(days+1)+1)*2【实例7】求最大公约数PrivateSubCmd1_Click()DimxAsIntegerDimyAsIntegerDimrAsIntegerDimsAsIntegerx=Val(Text1.Text)y=Val(Text1.Text)r=xModyDoWhiler<>0_____________________________________________Loops=yText3.Text=Str(s)EndSub10x=yy=rr=xmodyFunctiongcd(xAsInteger,yAsInteger)AsIntegerIfy=0Thengcd=xElse_______________________EndIfEndFunctionPrivateSubCommand1_Click()DimAAsInteger,BAsIntegerDimgysAsLongA=Val(Text1.Text)B=Val(Text2.Text)_____________________________Text3.Text=Str(gys)EndSub11求最大公约数递归算法gcd=gcd(y,xmody)gys=gcd(A,B)【实例8】汉诺塔问题有n张圆盘，依半径大小自下而上(半径从大到小)套在a柱上，b柱和c柱开始时无圆盘。每次只允许移动最上面一张圆盘到另外的柱子上去，但绝不允许发生柱子上出现大盘子在上，小盘子在下的情况。请你设计将a柱上的n张搬移到c柱的方法。12【实例8】汉诺塔问题13DimnumAsLongSubhanoi(nAsInteger,aAsString,cAsString,bAsString)'Hanoi过程四个参数分别是N个盘数，源柱，目标柱，帮助柱，过程的意思是将N个盘从源柱搬动到目标柱通过帮助柱帮助下。If(n=1)Then'当只有一个盘时num=num+1List1.AddItem(Str(num)+""+a+"->"+c)'搬动一个盘从源柱到目标柱Else_________________________'搬动N-1个盘从A柱到B柱，在C柱帮助下num=num+1List1.AddItem(Str(num)+""+a+"->"+c)_________________________'搬动N-1个盘从B柱到C柱，在A柱帮助下EndIfEndSubPrivateSubCommand1_Click()DimnAsIntegern=Val(Text1.Text)Callhanoi(n,"A","C","B")'将N个盘从源柱A柱搬动到目标柱C柱在帮助柱B柱帮助下List1.AddItem("共"+Str(num)+"次")EndSubPrivateSubText1_Click()num=0：List1.Clear：Text1.Text=""EndSubCallhanoi(n-1,a,b,c)Callhanoi(n-1,b,c,a)141516