VB递归算法ppt课件.ppt

1、递归算法,1,2,从前有座山， 山里有座庙， 庙里有个老和尚， 给小和尚讲故事， 故事是什么呢？,从前有座山， 山里有座庙， 庙里有个老和尚， 给小和尚讲故事， 故事是什么呢？,从前有座山， 山里有座庙， 庙里有个老和尚， 给小和尚讲故事， 故事是什么呢？,老和尚的故事,3,案例一、小猴吃桃,有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子?,4,我们能不能这样设一个函数：,算法描述： funct

2、ion 你有多少桃子？（第几天） 如果 第10天，那么 桃子数 = 1 否则 end function,桃子数=,第n天的桃子数,第n+1天的桃子数,2,-1,=,第n天的桃子数,=,(第n+1天的桃子数+1)*2,（ 明天的桃数+1）* 2,5,算法实现： Function tao(days As Integer) As Integer If days = 10 Then tao = 1 Else tao = (tao(days + 1) + 1) * 2 End If End Function,Tao(1)=(tao(2)+1)*2,Tao(2)=(tao(3)+1)*2,Tao(3)=(

3、tao(4)+1)*2,Tao(8)=(tao(9)+1)*2,Tao(9)=(tao(10)+1)*2,Tao(10)= 1,调用,调用,调用,调用,调用,返回,返回,返回,返回,返回,6,案例二、斐波那契数列问题,斐波纳契数列，又称黄金分割数列，指的是这样一个数列： 1、1、2、3、5、8、13、21、34、55 这个数列从第三项开始，每一项都等于前两项之和。 求：数列中的第N项是几？,算法规则： 1、最初两项值为1 2、第N项的值是它之前两项之和,求第N个斐波纳切数 if 是最初两项 then 斐波纳切数=1 else 斐波纳切数=前两个斐波纳切数之和 end if,7,案例二、斐波那契

4、数列问题,求第N个斐波纳切数 if 是最初两项 then 斐波纳切数=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,8,案例三、求最大公约数,早在公元前300年左右，欧几里得就在他的著作几何原本中给出了高效的解法辗转相除法。 辗转相除法的方法是用较大的数X除以较小的数Y，得到余数Z 如果余数为0，则较小数Y就是两者的最

5、大公约数。 例如：27和9的最大公约数就是9 如果余数不为0，则较小数Y与余数Z的最大公约数就是X与Y的的最大公约数 例如：33和9 的最大公约数就是9与6的最大公约数,9,案例三、求最大公约数,求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

6、和 Z,Y,10,递归,将要处理的问题划分为一个或多个子问题，而处理子问题的方法与处理原问题的方法是一样的，这样的处理方法称为递归,11,递归算法小结,在程序中，递归算法表现为函数在运行过程中调用了自己。 每一次递归调用，在处理问题的规模上都有所缩小 在问题的规模极小时，必须能给出直接的解答,求年龄： Function Age(n As Integer) As Integer if n=1 then age= 3 else age= age(n-1) * 2 - 2 end if End Function,求斐波那契数： Function Fib (n as Integer)as Intege

7、r If n3 then Fib =1 Else Fib = Fib (n-2)+Fib (n-1) End if End Function,12,从前有座山， 山里有座庙， 庙里有个老和尚， 给小和尚讲故事， 故事是什么呢？,从前有座山， 山里有座庙， 庙里有个老和尚， 给小和尚讲故事， 故事是什么呢？,从前有座山， 山里有座庙， 庙里有个老和尚， 给小和尚讲故事， 故事是什么呢？,再看老和尚的故事,这个过程算不算是递归？,怎么改才能算是递归？,13,拓展练习:求 n!,n! = 1234n n!=(n-1)! n 1!=1,14,拓展练习:恶魔与农夫,有一位农夫不满于自己的贫困,一天,他正在抱怨上天的不公平,一个恶魔出现在他的眼前.他对农夫说:“我可以帮助你,