《VB递归算法72633.ppt》由会员分享，可在线阅读，更多相关《VB递归算法72633.ppt（15页珍藏版）》请在三一文库上搜索。
1、递归算法,从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？,从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？,从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？,老和尚的故事,案例一、小猴吃桃,有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子?,我们能不能这样设一个函数：,算法描述： function 你有多少桃子？（第几天） 如果
2、第10天，那么 桃子数 = 1 否则 end function,桃子数=,第n天的桃子数,第n+1天的桃子数,2,-1,=,第n天的桃子数,=,(第n+1天的桃子数+1)*2,（ 明天的桃数+1）* 2,算法实现：Function tao(days As Integer) As IntegerIf days = 10 Then tao = 1Else tao = (tao(days + 1) + 1) * 2End IfEnd Function,Tao(1)=(tao(2)+1)*2,Tao(2)=(tao(3)+1)*2,Tao(3)=(tao(4)+1)*2,Tao(8)=(tao(9)+
3、1)*2,Tao(9)=(tao(10)+1)*2,Tao(10)= 1,调用,调用,调用,调用,调用,返回,返回,返回,返回,返回,案例二、斐波那契数列问题,斐波纳契数列，又称黄金分割数列，指的是这样一个数列： 1、1、2、3、5、8、13、21、34、55这个数列从第三项开始，每一项都等于前两项之和。求：数列中的第N项是几？,算法规则：1、最初两项值为12、第N项的值是它之前两项之和,求第N个斐波纳切数 if 是最初两项 then 斐波纳切数=1 else 斐波纳切数=前两个斐波纳切数之和 end if,案例二、斐波那契数列问题,求第N个斐波纳切数 if 是最初两项 then 斐波纳切数=
4、1 else 斐波纳切数=前两个斐波纳切数之和 end if,Function Fib (n as Integer)as Integer If then Fib = Else Fib = End if End Function,n3,Fib (n-2)+Fib (n-1),1,1、1、2、3、5、8、13、21、34、65,案例三、求最大公约数,早在公元前300年左右，欧几里得就在他的著作几何原本中给出了高效的解法辗转相除法。 辗转相除法的方法是用较大的数X除以较小的数Y，得到余数Z 如果余数为0，则较小数Y就是两者的最大公约数。 例如：27和9的最大公约数就是9 如果余数不为0，则较小数Y与
5、余数Z的最大公约数就是X与Y的的最大公约数 例如：33和9 的最大公约数就是9与6的最大公约数,案例三、求最大公约数,求X与Y的公约数： Z是X除Y得到的余数 If Z为0 then 公约数= Else 公约数= 的公约数 End if,Function GYS(x as Integer,y as Integer)as Integer Dim z as Integer z= If Z=0 then GYS= Else GYS= End if End Function,X mod Y,Y,GYS( Y , Z ),Y 和 Z,Y,递归,将要处理的问题划分为一个或多个子问题，而处理子问题的方法与处
6、理原问题的方法是一样的，这样的处理方法称为递归,递归算法小结,在程序中，递归算法表现为函数在运行过程中调用了自己。每一次递归调用，在处理问题的规模上都有所缩小在问题的规模极小时，必须能给出直接的解答,求年龄：Function Age(n As Integer) As Integer if n=1 then age= 3 else age= age(n-1) * 2 - 2 end ifEnd Function,求斐波那契数：Function Fib (n as Integer)as Integer If n3 then Fib =1 Else Fib = Fib (n-2)+Fib (n-1)
7、 End if End Function,从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？,从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？,从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？,再看老和尚的故事,这个过程算不算是递归？,怎么改才能算是递归？,拓展练习:求 n!,n! = 1234nn!=(n-1)! n1!=1,拓展练习:恶魔与农夫,有一位农夫不满于自己的贫困,一天,他正在抱怨上天的不公平,一个恶魔出现在他的眼前.他对农夫说:“我可以帮助你,你只要从桥上每走一次,你口袋里的钱就会增加一倍.但是作为报酬,每次你要付给我24法郎,如何?”农夫看了看自己口袋里的钱,不假思索地答应了。但是三次之后，农夫身上连一毛钱都没剩下。那么这个农民在遇见魔鬼以前有多少钱呢？,