2021—2022学年高中信息技术粤教版选修 4.5.1 从裴波那契的兔子问题看递归算法 课件 (21张PPT)

(共21张PPT)
4.5.1 从裴波那契的兔子问题看递归算法
授课教师：
学科：高中信息技术
单位：合肥市第六中学
教材：广东教育出版社 信息技术（选修1）《算法与程序设计》
一、兔子问题
小兔子
兔子
大兔子
一个月
一个月
生出
一、兔子问题
如果年初养了一对小兔子，问到年底时将有多少对兔子？（假设兔子没有死亡而且严格按照上述规律长大与繁殖）
（1）分析问题
第1个月（对）：
第2个月（对）：
第3个月（对）：
第4个月（对）：
第5个月（对）：
第6个月（对）：
第7个月（对）：
1
1
2
3
5
8
13
（1）分析问题
1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月
小兔 1 1 1 2 3 5 8 13 21 34 55
大兔 1 1 2 3 5 8 13 21 34 55 89
合计 1 1 2 3 5 8 13 21 34 55 89 144
（2）设计算法
F(N)=
｛
1
1
F(N-1)+F(N-2)
N=1
N=2
N>2
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368
（2）设计算法
F(N)=
｛
1
1
F(N-1)+F(N-2)
N=1
N=2
N>2
递归算法：函数不断引用自身，直到引用的对象已知，否则
会成为死循环而不能正常结束。思路清晰，代码少。
例：当N=5，求F(N)
F(5)=F(4)+F(3)
F(4)=F(3)+F(2)
F(3)=F(2)+F(1)
F(2)=1
F(1)=1
F(1)=1
F(2)=1
F(3)=F(2)+F(1)=2
F(4)=F(3)+F(2)=3
F(5)=F(4)+F(3)=5
不足：
递归算法的效率不高。
（3）编写程序
递归算法
If （条件）Then 表达式1 Else: 表达式2
（3）编写程序
递归算法
Function Fib(ByVal N As Integer) As Long
If Then Else:
End Function
N < 3
Fib = 1
Fib = Fib(N - 1) + Fib(N - 2)
（3）编写程序
Function Fib(ByVal N As Integer) As Long
If N < 3 Then Fib = 1 Else: Fib = Fib(N - 1) + Fib(N - 2)
End Function
Private Sub Command1_Click()
N = Val(Text1.Text)
Text2.Text = "第" & N & "月的兔子对数是：" & Fib(N)
End Sub
递归算法
（4）调试程序
完成学习资源包中的任务1
其他算法
If （条件）Then 表达式1 Else: 表达式2
For循环语句
基本格式
For 循环变量=初值 To 终值 step 步长
语句组
Next 循环变量
其他算法
Private Sub Command1_Click()
n = Val(Text1.Text)
If n < 3 Then
c = 1 ‘每月的兔子对数
Else
a = 1: b = 1
For i = 3 To n
c = a + b: a = b: b = c ‘a每月小兔子 b每月大兔子
Next i
End If
Print c
End Sub
学习资源包学案任务2
比较不同算法的效率（任务3）
递归算法 其他算法
当N=10
当N=40
总结
斐波那契数列
递归算法
任务4：在VB语言环境下用递归算法求n!（n!=1*2*3*···*n），如图