VB递归算法.pptx

文档介绍：递归算法
从前有座山,
山里有座庙,
庙里有个老和尚,
给小和尚讲故事,
故事是什么呢?
从前有座山,
山里有座庙,
庙里有个老和尚,
给小和尚讲故事,
故事是什么呢?
从前有座山,
山里有座庙,
庙里有个老和尚,
给小和尚讲故事,
故事是什么呢?
老和尚的故事…
案例一、小猴吃桃
有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半,仍觉得不过瘾又多吃了一个,以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候,看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子?
我们能不能这样设一个函数:
算法描述:
    function 你有多少桃子?(第几天)
   如果第10天,那么
桃子数= 1
  否则

    end function
桃子数=
第n天的桃子数
第n+1天的桃子数
2
-1
=
第n天的桃子数
=
(第n+1天的桃子数+1)*2
( 明天的桃数+1)* 2
算法实现:
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)=(tao(4)+1)*2
Tao(8)=(tao(9)+1)*2
Tao(9)=(tao(10)+1)*2
Tao(10)= 1
调用
调用
调用
调用
调用
返回
返回
返回
返回
返回
案例二、斐波那契数列问题
斐波纳契数列,又称黄金分割数列,指的是这样一个数列:
1、1、2、3、5、8、13、21、34、55……
这个数列从第三项开始,每一项都等于前两项之和。
求:数列中的第N项是几?
算法规则:
1、最初两项值为1
2、第N项的值是它之前两项之和
求第N个斐波纳切数
if 是最初两项 then
斐波纳切数=1
else
斐波纳切数=前两个斐波纳切数之和
end if
案例二、斐波那契数列问题
求第N个斐波纳切数
if 是最初两项 then
斐波纳切数=1
else
斐波纳切数=前两个斐波纳切数之和
end if
Function Fib (n as Integer)as Integer
If then
Fib =
Else
Fib =
End if
End Function
n<3
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与余数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