浙教版信息技术选修1 5.5 递归算法实例及程序实现 课件(共18张PPT)

递归算法实例及程序实现
从前有座山，
山里有座庙，
庙里有个老和尚，
给小和尚讲故事，
故事是什么呢？
从前有座山，
山里有座庙，
庙里有个老和尚，
给小和尚讲故事，
故事是什么呢？
从前有座山，
山里有座庙，
庙里有个老和尚，
给小和尚讲故事，
故事是什么呢？
老和尚的故事…
数果子问题
2
3
3
1
4
2
？
数果子问题
递归
将要处理的问题划分为一个或多个子问题，而处理子问题的方法与处理原问题的方法是一样的，这样的处理方法称为递归。
案例一、到底几岁了？
我比左边的2倍小2岁
我比左边的2倍小2岁
我比左边的2倍小2岁
我比左边的2倍小2岁
我比左边的2倍小2岁
我比左边的2倍小2岁
我3岁
案例一、到底几岁了？
算法规则：
1、第1个人的年龄=3\
2、第N个人的年龄=第N-1人的年龄*2-2
求第N个人的年龄：
if 是第1个人 then
年龄=3
else
年龄=前一人年龄*2-2
end if
案例一、到底几岁了？
VB代码：
Function Age(n As Integer) As Integer
if n=1 then
age= 3
else
age= age(n-1) * 2 - 2
end if
End Function
求第N个人的年龄
if 是第一个人 then
年龄=3
else
年龄=前一人年龄*2-2
end if
案例二、斐波那契数列问题
斐波纳契数列，又称黄金分割数列，指的是这样一个数列：
1、1、2、3、5、8、13、21、34、65……
这个数列从第三项开始，每一项都等于前两项之和。
求：数列中的第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
递归算法小结
在程序中，递归算法表现为函数在运行过程中调用了自己。
每一次递归调用，在处理问题的规模上都有所缩小，在问题的规模极小时，必须能给出直接的解答。
求年龄：
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 Integer
If n<3 then
Fib =1
Else
Fib = Fib (n-2)+Fib (n-1)
End if
End Function
从前有座山，
山里有座庙，
庙里有个老和尚，
给小和尚讲故事，
故事是什么呢？
从前有座山，
山里有座庙，
庙里有个老和尚，
给小和尚讲故事，
故事是什么呢？
从前有座山，
山里有座庙，
庙里有个老和尚，
给小和尚讲故事，
故事是什么呢？
再看老和尚的故事…
这个过程算不算是递归？
怎么改才能算是递归？
拓展练习:求 n!
n! = 1×2×3×4×……×n
n!=(n-1)! ×n
1!=1
拓展练习:恶魔与农夫
有一位农夫不满于自己的贫困。一天,他正在抱怨上天的不公平,一个恶魔出现在他的眼前，他对农夫说:“我可以帮助你,你只要从桥上每走一次,你口袋里的钱就会增加一倍。但是作为报酬,每次你要付给我24法郎,如何?”农夫看了看自己口袋里的钱,不假思索地答应了。但是三次之后，农夫身上连一毛钱都没剩下。那么这个农民在遇见魔鬼以前有多少钱呢？
谢 谢