5.2迭代与递归 课件 2022—2023学年浙教版（2019）高中信息技术选修1（12张PPT）
文档属性
| 名称 | 5.2迭代与递归 课件 2022—2023学年浙教版（2019）高中信息技术选修1（12张PPT） |  | |
| 格式 | pptx | ||
| 文件大小 | 1.4MB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 浙教版（2019） | ||
| 科目 | 信息技术（信息科技） | ||
| 更新时间 | 2022-09-28 22:57:29 | ||
图片预览
文档简介
(共12张PPT)
迭代算法与递归算法
选修一：数据结构
探究一：写一段程序实现求 n！
迭代是重复反馈过程的活动，其目的通常是为了使结果符合目标要求
n=5
result=n #第一次迭代
result=n*4 #第二次迭代
result=n*3 #第三次迭代
result=n*2 #第四次迭代
result=n*1 #第五次迭代
迭代关系式
探究一：迭代的概念
迭代算法：
①重复反馈的过程
②迭代过程：对迭代过程的重复
③每一次迭代结果会被用来作为下一次迭代的初始值
探究一：迭代的概念
迭代算法解决问题过程：
①确定迭代变量。
迭代算法处理的问题时，由旧值递推出新值的变量称为迭代变量。
②建立迭代关系式（数值关系）。
从变量的前一个值推出其下一个值的公式（或关系）。
③控制迭代过程（结束条件）。
迭代过程在经过若干次重复执行以后要能结束，因此，要设定迭代结束的条件。
探究二：迭代算法求a的平方根
迭代算法：
①确定迭代变量
②建立迭代关系式
③控制迭代过程
迭代法求a的平方根：
①估计近似值x,令x等于x和a/x的平均数
②x的值逼近于a的平方根，当误差小于时，将x的值作为a的平方根
探究二：迭代算法求a的平方根
迭代算法：
①确定迭代变量
②建立迭代关系式
③控制迭代过程
每次迭代结果将作为下一次迭代的初始值
1（n=1）
n*fac(n-1)（n≠1）
fac(n)
探究三：递归算法求 n！
递归：大问题中嵌套小问题，通过调用自身，不断降低问题的规模，进而求解
n = 5
5！=5*4！
4！=4*3！
3！=3*2！
2！=2*1！
1 ！ = 1
递推：分解问题
回归：代值求解
fac(4)
4*fac(3)
第1次调用
第2次调用
3*fac(2)
第3次调用
2*fac(1)
第4次调用
1
返回值1
返回值1
返回值2
返回值6
探究三：递归过程
探究三：递归算法求 n！
递归：大问题中嵌套小问题，通过调用自身，不断降低问题的规模，进而求解
1（n=1）
n*fac(n-1)（n≠1）
fac(n)
设计递归算法：确定递归公式和递归结束条件
探究四：如何用栈实现递归
1*fac(0)
2*fac(1)
3*fac(2)
4*fac(3)
5*fac(4)
fac(1)
fac(2)
fac(3)
fac(4)
fac(5)
通过不断的调用自己缩小问题规模，进而求解。
空间复杂度大
探究五：辨析迭代与递归
迭代：由旧值不断推出新值的过程。它包括三个方面：
①确定迭代变量；
②建立迭代关系式；
③控制迭代过程，使程序能够停止下来。
递归：是一种缩小问题规模，进而构造出整个问题解的思想方法。
①递推 ②回归
迭代难点：建立正确的迭代公式，通常要借助循环语句。
递归难点：思想比较难以理解，递归程序的效率相对不高。
探究五：辨析迭代与递归
斐波那契数列是这样一个数列：1,1,2,3,5,8,13,21,34，…，其定义如下：
f(0)=0，f(1)=1，f(n)=f(n-1)+f(n-2)(n>=2)。编程求f(40)的值
迭代程序
f0=0
f1=1
n=2
while n<=40:
f=f1+f0
f0=f1
f1=f
n=n+1
print(f1)
递归程序
def fib(n):
if n<1:
return 0
elif n==1:
return 1
else:
return fib(n-1)+fib(n-2)
print(fib(40))
迭代算法与递归算法
选修一：数据结构
探究一：写一段程序实现求 n！
迭代是重复反馈过程的活动，其目的通常是为了使结果符合目标要求
n=5
result=n #第一次迭代
result=n*4 #第二次迭代
result=n*3 #第三次迭代
result=n*2 #第四次迭代
result=n*1 #第五次迭代
迭代关系式
探究一：迭代的概念
迭代算法：
①重复反馈的过程
②迭代过程：对迭代过程的重复
③每一次迭代结果会被用来作为下一次迭代的初始值
探究一：迭代的概念
迭代算法解决问题过程：
①确定迭代变量。
迭代算法处理的问题时，由旧值递推出新值的变量称为迭代变量。
②建立迭代关系式（数值关系）。
从变量的前一个值推出其下一个值的公式（或关系）。
③控制迭代过程（结束条件）。
迭代过程在经过若干次重复执行以后要能结束，因此，要设定迭代结束的条件。
探究二：迭代算法求a的平方根
迭代算法：
①确定迭代变量
②建立迭代关系式
③控制迭代过程
迭代法求a的平方根：
①估计近似值x,令x等于x和a/x的平均数
②x的值逼近于a的平方根，当误差小于时，将x的值作为a的平方根
探究二：迭代算法求a的平方根
迭代算法：
①确定迭代变量
②建立迭代关系式
③控制迭代过程
每次迭代结果将作为下一次迭代的初始值
1（n=1）
n*fac(n-1)（n≠1）
fac(n)
探究三：递归算法求 n！
递归：大问题中嵌套小问题，通过调用自身，不断降低问题的规模，进而求解
n = 5
5！=5*4！
4！=4*3！
3！=3*2！
2！=2*1！
1 ！ = 1
递推：分解问题
回归：代值求解
fac(4)
4*fac(3)
第1次调用
第2次调用
3*fac(2)
第3次调用
2*fac(1)
第4次调用
1
返回值1
返回值1
返回值2
返回值6
探究三：递归过程
探究三：递归算法求 n！
递归：大问题中嵌套小问题，通过调用自身，不断降低问题的规模，进而求解
1（n=1）
n*fac(n-1)（n≠1）
fac(n)
设计递归算法：确定递归公式和递归结束条件
探究四：如何用栈实现递归
1*fac(0)
2*fac(1)
3*fac(2)
4*fac(3)
5*fac(4)
fac(1)
fac(2)
fac(3)
fac(4)
fac(5)
通过不断的调用自己缩小问题规模，进而求解。
空间复杂度大
探究五：辨析迭代与递归
迭代：由旧值不断推出新值的过程。它包括三个方面：
①确定迭代变量；
②建立迭代关系式；
③控制迭代过程，使程序能够停止下来。
递归：是一种缩小问题规模，进而构造出整个问题解的思想方法。
①递推 ②回归
迭代难点：建立正确的迭代公式，通常要借助循环语句。
递归难点：思想比较难以理解，递归程序的效率相对不高。
探究五：辨析迭代与递归
斐波那契数列是这样一个数列：1,1,2,3,5,8,13,21,34，…，其定义如下：
f(0)=0，f(1)=1，f(n)=f(n-1)+f(n-2)(n>=2)。编程求f(40)的值
迭代程序
f0=0
f1=1
n=2
while n<=40:
f=f1+f0
f0=f1
f1=f
n=n+1
print(f1)
递归程序
def fib(n):
if n<1:
return 0
elif n==1:
return 1
else:
return fib(n-1)+fib(n-2)
print(fib(40))