(
课件网) 5.2 迭 代 与 递 归 （一） ——— 迭 代 册 别：选择性必修1 学 科：高中信息技术（浙教版） 学习目标： 能理解迭代的算法思想。 能合理选用数据结构，理清迭代初值，迭代式及结束迭代。 能用自然语言、流程图、Python语言描述迭代算法。 能分析迭代算法的效率高低。 能熟练应用迭代算法，解决生活、学习中的问题。 引入：兔子有多少对？ 意大利数学家裴波那契（L．Fibonacci）在他的1228年版的《算经》一书中记述了有趣的兔子问题：假定我们有一雄一雌一对刚出生的兔子，它们在长到一个月大小时开始怀孕（自然状态是六个月左右），在第二月结束时，雌兔子产下另一对兔子，过了一个月后它们也开始繁殖，如此这般持续下去。每只雌兔在开始繁殖后每月都产下一对兔子，假定没有兔子死亡，在一年后总共有多少对兔子？ 时间（月） 1 2 3 4 …… 兔子（对） 1 1 2 3 算一算: 时间（月） 1 2 3 4 5 6 7 …… 兔子（对） 1 1 2 3 5 找出规律 时间 1 2 3 4 5 6 7 …… 总数 1 1 2 3 5 8 成年兔子 0 1 1 2 3 5 新小兔子 1 0 1 1 2 3 a1=1 a2=1 an=an-1+an-2(当n>2时) 算一算: 月份 成年兔 新小兔 共有的兔子 1 1 1 2 1 1 3 1 1 2 4 2 1 3 5 3 2 5 6 5 3 8 7 8 5 13 8 13 8 21 9 21 13 34 10 34 21 55 11 55 34 89 12 89 55 144 答案： 一年后总共有144对兔子。 裴波那契数列： 裴波那契数为：1，1，2，3，5，8，13 其规律是：数列中第1，2个数都是1，从第三个数起，该数是前面2个数之和，此数列称为Fibonacci数列。 第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] for 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 = 1 for 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 #输出第12月的兔子对数 #从第3个月起兔子对数为前面两个月的兔子对数之和 a,b,c三个变量存储近三个月的兔子数 迭代算法的概念: 迭代是重复反馈的活动，其目的通常是为了使结果符合目标需求。 开发产品 反复修改 符合客户需求 让计算机重复执行一组指令(或步骤)，这组指令(或步骤)每执行一次时，都会让变量从原值递推出一个新值。 迭代算法三个方面： 1、确定迭代变量 2、建立迭代关系 3、控制迭代过程 一个直接或间接地不断由旧值递推出新值的变量； 将变量从前一个值推出其下一个值的公式(或关系)； 设定迭代结束的条件。 a = 1 b = 1 for i in range(3,13): c = a + b a = b b = c print(c) 1、确定迭代变量 a( 前2个月),b（前1个月） 2、建立迭代关系：从第3个月 起兔子对数为前面两个月的兔 子对数之和。 1、确定迭代变量 a( 前2个月),b（前1个月） 3、设定迭代第3至第12月 迭代法求a的平方根： 教材P119 基本思路：先估测一个近似值x，然后不断令x等于x和的平均数（迭代公式为： (n≥0)），经过若干次迭代后，x的值将逐渐接近a的平方根（当与值无限接近时，可看作= ，则公式 可以化简为=, 就是a的平方根） 迭代式：是什么 可终止的条件是什么 1、确定迭代变量： 2、建立迭代关系: 3、控制迭代过程: X, ... ...
