信息技术选修1 数据与数据结构5.2 迭代与递归一等奖课件ppt

这是一份信息技术选修1 数据与数据结构5.2 迭代与递归一等奖课件ppt，共27页。PPT课件主要包含了学习目标，引入兔子有多少对，算一算，找出规律，裴波那契数列，程序实现一，程序实现二，迭代算法的概念，开发产品，反复修改等内容，欢迎下载使用。

能理解迭代的算法思想。
能合理选用数据结构，理清迭代初值，迭代式及结束迭代。
能用自然语言、流程图、Pythn语言描述迭代算法。
能分析迭代算法的效率高低。
能熟练应用迭代算法，解决生活、学习中的问题。
意大利数学家裴波那契（L．Fibnacci）在他的1228年版的《算经》一书中记述了有趣的兔子问题：假定我们有一雄一雌一对刚出生的兔子，它们在长到一个月大小时开始怀孕（自然状态是六个月左右），在第二月结束时，雌兔子产下另一对兔子，过了一个月后它们也开始繁殖，如此这般持续下去。每只雌兔在开始繁殖后每月都产下一对兔子，假定没有兔子死亡，在一年后总共有多少对兔子？
a1=1a2=1an=an-1+an-2(当n>2时)
答案：一年后总共有144对兔子。
裴波那契数为：1，1，2，3，5，8，13 其规律是：数列中第1，2个数都是1，从第三个数起，该数是前面2个数之和，此数列称为Fibnacci数列。第n项计算公式为：Fib(n)=1 (n<=2) Fib(n)=Fib(n-1)+Fib(n-2) (n>2)因此从第三个元素开始循环，Fib(3)=Fib(1)+Fib(2) Fib(4)=Fib(2)+Fib(3)Fib(5)=Fib(3)+Fib(4)……
a=[1,1]fr i in range(2,12): a.append(0) a[i]=a[i-1]+a[i-2]print(a[11])
#定义列表a为每个月的兔子对数，第1,2月的兔子数量为1对
#对第3个月至第12月逐一计算兔子对数
#a最后添加一个初值为0的元素，存第i个月兔子数
#求出第i个月的兔子对数(迭代表达式)
#输出第12月的兔子对数
12个月的兔子对数用a数组（a列表）来存储
a = 1 b = 1fr i in range(2,12): c = a + b a = b b = c print(c)
#定义a，b为第1月,第2月的兔子数量为1对
#对第3个月至第12月每月计算兔子对数
#当前一个月的值b迭代前两个月的值a
#当月的值c迭代前一个月的值b
#从第3个月起兔子对数为前面两个月的兔子对数之和
a,b,c三个变量存储近三个月的兔子数
迭代是重复反馈的活动，其目的通常是为了使结果符合目标需求。
让计算机重复执行一组指令(或步骤)，这组指令(或步骤)每执行一次时，都会让变量从原值递推出一个新值。
一个直接或间接地不断由旧值递推出新值的变量；
将变量从前一个值推出其下一个值的公式(或关系)；
a = 1 b = 1fr i in range(3,13): c = a + b a = b b = c print(c)
1、确定迭代变量a( 前2个月),b（前1个月）
2、建立迭代关系：从第3个月起兔子对数为前面两个月的兔子对数之和。
3、设定迭代第3至第12月
迭代法求a的平方根： 教材P119
迭代变量x的迭代过程：
当前后两次求出的x值（xn+1和xn）的差的绝对值（ ▏xn+1-xn ▏）为0.000002时（即 ▏xn+1-xn ▏<=0.00001） 停止迭代，得出结果。如2的平方根约为1.414214。
求平方根迭代程序流程图
（1）输入a, 求x估测近似值 x0=a；x1=(x0+a/x0)/2
①若〡x1-x0〡>10-5②迭代式x0=x1 x1=(x0+a/x0)/2③否则〡x1-x0〡<=10-5④输出a 的平方根x1
〡x1-x0〡>0.00001
x0=x1;x1=(x0+a/x0)/2
x0=a；x1=(x0+a/x0)/2
编写求平方根迭代程序并上机调试：
#程序一：a=int(input("请输入一个需要求其平方根的数："))x0=a x1=(x0+a/x0)/2while (abs(x1-x0))>0.00001: x0=x1 x1=(x0+a/x0)/2print(a,"的平方根约为",rund(x1,6))
牛顿迭代法计算正数a的算术根
#X1与x0无限接近，相差0.00001
在保留小数位数不同的情况下，程序效率差异也大
#程序二：a=int(input("请输入一个需要求其平方根的数："))x=a/2while ((abs((x+a/x)/2-x))>0.00001): x=(x+a/x)/2print(a,"的平方根约为",rund((x+a/x)/2,6))
#(x+a/x)/2为a的平方根
#程序三：a=int(input("请输入一个需要求其平方根的数："))x=a/2while abs(x*x-a) > 1e-5:x=(x+a/x)/2print(a,"的平方根约为",rund((x+a/x)/2,6))
#平方根X的初始值a/2
#X*X与a无限接近，相差0.00001
x0=a或x0=a/2
(abs(x1-x0))>0.00001（保留5位小数位数）
(abs(x1-x0))>0.000001（保留6位小数位数）
初始值、终止条件等直接影响算法效率
利用欧几里得算法求最大公约数的pythn程序，其中m和n是迭代变量，迭代关系是n→m和m%n→n，由旧值推出新值，然后循环执行，直到余数为0，结束迭代。m=int(input("请输入数m:"))n=int(input("请输入数n:"))while n!=0: t=n m=tprint( )
1.完善划线处代码：
一个楼梯有n阶，上楼可以一步上一阶，也可以一步上二阶。要求：编写一个程序，输入一个正整数n(表示楼梯阶数)，输出共有多少种不同的走法可以到达第n阶。
2.程序设计并调试：
n=int(input("请输入台阶数量："))a=1;b=2fr i in range(3,n+1): c=a+b a=b b=cif n==1 r n==2: print(n)else: print(c)
生活实战应用：秋游安排车辆
某班家委会根据参加秋游的同学到达指定上车点时间和每位同学可以等待的时间信息，安排车辆接送参加秋游活动同学去秋游点白云山脚（考虑车子座位数量<=4人）。参加秋游活动同学到达上车点的时间和可以等待的时间用长度为7的字符串表示，例如ut.txt中第一行“ 08:11 4 xixi”表示xixi同学当天8点11分到达上车点，最多等待4分钟(每个同学的等待时间都小于10)，那么最晚8点23分出发去秋游点(若8点23分刚到的同学也一同出发)。编写 Pythn 程序，统计接送n个参加秋游活动同学所需的最少车辆数。运行程序，显示所有同学提交的信息，数据已经按到达时间先后排列，程序运行结果显示所需的最少车辆数。
（1）若将图中第 1 行“08:11 4”数据改为“08:11 2”，程序输出的结果是否会发生改变 （A.会改变 B.不会改变）
生活实战应用：安排车辆
（2）实现上述功能的部分 Pythn 程序如下，请在划线处填入合适的代码。 a=[];b=[];c=[];xz=4 #每辆车最多坐4人#从文件ut.txt中读取每一行数据在列表a中，n为参加秋游人数，代码略fr i in range(n): b.append(0);c.append(0) b[i]=int(a[i][:2])*60+int(a[i][3:5]) c[i]=b[i]+int(a[i][6:8])
tt=0;i=0;k=1while ifr i in range(n):print(a[i])print("接送所有参加秋游同学最少需要",tt,"辆车")
这个fr循环求出到指定地点的时间b列表，最迟离开时间c列表
tt为接送所有参加秋游同学最少需要车辆数
外循环求出当前i同学最迟离开时间c[i]前与最早离开j同学同一辆车拼车过程
内循环求出当前i同学最迟离开时间c[i]前与最早离开j同学b[j]同一辆车不超过4人的拼车过程,若拼不成，j同学为另起一辆车
迭代算法的数学原理与注意事项
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）
1.操作系统从win xp、win7、win10……,不断更新过程可以看出,一款产品是不断试错,不断根据用户体验反馈,快速调整和完善得到的。这个例子体现的算法思想是 ( ) A.枚举 B.迭代 C.解析 D.递归2.利用迭代算法处理问题，需要考虑以下三个方面：①确定迭代变量：一个直接或间接地不断由旧值递推出新值的变量；② ：将变量从前一个值推出其下一个值的公式(或关系)；③控制迭代过程：设定迭代结束的条件。